Diese Fragen kamen bei einer Hausaufgabe auf. Ich kann nicht verstehen warum? Es scheint, als würden Sie immer den Algorithmus wählen wollen, der die beste Laufzeit erzeugt.Gründe, warum Sie einen Θ (n log n) -Zeitalgorithmus über einen Θ (n) -Zeitalgorithmus für die gleiche Aufgabe verwenden könnten
Die Big-O- und Big-Theta-Notation implizieren nur, dass die Performance bei beliebig großen Input-Größen zu einer gewissen Grenze tendiert. Zum Beispiel ist die Funktion 99999999n O (n), aber die Funktion (1/9999999999) n^2 ist O (n^2). Für jede Eingabe von angemessener Größe (nicht unendlich groß) ist die O (n^2) -Funktion jedoch offensichtlich schneller.
Mit anderen Worten, wenn Sie Annahmen über Ihre Eingabedaten machen können, gibt es einige Fälle, in denen ein im Allgemeinen schlechterer Algorithmus besser funktionieren kann.
Ein Beispiel aus der Praxis für das obige Konzept ist das Sortieren - es gibt einige Algorithmen, die in O (n) -Zeit funktionieren, wenn das Array bereits sortiert ist (Blasensortierung). Wenn Sie wissen, dass viele Ihrer Arrays bereits sortiert sind, können Sie aus diesem Grund Bubble-Sort über Merge-Sort verwenden.
Ein weiterer Eckfall, bei dem Sie möglicherweise keinen zeiteffizienten Algorithmus verwenden möchten, ist die Speicherplatzeffizienz. Vielleicht programmieren Sie auf einem Embedded-Gerät mit sehr wenig RAM. Sie würden lieber weniger Speicher verbrauchen und etwas mehr Zeit verschwenden, als so perfekt zeiteffizient wie möglich zu sein.
Vielen Dank für diese detaillierte Antwort. Macht viel Sinn. Auch, wenn es Ihnen nichts ausmacht, ein Follow-up zu beantworten, mein Prof. sagte, dass Big Theta als "die beste Zeit des schlimmsten Falles" beschrieben werden kann. Kannst du das mit anderen Worten erklären? Mein Verständnis ist, dass große Theta eine Untergrenze für die Worst-Case-Eingabegröße ist. Aber ich hörte nur Sachen, die ich hörte und bin mir nicht sicher, was das überhaupt bedeutet. – mdm508
@ mdm508 Big O ist die Worst-Case-Zeit Komplexität, große Omega ist die beste Zeit Komplexität. Big Theta ist eine Kombination von beiden - wenn etwas θ (n^2) ist, bedeutet dies, dass sowohl im schlimmsten Fall als auch im besten Fall es oben und unten durch die Funktion k (n^2) begrenzt wird, wobei n beliebig groß ist und k ist eine Konstante. Das ist der Grund, warum Ihr Professor es als "schlimmsten Fall" bezeichnet hat. Wenn dies Ihnen geholfen hat, wird eine positive und akzeptierte Antwort sehr geschätzt. – nhouser9
@ mdm508 Keine Sorge - ich hoffe meine Erklärung hat auf jeden Fall geholfen. – nhouser9