Könnte jemand Big O gegen Big Omega gegen Big Theta erklären?

Question

Mögliche Duplizieren:
Big Theta Notation - what exactly does big Theta represent?

ich es in der Theorie verstehen, glaube ich, aber was ich habe Probleme beim Greifen ist die Anwendung der drei.

In der Schule verwendeten wir immer Big O, um die Komplexität eines Algorithmus zu bezeichnen. Blasensortierung war beispielsweise O (n^2).

Jetzt nach dem Lesen mehr Theorie, dass Big Oh ist nicht die einzige Maßnahme, gibt es mindestens zwei andere interessante.

Aber hier ist meine Frage:

Big O ist die obere gebunden, Big Omega die untere Grenze ist, und Big Theta ist eine Mischung aus beiden. Aber was bedeutet das konzeptionell? Ich verstehe, was es auf einer Grafik bedeutet; Ich habe eine Million Beispiele dafür gesehen. Aber was bedeutet es für die Komplexität des Algorithmus? Wie mischt sich eine "obere Grenze" oder eine "untere Grenze" damit?

Ich denke, ich bekomme einfach nicht seine Anwendung. Ich verstehe, dass, wenn sie mit einer Konstanten c multipliziert werden, wenn f nach einem Wert n_0 f (x) größer als g (x) ist, f (x) als O (g (x)) betrachtet wird. Aber was bedeutet das praktisch? Warum würden wir f (x) mit einem Wert c multiplizieren? Hölle, ich dachte mit Big O Notation Multiples war egal.

Answer 1

Die große O-Notation und ihre Verwandten, das große Theta, das große Omega, das kleine O und das kleine Omega sind Möglichkeiten, etwas darüber zu sagen, wie sich eine Funktion an einem Grenzpunkt verhält (z. aber auch bei Annäherung an 0 usw.) ohne viel mehr über die Funktion zu sagen. Sie werden häufig verwendet, um den Laufraum und die Zeit von Algorithmen zu beschreiben, aber sie können auch in anderen Bereichen der Mathematik in Bezug auf asymptotisches Verhalten gesehen werden.

Die halb intuitive Definition ist wie folgt:

eine Funktion g (x) wobei O (f (x)) Wenn "auf von einem Punkt" sein, g (x) niedriger als c * f (x), wobei c eine Konstante ist.

Die anderen Definitionen sind ähnlich, Theta fordern, dass g (x) zwischen zwei konstanten Vielfachen von f (x), Omega fordern g (x)> c * f (x), und die kleinen Versionen verlangen, dass dies ist gilt für alle diese Konstanten.

Aber warum ist es interessant zu sagen, dass zum Beispiel ein Algorithmus eine Laufzeit von O (n^2) hat?

Es ist vor allem interessant, weil wir uns in der theoretischen Informatik am meisten dafür interessieren, wie sich Algorithmen für große Eingaben verhalten. Dies ist der Fall, da die Laufzeiten von Algorithmen bei kleinen Eingaben je nach Implementierung, Kompilierung, Hardware und anderen Dingen, die bei der theoretischen Analyse eines Algorithmus nicht wirklich interessant sind, stark variieren können.

Die Wachstumsrate hängt jedoch normalerweise von der Art des Algorithmus ab, und um sie zu verbessern, benötigen Sie tiefere Einblicke in das Problem, das Sie zu lösen versuchen. Dies ist beispielsweise bei Sortieralgorithmen der Fall, wo Sie einen einfachen Algorithmus (Bubble Sort) für die Ausführung in O (n^2) erhalten können. Um dies jedoch zu O (n log n) zu verbessern, benötigen Sie eine wirklich neue Idee wie das in Merge Sort oder Heap Sort eingegebene.

Auf der anderen Seite, wenn Sie einen Algorithmus haben, der in genau 5n Sekunden läuft, und einen anderen, der in 1000n Sekunden läuft (was beispielsweise der Unterschied zwischen einem langen Gähnen und einer Startunterbrechung für n = 3 ist), Wenn Sie zu n = 1000000000000 kommen, scheint der Größenunterschied weniger wichtig zu sein. Wenn Sie einen Algorithmus haben, der O (log n) benötigt, müssten Sie jedoch log (1000000000000) = 12 Sekunden warten, vielleicht multipliziert mit einer Konstante, anstatt der fast 317.098 Jahre, egal wie groß die Konstante ist ist, ist eine ganz andere Skala.

Ich hoffe, dass dies die Dinge ein wenig klarer macht. Viel Glück mit Ihrem Studium!