wake-up-neo.com

Was genau bedeutet die Notation?

Ich bin wirklich verwirrt über die Unterschiede zwischen großem O, großem Omega und großer Theta-Notation. 

Ich verstehe, dass das große O die obere Grenze und das große Omega die untere Grenze ist. 

Ich habe gelesen, dass estight boundbedeutet, aber was bedeutet das?

154
user1364768

Dies bedeutet, dass der Algorithmus in der gegebenen Funktion sowohl Big-O als auch Big-Omega ist. 

Wenn es zum Beispiel Ө(n) ist, gibt es eine Konstante k, so dass Ihre Funktion (Laufzeit, was auch immer) für ausreichend große n größer als n*k ist, und eine andere Konstante K, für die Ihre Funktion kleiner ist als n*K ausreichend groß n

Mit anderen Worten, für ausreichend große n ist es zwischen zwei linearen Funktionen eingefügt:

Für k < K und n ausreichend groß, n*k < f(n) < n*K

83
happydave

Lassen Sie uns zuerst verstehen, was Big O, Big Theta und Big Omega sind. Sie sind alle Mengen von Funktionen.

Big O gibt eine obere asymptotische Schranke , während Big Omega eine untere Schranke gibt. Big Theta gibt beides.

Alles, was Ө(f(n)) ist, ist auch O(f(n)), aber nicht umgekehrt.
T(n) soll sich in Ө(f(n)) befinden, wenn es sich sowohl in O(f(n)) als auch in Omega(f(n)) befindet.
In der Mengen-Terminologie ist Ө(f(n)) DAS SCHNITTMENGE VON O(f(n)) UND Omega(f(n))

Beispielsweise ist der schlechteste Fall der Zusammenführungssortierung sowohl O(n*log(n)) als auch Omega(n*log(n)) - und damit auch Ө(n*log(n)), aber es ist auch O(n^2), da n^2 asymptotisch "größer" ist als er. Es ist jedoch nicht Ө(n^2), da der Algorithmus nicht Omega(n^2) ist.

Eine etwas tiefere mathematische Erklärung

O(n) ist eine asymptotische Obergrenze. Wenn T(n)O(f(n)) ist, bedeutet dies, dass es ab einem bestimmten n0 eine Konstante C gibt, so dass T(n) <= C * f(n). Auf der anderen Seite sagt Big-Omega, dass es eine Konstante C2 gibt, so dass T(n) >= C2 * f(n))).

Nicht verwechseln!

Nicht zu verwechseln mit der Analyse der schlimmsten, besten und durchschnittlichen Fälle: Alle drei (Omega, O, Theta) -Notationen beziehen sich nicht auf die besten, schlechtesten und durchschnittliche Fallanalyse von Algorithmen. Jeder von diesen kann auf jede Analyse angewendet werden.

Wir verwenden es normalerweise, um die Komplexität von Algorithmen zu analysieren (wie im obigen Beispiel für die Zusammenführungssortierung). Wenn wir sagen "Algorithmus A ist O(f(n))", meinen wir wirklich "Die Komplexität des Algorithmus im schlimmsten Fall1 Fallanalyse ist O(f(n)) "- Bedeutung - es skaliert" ähnlich "(oder formal nicht schlechter als) die Funktion f(n).

Warum kümmern wir uns um die asymptotische Bindung eines Algorithmus?

Nun, es gibt viele Gründe dafür, aber ich glaube, die wichtigsten sind:

  1. Es ist viel schwieriger, die exakte Komplexitätsfunktion zu bestimmen, daher "kompromittieren" wir bei den Big-O/Big-Theta-Notationen, die theoretisch informativ genug sind.
  2. Die genaue Anzahl der Operationen ist ebenfalls plattformabhängig . Zum Beispiel, wenn wir einen Vektor (Liste) von 16 Zahlen haben. Wie viel Arbeit wird es dauern? Die Antwort lautet: es kommt darauf an. Einige CPUs erlauben Vektoradditionen, andere nicht. Die Antwort variiert zwischen verschiedenen Implementierungen und verschiedenen Maschinen, was eine unerwünschte Eigenschaft ist. Die Big-O-Notation ist jedoch zwischen Maschinen und Implementierungen viel konstanter.

Sehen Sie sich die folgenden Grafiken an, um dieses Problem zu veranschaulichen: enter image description here

Es ist klar, dass f(n) = 2*n "schlechter" ist als f(n) = n. Der Unterschied ist jedoch nicht ganz so drastisch wie bei der anderen Funktion. Wir können sehen, dass f(n)=logn schnell viel niedriger wird als die anderen Funktionen, und f(n) = n^2 wird schnell viel höher als die anderen.
Aus den oben genannten Gründen "ignorieren" wir die konstanten Faktoren (2 * im Diagrammbeispiel) und nehmen nur die Big-O-Notation.

Im obigen Beispiel befindet sich f(n)=n, f(n)=2*n sowohl in O(n) als auch in Omega(n) - und damit auch in Theta(n).
Andererseits - wird f(n)=logn in O(n) sein (es ist "besser" als f(n)=n), wird aber NICHT in Omega(n) sein - und wird somit auch NICHT in Theta(n) sein.
Symetrisch wird f(n)=n^2 in Omega(n) sein, aber NICHT in O(n), und somit ist - auch NOT Theta(n).


1Normalerweise, aber nicht immer. Wenn die Analyseklasse (schlechtester, durchschnittlicher und bester) fehlt, meinen wir wirklich den schlechtesten Fall.

312
amit

Theta (n): Eine Funktion f(n) gehört zu Theta(g(n)), wenn positive Konstanten c1 und c2 vorhanden sind, so dass f(n) zwischen c1(g(n)) und c2(g(n)) eingefügt werden kann. Das heißt, es gibt sowohl obere als auch untere Schranken.

Theta (g (n)) = {f(n): Es gibt positive Konstanten c1, c2 und n1, so dass 0 <= c1 (g (n)) <= f (n) <= c2 (g (n)) für alle n> = n1}

wenn wir f(n)=c2(g(n)) oder f(n)=c1(g(n)) sagen, bedeutet dies eine asymptotisch enge Bindung.

O (n): Es gibt nur eine obere Schranke (kann oder darf nicht eng sein)

O(g(n)) = {f(n): Es gibt positive Konstanten c und n1, so dass 0 <= f (n) <= cg (n) für alle n> gilt = n1}

ex: Die gebundene 2*(n^2) = O(n^2) ist asymptotisch eng, während die gebundene 2*n = O(n^2) nicht asymptotisch dicht ist.

o (n): Es gibt nur obere Schranke (niemals eine enge Schranke)

der bemerkenswerte Unterschied zwischen O(n) und o(n) ist f(n) kleiner als cg (n) für alle n> = n1, aber nicht gleich wie in O (n).

ex: 2*n = o(n^2), aber 2*(n^2) != o(n^2)

13
ThisIzKp

Ich hoffe, das ist es, was Sie in der klassischen CLRS (Seite 66) finden möchten:  enter image description here 

1
Lerner Zhang

Big Theta-Notation:

Nichts um den Kumpel zu versauen !!

Wenn wir einen positiven Wert haben, nehmen die Funktionen f(n) und g(n) ein positives Argument n an, dann gilt ϴ (g (n)), definiert als {f (n): Es gibt Konstanten c1 , c2 und n1 für alle n> = n1}

wobei c1 g (n) <= f (n) <= c2 g (n)

Nehmen wir ein Beispiel:

sei f (n) =  

g (n) =  

c1 = 5 und c2 = 8 und n1 = 1

Unter allen Notationen gibt ϴ die beste Intuition über die Wachstumsrate der Funktion an, weil sie uns eine enge Grenze gibt, im Gegensatz zu big-oh und big-ω, die die obere bzw. die untere Grenze angibt.

ϴ sagt uns, dass g(n) so nahe wie f (n) ist, die Wachstumsrate von g(n) liegt so nahe an der Wachstumsrate von f(n) wie möglich.

 see the image to get a better intuition