Ω-Symbol (Omega)

Manchmal möchten wit etwas über die Mindestlaufzeit eines Algorithmus aussagen, also die Zeit, die er mindestens zur Ausführung benötigt, ohne dabei über eine Obergrenze zu sprechen. Wir verwenden dazu die big-Ω Notation. Das ist der griechische Buchstabe "Omega".

Wenn eine Laufzeit $\mathrm{\Omega }(f(n))$‍ ist, dann beträgt für hinreichend große $n$‍ die Laufzeit mindestens $k\cdot f(n)$‍ für eine Konstante $k$‍. Man kann sich eine $\mathrm{\Omega }(f(n))$‍ Laufzeit folgendermaßen vorstellen:

Wir sagen, dass die Laufzeit "Big-Ω von $f(n)$‍" ist. " Wir verwenden eine Big-Ω-Notation für asymptotische Untergrenzen , da sie das Wachstum der Laufzeit von unten für ausreichend große Eingangsgrößen begrenzt.

So wie $\mathrm{\Theta }(f(n))$‍ automatisch $O(f(n))$‍ impliziert, impliziert es auch automatisch $\mathrm{\Omega }(f(n))$‍. Wir können also sagen, dass die Worst-Case-Laufzeit der binären Suche $\mathrm{\Omega }({\log }_{2}n)$‍ ist.

Wir können auch korrekte, aber ungenaue Aussagen mit der big-Ω-Notation machen. Wenn du zum Beispiel wirklich eine Million Euro in deiner Tasche hast, kannst du wahrheitsgemäß sagen: "Ich habe einen Geldbetrag in meiner Tasche, und es sind mindestens 10 Euro." Das ist korrekt, aber sicherlich nicht sehr präzise. Ähnlich können wir korrekt, aber ungenau sagen, dass die Worst-Case-Laufzeit der binären Suche $\mathrm{\Omega }(1)$‍ ist, weil wir wissen, dass sie mindestens konstante Zeit braucht.

Natürlich versuchen wir, wenn wir über Algorithmen sprechen, deren Laufzeit so genau wie möglich zu beschreiben. Wir geben hier die Beispiele für die ungenauen Aussagen, damit du big-$\mathrm{\Omega }$‍, big-$O$‍ und big-$\mathrm{\Theta }$‍ besser verstehen kannst.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.