Was ist der Unterschied zwischen Θ(n) und O(n)?

https://stackoverflow.com/questions/471199

19-08-2019
|

Frage

Manchmal sehe ich Θ(n) mit dem seltsamen Θ-Symbol und etwas in der Mitte, und manchmal nur O(n).Ist es nur Schreibfaulheit, weil niemand weiß, wie man dieses Symbol eintippt, oder bedeutet es etwas anderes?

Lösung

Kurze Erläuterung:

Wenn ein Algorithmus von Θ (g (n)) ist, bedeutet dies, dass die Laufzeit des Algorithmus als n (Eingangsgröße) größer wird, ist proportional zu g (n).

Wenn ein Algorithmus von O (g (n)), bedeutet dies, dass die Laufzeit des Algorithmus, wie n größer wird ist höchstens proportional zu g (n).

Normalerweise, auch wenn die Leute über O (g (n)) sprechen sie tatsächlich bedeuten, Θ (g (n)), aber technisch gesehen, gibt es einen Unterschied.

Technisch:

O (n) repräsentiert obere Schranke. Θ (n) bedeutet und fest gebunden. Ω (n) stellt untere Schranke.

f (x) = Θ (g (x)) genau dann, wenn f (x) =     O (g (x)) und f (x) = Ω (g (x))

Im Grunde genommen, wenn wir sagen, ein Algorithmus von O (n) ist, ist es auch O (n ²), O (n ^1000000), O (2 ⁿ), ... aber ein Θ (n) Algorithmus ist nicht Θ (n ²).

In der Tat, da f (n) = Θ (g (n)) für hinreichend große Werte von n bedeutet, kann f (n) innerhalb von c gebunden ₁ g (n) und c ₂ g (n) für einige Werte von C ₁ und C ₂, dh, die Wachstumsrate von f zu g asymptotisch gleich ist: g-Dose sein eine untere Schranke und und eine obere Grenze von f. Diese direkt impliziert f kann eine untere Grenze und eine obere Grenze von g als gut. Folglich

f (x) = Θ (g (x)) genau dann, wenn g (x) = Θ (f (x))

Ähnlich zeigen f (n) = Θ (g (n)), es reicht g zu zeigen ist eine obere Grenze von F (dh f (n) = O (g (n))) und f ein gebunden von g (dh f (n) = Ω (g (n)), die genau den gleichen wie g (n) = O (f (n)) ist) niedriger. Prägnant,

f (x) = Θ (g (x)) genau dann, wenn f (x) = O (g (x)) und g (x) = O (f (x))

Es gibt auch wenig oh und wenig Omega (ω) Notationen lose obere und lose untere Grenze eine Funktion darstellen.

Um es zusammenzufassen:

f(x) = O(g(x)) (big-oh) bedeutet, dass   die Wachstumsrate von f(x) ist   asymptotisch kleiner oder gleich   zu , um die Wachstumsrate von g(x).

f(x) = Ω(g(x)) (big-omega) Mittel   dass die Wachstumsrate von f(x) ist   asymptotisch größer oder   gleich die Wachstumsrate der g(x)

f(x) = o(g(x)) (little-oh) bedeutet, dass   die Wachstumsrate von f(x) ist   asymptotisch kleine die   Wachstumsrate von g(x).

f(x) = ω(g(x)) (little-omega) Mittel   dass die Wachstumsrate von f(x) ist   asymptotisch größer als die   Wachstumsrate von g(x)

f(x) = Θ(g(x)) (theta) bedeutet, dass   die Wachstumsrate von f(x) ist   asymptotisch gleich die   Wachstumsrate von g(x)

Für eine ausführlichere Diskussion Sie href="http://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer"> lesen oder ein klassisches Lehrbuch konsultieren wie Introduction to Algorithms von Cormen et al.

Andere Tipps

Es gibt einen einfachen Weg (einen Trick, ich denke) zu erinnern, welche Notation bedeutet, was.

