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

Question

Ich kenne die Definitionen von beiden, aber was ist der Grund, warum ich manchmal O (1) und andere Male Θ (1) in Lehrbüchern geschrieben sehe?

Danke.

Answer 1

Die Big-O-Notation drückt eine asymptotische Obergrenze aus, während die Big-Theta-Notation zusätzlich eine asymptotische Untergrenze ausdrückt. Oft interessiert die Leute an der Obergrenze, also schreiben sie O (etwas), selbst wenn Theta (etwas) auch wahr wäre. Wenn Sie z. B. die Anzahl der Dinge, die in einer unsortierten Liste gleich x sind, zählen möchten, können Sie sagen, dass dies in linearer Zeit geschehen kann und O (n) ist, denn was Ihnen wichtig ist, ist, dass es gewonnen hat. Es dauert nicht länger. Es ist jedoch auch wahr, dass es Omega (n) und daher Theta (n) ist, da Sie alle Elemente in der Liste untersuchen müssen - es kann nicht in sublinearer Zeit durchgeführt werden.

Answer 2

O (1) und Θ (1) sind nicht unbedingt identisch, wenn Sie Funktionen über reelle Zahlen sprechen. Betrachten Sie zum Beispiel die Funktion f (n) = 1/n. Diese Funktion ist O (1), weil für jedes n ≥ 1, f (n) ≤ 1. Es ist jedoch nicht Θ (1) aus dem folgenden Grund: eine Definition von f (n) = Θ (g (n)) ist das die Grenze von | f (n)/g (n) | Wenn n in die Unendlichkeit geht, ist ein endlicher Wert L, der 0 < L erfüllt. Wenn f (n) = 1/n und g (n) = 1 eingegeben werden, nehmen wir die Grenze von | 1/n | wenn n in die Unendlichkeit geht und es wird 0 sein. Daher gilt f (n) ≠ Θ (1).

Hoffe, das hilft!