Was ist der Unterschied zwischen unterer Grenze und enger Grenze?

Question

Mit dem Hinweis darauf Antwort, was ist Theta (fest gebunden)?

Omega ist eine Untergrenze, also die minimale Zeit, die ein Algorithmus benötigen darf.Und wir wissen, dass Big-O für die Obergrenze steht, also die maximale Zeit, die ein Algorithmus benötigen darf.Aber ich habe keine Ahnung, was Theta angeht.

Answer 1

Big O ist die Obergrenze, während Omega ist die Untergrenze. Theta erfordert sowohl Big O als auch Omega, daher wird es als a bezeichnet fest gebunden (Es muss sowohl die Ober- als auch die Untergrenze sein).

Zum Beispiel ein Algorithmus Omega(n log n) dauert mindestens n log n Zeit, hat aber keine Obergrenze.Ein Algorithmus übernimmt Theta(n log n) ist weitaus vorteilhafter, da es dauert mindestens n log n (Omega n log n) und nicht mehr als n log n (Großes O n log n).

Answer 2

Θ-Notation (Theta-Notation) genannt wird eng gebunden, weil es präziser als O-Notation und Ω-Notation (Omega Notation).

Wenn ich faul wäre, könnte ich sagen, dass binäre Suche auf einem sortierten Array ist O (n ² ), O (n ³ ) und O (2 < sup> n ), und ich würde in jedem Fall technisch korrekt sein. Das ist, weil O-Notation nur eine gibt Obergrenze und binäre Suche wird durch all diese Funktionen auf der hohen Seite begrenzt, nur nicht sehr eng. Diese faulen Schätzungen wären nutzlos .

Θ-Notation löst dieses Problem, indem sie Kombinieren O-Notation und Ω-Notation. Wenn ich sage, dass binäre Suche ist Θ (log n), das gibt Ihnen genauere Informationen. Es sagt Ihnen, dass der Algorithmus auf begrenzt ist beide Seiten durch die gegebene Funktion, so wird es nie wesentlich schneller oder langsamer sein als angegeben.

Answer 3

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

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

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

Wikipedia-Artikel ist in Ordnung, wenn auch ein wenig dicht.

Answer 4

Asymptotic obere Schranke bedeutet, dass ein bestimmte Algorithmus während der maximalen Zeitdauer ausgeführt wird, in Abhängigkeit von der Anzahl der Eingänge.

Nehmen wir einen Sortieralgorithmus als Beispiel. Wenn alle Elemente eines Arrays sind in absteigender Reihenfolge, dann sie zu sortieren, es wird eine Laufzeit von O(n) nehmen, obere Schranke Komplexität zeigt. Wenn das Array bereits sortiert ist, wird der Wert O(1).

Im Allgemeinen O-notation ist für die obere Grenze Komplexität verwendet.

---

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

Answer 5

Die Sätze Mindestzeit und maximale Zeit sind ein bisschen hier irreführend. Wenn wir über große O-Notationen zu sprechen, es ist nicht die tatsächliche Zeit, die wir interessiert sind, ist es, wie die Zeit erhöht, wenn unsere Eingangsgröße größer wird. Und es ist in der Regel die durchschnittliche oder schlimmsten Fall, wenn wir reden, nicht best case , die in der Regel nicht sinnvoll ist, unsere Probleme zu lösen.

Mit der Array-Suche in der akzeptierte Antwort auf die andere Frage als Beispiel. Die Zeit, die eine bestimmte Anzahl in der Liste der Größe n zu finden nimmt, ist n / 2 * some_constant im Durchschnitt. Wenn Sie es als eine Funktion f(n) = n/2*some_constant behandeln, erhöht es nicht schneller als g(n) = n, in dem Sinne, wie von Charlie gegeben. Außerdem erhöht es nicht langsamer als g(n) entweder. Daher ist g(n) beide tatsächlich eine obere Grenze und eine untere Grenze von f(n) in Big-O-Notation, so dass die Komplexität der linearen Suche ist genau n , was bedeutet, dass es Theta (n).

In dieser Hinsicht ist die Erklärung in der akzeptierte Antwort auf die andere Frage ist nicht ganz korrekt, die behauptet, dass O (n) obere Grenze, da der Algorithmus in konstanter Zeit für einige Eingaben ausgeführt werden kann (dies ist die best case ich oben erwähnt habe, was nicht wirklich das, was wir über die Laufzeit wissen wollen).

Answer 6

  

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

Wir können o-Notation ( „little-oh“) zu bezeichnen, eine obere Schranke verwenden, die nicht asymptotisch dicht ist. Beide big-oh und wenig oh sind ähnlich. Aber, Big-oh ist wahrscheinlich asymptotisch fest obere Grenze zu definieren.

Answer 7

Gerade die untere Schranke oder $ \ omega $ bfon f (n) die Gesamtheit von Funktionen, die sich asymptotisch weniger oder gleich f (n) U d.h      g (n) ≤ cf (n) $ \ für alle $ `un≥ n‘ Für einige c, n‘$ \ in $ $ \ Bbb {N} $

Und die obere Grenze oder $ \ mathit {O} $ auf f (n) bedeutet den Satz von Funktionen, die assymptotically größer oder gleich f (n), die mathematisch sagt,

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

Nun ist die $ \ Theta $ ist der Schnittpunkt der oben geschrieben zwei

  

$\theta $

Wie, wenn ein Algorithmus ist wie "genau \ $ Omega \ (f links (n) \ right $", dann ist es besser zu sagen, dass es $ \ Theta \ ist links (f (n) \ right) $.

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

Answer 8

Der grundlegende Unterschied zwischen

  

Blockquote

asymptotisch obere Schranke und asymptotisch fest Asym.upperbound bedeutet eine gegebene algorythm, die mit maximalem Zeitbetrag von der Anzahl der Eingänge in Abhängigkeit ausführen, können, zum Beispiel bei der Sortierung Algo wenn alle Array (n) Elemente in absteigender Reihenfolge werden diese dann für aufsteigendes es eine Laufzeit stattfinden O (n), die obere Grenze der Komplexität zeigt, aber wenn sie bereits sortiert sind, dann wird es dauern, Ohm (1) .so wir „O“ Notation für obere Schranke Komplexität verwendet.

Asym. tightbound gebundenen zeigt die für eg (C1G (n) <= f (n) <= c2g (n)) die enge gebunden begrenzen, zeigt, dass die Funktion den Wert zwischen zwei gebunden hat (obere Grenze und untere Grenze), was die durchschnittlicher Fall.