Alle der Big-O-Notationen können eine Bar haben, in Betracht gezogen werden.

Wenn bei einem Ω suchen, ist die Leiste am unteren Rand, so ist es eine (asymptotisch) untere Schranke.

Wenn bei einem Θ suchen, die Bar ist offensichtlich in der Mitte. Es ist also ein (asymptotisch) fest gebunden.

Wenn O Handschrift, Sie in der Regel an der Spitze zu beenden, und einen Kringel ziehen. Daher O (n) ist die obere der Funktion gebunden. Um fair zu sein, ist dieser nicht mit den meisten Schriftarten arbeiten, aber es ist die ursprüngliche Rechtfertigung der Namen.

einer ist Big „O“

einer ist Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

Großes O bedeutet, dass Ihr Algorithmus in nicht mehr Schritten als im angegebenen Ausdruck (n^2) ausgeführt wird.

Big Omega bedeutet, dass Ihr Algorithmus in nicht weniger Schritten ausgeführt wird als im angegebenen Ausdruck (n^2).

Wenn beide Bedingungen für denselben Ausdruck wahr sind, können Sie die Big-Theta-Notation verwenden....

Anstatt eine theoretische Definition zu liefern, die hier schon schön zusammengefasst ist, werde ich ein einfaches Beispiel:

Angenommen, die Laufzeit von f(i) ist O(1). Unten ist ein Codefragment, dessen asymptotische Laufzeit ist Θ(n). Es immer ruft die Funktion f(...) n mal. Sowohl die untere und die obere Grenze n.

for(int i=0; i<n; i++){
    f(i);
}

Das zweite Code-Fragment hat die asymptotische Laufzeit von O(n). Es ruft die Funktion f(...) höchstens n mal. Die obere Grenze ist n, aber die untere Grenze Ω(1) oder Ω(log(n)) werden könnte, je nachdem, was in f2(i) passiert.

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Theta ist eine Abkürzung auf eine Sonderregelung Situtation zu verweisen, wo der große O und Omega sind die gleichen.

Wenn man also The Theta is expression q behauptet, dann sind sie auch unbedingt behaupten, dass Big O is expression q und Omega is expression q.

Raute Analogie:

If: Theta behauptet: „Das Tier 5 Beine hat.“ dann folgt daraus, dass: Big O ist wahr ( „Das Tier weniger als oder gleich 5 Beinen.“) und Omega ist wahr ( „Das Tier hat mehr als oder gleich 5 Beine“).

Es ist nur eine grobe Analogie, weil die Ausdrücke sind nicht notwendigerweise bestimmte Zahlen, sondern Funktionen von Größenordnungen variiert wie log (n), n, n ^ 2, (usw.).

Diagramm könnte die bisherigen Antworten erleichtern zu verstehen:

Θ-Notation - gleiche Reihenfolge | O-Notation - Obere Grenze

T (n) - gleiche Reihenfolge

In Englisch,

Auf der linken Seite ist zu beachten, dass es eine obere Grenze und eine untere Grenze, dass beide der gleichen Größenordnung sind (d g (n) ). Ignorieren Sie die Konstanten, und wenn die obere Grenze und untere Grenze hat die gleiche Größenordnung, kann man gültig sagen f (n) = Θ (g (n)) oder f (n) ist in großen Theta von g (n) .

mit dem rechten Ab dem einfacheren Beispiel, es sagt die obere Grenze g (n) ist einfach die Größenordnung und ignoriert die Konstante c (wie alle big O Notation der Fall ist).

f(n) gehört zu O(n) wenn positive k als f(n)<=k*n existiert

f(n) gehört Θ(n) falls vorhanden positive k1, k2 als k1*n<=f(n)<=k2*n

Wikipedia-Artikel über Big O Notation

Fazit: Wir sehen großes O, großen θ und großen Ω als die gleiche Sache.

