wake-up-neo.com

Big-oh gegen Big-Theta

Mögliches Duplikat:
Was ist der Unterschied zwischen Θ (n) und O (n)?

Mir scheint, wenn die Leute informell über die Komplexität von Algorithmen sprechen, sprechen sie über Big-Oh. Aber in formellen Situationen sehe ich oft Big-Theta mit gelegentlich eingeworfenem Big-Oh. Ich weiß mathematisch, was der Unterschied zwischen den beiden ist, aber auf Englisch, in welcher Situation würde man Big-Oh verwenden, wenn man Big-Theta meint falsch oder umgekehrt (ein beispielhafter Algorithmus wäre wünschenswert)?

Bonus: Warum verwenden Leute scheinbar immer Big-Oh, wenn sie informell sprechen?

90
Boris Yeltz

Big-O ist eine Obergrenze.

Big-Theta ist eine enge Grenze, d. H. Eine obere und untere Grenze.

Wenn sich die Leute nur darum sorgen, was am schlimmsten passieren kann, ist big-O ausreichend. es heißt, dass "es nicht viel schlimmer kommen kann". Je enger die Grenze, desto besser natürlich, aber eine enge Grenze ist nicht immer einfach zu berechnen.

Siehe auch

Verwandte Fragen


Das folgende Zitat aus Wikipedia wirft ebenfalls ein Licht auf:

Informell, insbesondere in der Informatik, darf die Big-O-Notation häufig missbraucht werden, um eine asymptotische enge Bindung zu beschreiben, bei der die Verwendung der Big-Theta-Notation in einem bestimmten Kontext sachgerechter sein könnte.

Zum Beispiel, wenn man eine Funktion betrachtet T(n) = 73n3+ 22n2+ 58, Alle folgenden sind im Allgemeinen akzeptabel, aber die Dichtheit der Bindung (d. H. Die Kugeln 2 und 3 unten) wird gewöhnlich der Nachlässigkeit der Bindung (d. H. Die Kugel 1 unten) vorgezogen.

  1. T(n) = O(n100), Identisch mit T(n) ∈ O(n100)
  2. T(n) = O(n3), Identisch mit T(n) ∈ O(n3)
  3. T(n) = Θ(n3), Identisch mit T(n) ∈ Θ(n3)

Die entsprechenden englischen Aussagen sind:

  1. T(n) wächst asymptotisch nicht schneller als n100
  2. T(n) wächst asymptotisch nicht schneller als n3
  3. T(n) wächst asymptotisch so schnell wie n3.

Während also alle drei Aussagen wahr sind, sind in jeder nach und nach mehr Informationen enthalten. In einigen Bereichen wird jedoch die Big O-Notation (Aufzählungszeichen 2 in den obigen Listen) häufiger verwendet als die Big Theta-Notation (Aufzählungszeichen 3 in den obigen Listen), da Funktionen, die langsamer wachsen, wünschenswerter sind.

93

Ich bin Mathematiker und habe immer wieder Big-O-, Big-Theta- und Big-Omega-Notationen gesehen und gebraucht, nicht nur wegen der Komplexität von Algorithmen. Wie die Leute sagten, ist Big-Theta eine zweiseitige Bindung. Genau genommen sollten Sie es verwenden, wenn Sie erklären möchten, dass ein Algorithmus so gut funktioniert und dass entweder dieser Algorithmus nicht besser funktioniert oder kein Algorithmus besser funktioniert. Wenn Sie beispielsweise sagen, dass beim Sortieren Sort (n (log n)) Vergleiche für die Eingabe im ungünstigsten Fall erforderlich sind, dann erklären Sie, dass es einen Sortieralgorithmus gibt, der für jede Eingabe O (n (log n)) Vergleiche verwendet ; und dass es für jeden Sortieralgorithmus eine Eingabe gibt, die ihn zwingt, Vergleiche mit Ω (n (log n)) durchzuführen.

Ein enger Grund, warum Menschen O anstelle von Ω verwenden, besteht darin, Haftungsausschlüsse in Bezug auf die schlimmsten oder durchschnittlichen Fälle zu streichen. Wenn Sie sagen "Sortieren erfordert O (n (log n)) Vergleiche", dann gilt die Aussage weiterhin für günstige Eingaben. Ein weiterer enger Grund ist, dass selbst wenn ein Algorithmus für die Ausführung von X Zeit benötigt (f (n)), ein anderer Algorithmus möglicherweise eine bessere Leistung erbringt, sodass Sie nur sagen können, dass die Komplexität von X selbst O (f (n)) ist.

Es gibt jedoch einen breiteren Grund, warum Menschen O informell verwenden. Auf menschlicher Ebene ist es eine Qual, immer zweiseitige Aussagen zu treffen, wenn die Gegenseite aus dem Kontext "offensichtlich" ist. Da ich Mathematiker bin, würde ich im Idealfall immer vorsichtig sagen: "Ich nehme einen Regenschirm, wenn es regnet" oder "Ich kann 4 Bälle jonglieren, aber nicht 5", anstatt "Ich nehme einen Regenschirm, wenn es regnet" Regen "oder" Ich kann 4 Bälle jonglieren ". Aber die anderen Hälften solcher Aussagen sind oft offensichtlich beabsichtigt oder offensichtlich nicht beabsichtigt. Es ist nur die menschliche Natur, über das Offensichtliche nachlässig zu sein. Es ist verwirrend, Haare zu spalten.

Leider ist es in einem rigorosen Bereich wie Mathematik oder Algorithmentheorie auch verwirrend, keine Haare zu spalten. Die Leute werden unweigerlich O sagen, wenn sie Ω oder Θ hätten sagen sollen. Das Überspringen von Details, weil sie "offensichtlich" sind, führt immer zu Missverständnissen. Dafür gibt es keine Lösung.

46
Greg Kuperberg

Weil meine Tastatur eine O-Taste hat.
Es gibt keine Θ- oder Ω-Taste.

Ich vermute, die meisten Leute sind ähnlich faul und verwenden O, wenn sie mean bedeuten, weil es einfacher ist, etwas zu schreiben.

17
Ax.

Ein Grund, warum Big O so oft benutzt wird, ist, dass es so oft benutzt wird. Viele Leute sehen die Notation und denken sie wissen, was es bedeutet, und verwenden sie dann selbst (falsch). Das passiert oft bei Programmierern, deren formale Ausbildung nur so weit ging - ich war selbst einmal schuldig.

Ein weiterer Grund ist, dass es auf den meisten nicht-griechischen Tastaturen einfacher ist, ein großes O einzugeben als ein großes Theta.

Aber ich denke, viel liegt an einer Art Paranoia. Ich habe ein bisschen mit verteidigungsbezogener Programmierung gearbeitet (und wusste damals sehr wenig über Algorithmenanalyse). In diesem Szenario ist die Leistung im schlimmsten Fall immer das, woran die Leute interessiert sind, da der schlimmste Fall möglicherweise zum falschen Zeitpunkt auftritt. Es spielt keine Rolle, ob die tatsächliche Wahrscheinlichkeit dafür z. weit weniger als die Wahrscheinlichkeit, dass alle Mitglieder einer Schiffsbesatzung im selben Moment einen plötzlichen Herzinfarkt erleiden - es könnte immer noch passieren.

Natürlich haben viele Algorithmen unter sehr häufigen Umständen den schlimmsten Fall - das klassische Beispiel ist das Einfügen der Reihenfolge in einen Binärbaum, um eine effektiv einfach verknüpfte Liste zu erhalten. Eine "echte" Bewertung der durchschnittlichen Leistung muss die relative Häufigkeit verschiedener Arten von Eingaben berücksichtigen.

8
Steve314

Bonus: Warum verwenden Leute scheinbar immer Big-Oh, wenn sie informell sprechen?

