Ich verstehe $ f (n) \ in O (g (n)) $ mathematisch: $ f (n) $ nicht wachsen schneller als $ g (n) $. Formal gesehen existiert $ \ c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
In ähnlicher Weise bedeutet $ f (n) \ in \ Theta (g (n)) $, dass $ f (n) $ ungefähr so schnell wächst wie $ g (n) $. dh $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Was ich nicht verstehe, ist, warum Leute großes Oh für die Laufzeit von verwenden Ein Algorithmus? Sollten wir nicht großes Theta verwenden? Wenn wir „Laufzeit“ eines Algorithmus sagen, beziehen wir uns auf die Laufzeit im ungünstigsten Fall, d. H. $ T (n) = max \ {ALG (x): | x | = n \} $.
Beispiel: Die Laufzeit der linearen Suche im ungünstigsten Fall für eine Eingabe der Größe $ n $ ($ n $ Elemente und ein Zielwert) ist $ \ Theta (n). $ und $ O (n) $, aber $ \ Theta (n) $ gibt weitere Informationen. Warum verwenden Algorithmusbücher $ O (n) $ und nicht $ \ Theta (n) $.
Kommentare
- Oft ist es ‚ s, weil wir ‚ einfach keine enge Big-Theta-Grenze für die Laufzeit eines Algorithmus erhalten können. Wenn ein Algorithmus ausreichend kompliziert ist, kann es passieren, dass das Beste, was wir tun können, darin besteht, zu sagen, dass die Laufzeit $ O (n ^ {n!}) $ Ist, wobei es in Wirklichkeit $ \ Theta (2 ^ {n \) sein kann log n \ log \ log n}) $.
- Historische Gründe.
- “ Was ich nicht tue ‚ nicht verstehen, warum Leute big Oh für die Laufzeit eines Algorithmus verwenden? Sollte ‚ nicht verwendet werden, verwenden wir großes Theta. “ – Ja. Warten Sie nicht, wir sollten noch genauere Aussagen machen. Aber wenn ich wählen muss, ja, $ \ Theta $!
Antwort
Ich sehe zwei Gründe dafür Leute bevorzugen Big Oh gegenüber Big Theta:
- Die Laufzeitkomplexität eines Algorithmus wird nicht unbedingt als die Worst-Case-Laufzeitkomplexität definiert. Sie können es auch als Laufzeit für eine beliebige Instanz der Länge $ n $ betrachten. Wenn Sie dann beispielsweise schreiben, dass sich die Laufzeit $ t (n) $ eines Algorithmus in $ \ mathcal {O} (n ^ 2) $ befindet, bedeutet dies, dass die von Ihnen gewählte Eingabe der Länge $ n $ immer wächst asymptotisch langsamer als die Funktion $ c \ cdot n ^ 2 $ für eine Konstante $ c $ – also machen wir dann offensichtlich eine Aussage über die Worst-Case-Laufzeit.
- Manchmal, wenn Sie die Laufzeit analysieren Komplexität eines Algorithmus, von dem Sie nicht sicher wissen, ob die von Ihnen angegebene Worst-Case-Komplexität wirklich eng ist. Nehmen Sie zum Beispiel die Laufzeitkomplexität der Matrixmultiplikation Dort ist immer noch nicht klar, ob die Laufzeit $ n ^ {2.3728639} $ wirklich der schlechteste Fall ist. Daher ist bekannt, dass sich die Laufzeit in $ \ mathcal {O} (n ^ {2.3728639}) $ befindet, während sie “ Ich bin mir nicht sicher, ob es sich um $ \ Theta (n ^ {2.3728639}) $ handelt.
Aber Sie haben auch Recht, dass es in einigen Fällen besser wäre, ein großes Theta bereitzustellen gebunden als ein Big Oh gebunden.
Kommentare
- Anzeige 1: Leser, seien Sie vorsichtig , um nicht zu viel darüber zu lesen !
Antwort
Eine (schlampige) Obergrenze ist leichter zu beweisen als eine enge Obergrenze, geschweige denn die obere und untere Grenze.
Die Laufzeit einiger Algorithmen kann nicht mit der gleichen Funktion wie die Ober- / Untergrenze angegeben werden. Z.B. Einfache Sortieralgorithmen sind $ O (n ^ 2) $, haben aber eine Untergrenze von $ \ Omega (n) $.
Einige bestehen darauf, eine asymptotische Leistung über $ \ sim $ zu erzielen, wobei $ f (n) \ sim g (n) $ wenn
$$ \ lim_ {n \ bis \ infty} \ frac {f (n)} {g (n)} = 1 $$
(etwa als Durchschnitt oder Worst-Case in Bezug auf die Anzahl kritischer Operationen, z. B. Vergleiche beim Sortieren). Dh Wackelraum, aber keine (möglicherweise gewaltigen) Konstanten, die unter den Teppich gekehrt wurden.
Kommentare
- Wenn wir uns auf Laufzeit „, wir beziehen uns auf so etwas wie Best-Case-Laufzeit, Worst-Case-Laufzeit und durchschnittliche Laufzeit. Beispiel: Quicksort hat eine Laufzeit von $ \ Theta (n ^ 2) $ im ungünstigsten Fall und eine Laufzeit von $ \ Theta (n) $ im besten Fall. Asymptotik wird für Funktionen richtig definiert.
Antwort
Wenn big-Theta anstelle von big- verwendet werden kann Oh, es sollte verwendet werden, es sei denn, es führt zu unnötigen Schwierigkeiten beim Verständnis. Es gibt einige subtile Fälle, in denen Big-Theta nicht anstelle von Big-Oh verwendet werden kann, z. B.:
Betrachten Sie das folgende Problem: Sortieren Sie Arrays gleicher Länge. Das Programm zur Lösung dieses Problems könnte sein: Wenn die Array-Länge ungerade ist, beenden Sie sofort, wenn die Array-Länge gerade ist, führen Sie eine Blasensortierung durch. Was ist die Worst-Case-Laufzeit dieses Algorithmus?
Es ist sicherlich $ O (n ^ 2) $, aber es ist NICHT $ \ Omega (n ^ 2) $ im Sinne von $ \ Omega $ wird normalerweise definiert. Stattdessen lautet die Laufzeit im ungünstigsten Fall sozusagen „$ \ Omega (n ^ 2) $ unendlich oft“ (Warnung: Nicht-Standard-Terminologie).
Antwort
In der Antwort von „Warum verwenden Algorithmusbücher Big-Oh und nicht Theta“:
Big-Oh wird für die Worst-Case-Analyse und Big-Omega nur für den Best-Case verwendet. Bei der Analyse in Bezug auf Big-Theta sprechen wir jedoch gleichzeitig über Big-Oh & Big-Omega.
dh. Für Big-Theta ist es notwendig, dass Big-Oh == Big-Omega, sonst können wir nicht über Big-Theta sprechen.
Also, wo immer (Buch / irgendein Dokument) Sie die Verwendung von sehen Big-Theta, sie geben die Komplexität von Big-Oh an. & Big-Omega (und beide sind auch gleich). Aber in vielen Fällen sind sie nicht gleich, dann verwenden wir nur Big- Oh, nur für den schlimmsten Fall.