Warum? Ich werde sagen, den Grund unter:

Zum einen werde ich eine falsche Aussage klären, einige Leute denken, dass wir die schlimmste Zeit Komplexität nur kümmern, also verwenden wir immer große O statt großer θ. Ich werde sagen, dieser Mann ist Blödsinn. Obere und untere Grenze werden verwendet, um eine Funktion zu beschreiben, die Zeitkomplexität nicht zu beschreiben. Die schlimmste Zeit Funktion hat seine obere und untere Grenze; die beste Zeit Funktion seiner oberen hat und auch untere Schranke.

Um klar die Beziehung zwischen großen OS und großen θ zu erklären, werde ich die Beziehung zwischen großen OS und kleinen o zunächst erklären. Aus der Definition können wir leicht erkennen, dass kleines o eine Teilmenge von großem O. Zum Beispiel ist:

T (n) = n ^ 2 + n, wir können sagen, T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Aber für kleines o, T (n) = O (n ^ 2) nicht die Definition des kleinen os erfüllen. Also nur T (n) = O (n ^ 3), T (n) = o (n ^ 4) korrekt sind für kleines o. Die redundante T (n) = O (n ^ 2) ist, und? Es ist groß θ!

Im Allgemeinen wir sagen, großes O ist O (n ^ 2), kaum zu sagen, T (n) = O (n ^ 3), T (n) = O (n ^ 4). Warum? Weil wir großes O so groß betrachten θ unbewusst.

Ebenso sehen wir auch große Ω so groß θ unbewusst.

In einem Wort, großes O, große θ und große Ω sind nicht das Gleiche von den Definitionen, aber sie sind die gleiche Sache in unserem Mund und Gehirn.

Mit Grenzen

Lassen Sie uns f(n) > 0 und g(n) > 0 für alle n betrachten. Es ist in Ordnung, dies zu betrachten, weil der schnellste Real Algorithmus mindestens eine Operation hat und beendet seine Ausführung nach dem Start. Dadurch wird das Kalkül vereinfachen, weil wir den Wert (f(n)) anstelle des Absolutwert (|f(n)|) verwenden können.

`f(n) = O(g(n))`

Allgemein:

          f(n)     
0 ≤ lim ──────── < ∞
    n➜∞   g(n)

Für g(n) = n:

          f(n)     
0 ≤ lim ──────── < ∞
    n➜∞    n

Beispiele:

    Expression               Value of the limit
------------------------------------------------
n        = O(n)                      1
1/2*n    = O(n)                     1/2
2*n      = O(n)                      2
n+log(n) = O(n)                      1
n        = O(n*log(n))               0
n        = O(n²)                     0
n        = O(nⁿ)                     0

Gegenbeispiele:

    Expression                Value of the limit
-------------------------------------------------
n        ≠ O(log(n))                 ∞
1/2*n    ≠ O(sqrt(n))                ∞
2*n      ≠ O(1)                      ∞
n+log(n) ≠ O(log(n))                 ∞

`f(n) = Θ(g(n))`

Allgemein:

          f(n)     
0 < lim ──────── < ∞
    n➜∞   g(n)

Für g(n) = n:

          f(n)     
0 < lim ──────── < ∞
    n➜∞    n

Beispiele:

    Expression               Value of the limit
------------------------------------------------
n        = Θ(n)                      1
1/2*n    = Θ(n)                     1/2
2*n      = Θ(n)                      2
n+log(n) = Θ(n)                      1

Gegenbeispiele:

    Expression                Value of the limit
-------------------------------------------------
n        ≠ Θ(log(n))                 ∞
1/2*n    ≠ Θ(sqrt(n))                ∞
2*n      ≠ Θ(1)                      ∞
n+log(n) ≠ Θ(log(n))                 ∞
n        ≠ Θ(n*log(n))               0
n        ≠ Θ(n²)                     0
n        ≠ Θ(nⁿ)                     0

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow