Was ist der Unterschied zwischen Untergrenze und Festgrenze?

Was ist Theta (eng gebunden) unter Bezugnahme auf diese Antwort ?

Omega ist die untere Grenze, ganz verstanden, die minimale Zeit, die ein Algorithmus benötigen kann. Und wir wissen, dass Big-O für die Obergrenze steht, dh die maximale Zeit, die ein Algorithmus benötigen kann. Aber ich habe keine Ahnung von der Theta.

Big O ist die Obergrenze, während Omega die Untergrenze ist. Theta benötigt sowohl Big O als auch Omega, daher wird es als enge Grenze bezeichnet (es muss sowohl die obere als auch die untere Grenze sein).

Zum Beispiel Omega(n log n)dauert ein Algorithmus mindestens einige n log nZeit, hat aber keine Obergrenze. Eine Algorithmusaufnahme Theta(n log n)ist weitaus bevorzugt, da sie mindestens n log n (Omega n log n) und nicht mehr als n log n (Big n log n) benötigt.

Die Θ-Notation (Theta-Notation) wird als eng gebunden bezeichnet, da sie genauer ist als die O-Notation und die Ω-Notation (Omega-Notation).

Wenn ich faul wäre, könnte ich sagen, dass die binäre Suche in einem sortierten Array O (n ² ), O (n ³ ) und O (2 ⁿ ) ist, und ich wäre in jedem Fall technisch korrekt. Das liegt daran, dass die O-Notation nur eine Obergrenze angibt und die binäre Suche auf der oberen Seite von all diesen Funktionen begrenzt wird, nur nicht sehr genau. Diese faulen Schätzungen wären nutzlos .

Die Θ-Notation löst dieses Problem, indem sie die O-Notation und die Ω-Notation kombiniert . Wenn ich sage, dass die binäre Suche Θ (log n) ist, erhalten Sie genauere Informationen. Es zeigt Ihnen, dass der Algorithmus auf beiden Seiten durch die angegebene Funktion begrenzt ist, sodass er niemals wesentlich schneller oder langsamer als angegeben sein wird.

Wenn Sie etwas haben, das O (f (n)) ist , bedeutet dies, dass es k , g (n) gibt, so dass f (n) ≤ kg (n) ist .

Wenn Sie etwas haben, das Ω (f (n)) ist , bedeutet dies, dass es k , g (n) gibt, so dass f (n) ≥ kg (n) ist .

Und wenn Sie etwas mit O (f (n)) und Ω (f (n)) haben , dann ist es Θ (f (n) .

Der Wikipedia-Artikel ist anständig, wenn auch etwas dicht.

Asymptotische Obergrenze bedeutet, dass ein bestimmter Algorithmus abhängig von der Anzahl der Eingaben während der maximalen Zeit ausgeführt wird.

Nehmen wir als Beispiel einen Sortieralgorithmus. Wenn alle Elemente eines Arrays in absteigender Reihenfolge vorliegen, dauert das Sortieren eine Laufzeit von O(n)und zeigt die Komplexität der Obergrenze. Wenn das Array bereits sortiert ist, lautet der Wert O(1).

Im Allgemeinen O-notationwird für die Komplexität der oberen Grenze verwendet.

Asymptotisch eng gebunden (c ₁ g (n) ≤ f (n) ≤ c ₂ g (n)) zeigt die durchschnittliche gebundene Komplexität für eine Funktion mit einem Wert zwischen gebundenen Grenzen (obere Grenze und untere Grenze), wobei c ₁ und c ₂ sind Konstanten.

Die Sätze minimale Zeit und maximale Zeit sind hier etwas irreführend. Wenn wir über große O-Notationen sprechen, ist es nicht die tatsächliche Zeit, an der wir interessiert sind, sondern wie sich die Zeit erhöht, wenn unsere Eingabegröße größer wird. Und es ist normalerweise die durchschnittliche oder schlechteste Zeit, über die wir sprechen, nicht der beste Fall , was normalerweise für die Lösung unserer Probleme nicht sinnvoll ist.

Verwenden Sie die Arraysuche in der akzeptierten Antwort auf die andere Frage als Beispiel. Die Zeit, die benötigt wird, um eine bestimmte Zahl in der Liste der Größe n zu finden, beträgt im Durchschnitt n / 2 * some_constant. Wenn Sie es als Funktion behandeln f(n) = n/2*some_constant, steigt es nicht schneller an als g(n) = nim Sinne von Charlie. Außerdem steigt es nicht langsamer als g(n)beide. Daher g(n)ist tatsächlich sowohl eine Obergrenze als auch eine Untergrenze von f(n)in der Big-O-Notation, so dass die Komplexität der linearen Suche genau n ist , was bedeutet, dass es Theta (n) ist.

In dieser Hinsicht ist die Erklärung in der akzeptierten Antwort auf die andere Frage nicht ganz richtig, was besagt, dass O (n) die Obergrenze ist, da der Algorithmus für einige Eingaben in konstanter Zeit ausgeführt werden kann (dies ist der beste Fall, den ich oben erwähnt habe). Das ist nicht wirklich das, was wir über die Laufzeit wissen wollen.

Wenn ich faul wäre, könnte ich sagen, dass die binäre Suche in einem sortierten Array O (n2), O (n3) und O (2n) ist, und ich wäre in jedem Fall technisch korrekt.

Wir können die O-Notation ("little-oh") verwenden, um eine Obergrenze zu bezeichnen, die nicht asymptotisch eng ist. Sowohl Big-Oh als auch Little-Oh sind ähnlich. Aber Big-Oh wird wahrscheinlich verwendet, um eine asymptotisch enge Obergrenze zu definieren.

Genau die Untergrenze oder $ \ omega $ bfon f (n) bedeutet die Menge von Funktionen, die asymptotisch kleiner oder gleich f (n) sind, dh U g (n) ≤ cf (n) $ \ für alle $ `un≥ n 'Für einige c, n' $ \ in $ $ \ Bbb {N} $

Und die Obergrenze oder $ \ mathit {O} $ für f (n) bedeutet die Menge von Funktionen, die assymptotisch größer oder gleich f (n) sind, was mathematisch sagt,

$ g (n) \ ge cf (n) \ für alle n \ ge n '$, für einige c, n' $ \ in $ $ \ Bbb {N} $.

Jetzt ist das $ \ Theta $ der Schnittpunkt der oben geschriebenen zwei

$\theta $

Wenn ein Algorithmus wie "genau $ \ Omega \ left (f (n) \ right $" ist, ist es besser zu sagen, dass es $ \ Theta \ left (f (n) \ right) $ ist.

Oder wir können auch sagen, dass es uns die tatsächliche Geschwindigkeit $ \omega $gibt, wo es uns die niedrigste Grenze gibt.

Der grundlegende Unterschied zwischen

Blockquote

asymptotisch obergrenze und asymptotisch eng Asym.upperbound bedeutet einen gegebenen Algorithmus, der abhängig von der Anzahl der Eingaben mit maximaler Zeit ausgeführt werden kann, z. B. beim Sortieren von Algo, wenn alle Array (n) -Elemente in absteigender Reihenfolge sind, und dann zum Aufsteigen dauert eine Laufzeit von O (n), die die Komplexität der Obergrenze zeigt, aber wenn sie bereits sortiert sind, dauert es Ohm (1). Daher haben wir im Allgemeinen die "O" -Notation für die Komplexität der Obergrenze verwendet.

Asym. eng gebundene Grenze zeigt die für zB (c1g (n) <= f (n) <= c2g (n)) zeigt die eng gebundene Grenze, so dass die Funktion den Wert zwischen zwei Grenzen hat (obere Grenze und untere Grenze), was die ergibt durchschnittlicher Fall.