Denn in Big-Oh, diese Schleife:

for i = 1 to n do
    something in O(1) that doesn't change n and i and isn't a jump

ist O(n), O(n^2), O(n^3), O(n^1423424). big-oh ist nur eine obere Schranke, was die Berechnung erleichtert, da Sie keine enge Schranke finden müssen.

Die obige Schleife ist jedoch nur big-theta(n).

Was ist die Komplexität des Sieb von Eratosthenes ? Wenn Sie O(n log n) sagten, würden Sie sich nicht irren, aber es wäre auch nicht die beste Antwort. Wenn Sie big-theta(n log n) sagen, liegen Sie falsch.

5
IVlad

Weil es Algorithmen gibt, deren Best-Case schnell ist und daher technisch gesehen ein großes O ist, kein großes Theta.

Big O ist ein obere Schranke, Big Theta ist ein Äquivalenzrelation.

3
Alexandre C.

Hier gibt es viele gute Antworten, aber mir ist aufgefallen, dass etwas fehlt. Die meisten Antworten scheinen zu implizieren, dass der Grund, warum Menschen Big O anstelle von Big Theta verwenden, ein Problem ist, und in einigen Fällen kann dies zutreffen. Oft ist ein Beweis, der zu einem Big-Theta-Ergebnis führt, weitaus komplizierter als ein Beweis, der zu Big-O führt. Dies gilt normalerweise, aber ich glaube nicht, dass dies in großem Zusammenhang mit der Verwendung einer Analyse gegenüber der anderen steht.

Wenn wir über Komplexität sprechen, können wir viele Dinge sagen. Große O-Zeit-Komplexität sagt uns nur, in welcher Obergrenze ein Algorithmus garantiert abläuft. Big Omega wird weitaus seltener diskutiert und gibt die Mindestlaufzeit eines Algorithmus an, eine Untergrenze. Nun sagt uns Big Theta, dass diese beiden Zahlen für eine gegebene Analyse tatsächlich gleich sind. Dies sagt uns, dass die Anwendung eine sehr strenge Laufzeit hat, die nur um einen Wert abweichen kann, der asymptotisch geringer ist als unsere Komplexität. Viele Algorithmen haben einfach keine oberen und unteren Grenzen, die zufällig asymptotisch äquivalent sind.

Die Verwendung von Big O anstelle von Big Theta ist also technisch immer gültig, während die Verwendung von Big Theta anstelle von Big O nur dann gültig ist, wenn Big O und Big Omega zufällig gleich sind. Zum Beispiel hat Einfügesort eine Zeitkomplexität von Big О bei n ^ 2, aber sein bestes Szenario setzt sein Big Omega bei n. In diesem Fall wäre es nicht richtig zu sagen, dass seine Zeitkomplexität Big Theta von n oder n ^ 2 ist, da es sich um zwei verschiedene Grenzen handelt, die als solche behandelt werden sollten.

1
Daynew

Ich habe Big Theta gesehen und bin mir ziemlich sicher, dass mir der Unterschied in der Schule beigebracht wurde. Ich musste es allerdings nachschlagen. Das sagt Wikipedia:

Big O ist die am häufigsten verwendete asymptotische Notation zum Vergleichen von Funktionen, obwohl Big O in vielen Fällen durch Big Theta Θ für asymptotisch engere Grenzen ersetzt werden kann.

Quelle: Big O Notation # verwandte asymptotische Notation

Ich weiß nicht, warum Leute Big-O benutzen, wenn sie formal sprechen. Vielleicht liegt es daran, dass die meisten Menschen mit Big-O besser vertraut sind als mit Big-Theta? Ich hatte vergessen, dass Big-Theta überhaupt existiert, bis Sie mich daran erinnerten. Obwohl mein Gedächtnis jetzt aufgefrischt ist, kann ich es letztendlich in Gesprächen verwenden. :)

0
Vivin Paliath