Landau-Notation: O, Omega und Theta einfach erklärt

Landau-Symbole beschreiben, wie eine Funktion für sehr große Eingaben wächst. Man nennt das asymptotisches Verhalten. In der Informatik geben sie ein Maß für die Anzahl der Elementarschritte (einfache Rechenschritte) in Abhängigkeit von der Größe n des Problems an. Konstanten spielen dabei keine Rolle.

Es gibt drei Symbole. O ist die obere Schranke: f wächst höchstens genauso schnell wie g. Ω ist in der Komplexitätstheorie die untere Schranke: f wächst mindestens genauso schnell wie g. Θ ist die enge Schranke: f wächst genauso schnell wie g. Θ bedeutet beides zugleich: f liegt in O(g) und in Ω(g).

Genauer: f(n) = O(g(n)) bedeutet f(n) ≤ c·g(n) für alle n ≥ n₀ und ein c > 0. Bei Ω steht ≥ statt ≤. Bei Θ liegt f(n) ab einem n₀ zwischen zwei Vielfachen von g(n), mit zwei positiven Konstanten c₁ und c₂. Außerdem gilt in der Komplexitätstheorie: f ∈ Ω(g) genau dann, wenn g ∈ O(f).

Eine Hilfe ist der Quotient f(n)/g(n) für wachsendes n. Strebt er gegen einen Wert kleiner als unendlich, gilt f = O(g). Strebt er gegen einen Wert größer als 0, gilt f = Ω(g). Strebt er gegen eine Konstante c mit c > 0, wächst f genauso schnell wie g.

Vorsicht bei der Schreibweise: f = O(g) ist keine Gleichung, sondern nur symbolisch gemeint. O(g) ist eine Menge von Funktionen, deshalb ist f(n) ∈ O(g(n)) formal korrekt. Aus f₁ = O(g) und f₂ = O(g) folgt nicht, dass f₁ und f₂ gleich sind. Das Symbol Ω hat in der Zahlentheorie eine andere Definition; hier gilt die aus der Komplexitätstheorie.

Eine Kostenfunktion T(n) gibt hier die Anzahl der Datensatzvergleiche bei Problemgröße n an. Dabei interessiert nicht die Zeit eines Programms auf einem bestimmten Computer, sondern wie der Bedarf bei mehr Daten wächst. Meist sind große n wichtig, weil sich kleine Problemgrößen oft nur im Millisekundenbereich unterscheiden.

Zwei Regeln helfen. Additionsregel: Bei einer Summe zählt nur der größere Summand, O(f(n)+g(n)) wird zu O(max(f(n), g(n))). Konstantenregel: Ein konstanter Faktor c > 0 fällt weg, O(c·f(n)) wird zu O(f(n)). Beide Regeln gelten entsprechend für Θ. Der Summand, der übrig bleibt, ist der dominierende Term.

Welcher Summand am schnellsten wächst, siehst du an der Reihenfolge der Wachstumsprototypen: log(n) wächst langsamer als n, dieses langsamer als n·log(n), dann folgen n², n³ und so weiter. Die Basis des Logarithmus ist dabei egal.

Die Laufzeit hängt manchmal nicht nur von n ab, sondern auch davon, wie stark eine Liste bereits vorsortiert ist. Darum unterscheidet man drei Fälle. Best Case ist der Fall mit den wenigsten Kosten. Worst Case ist der Fall mit den meisten Kosten. Average Case ist eine Mittelung der Kosten über alle Fälle. Der Average Case ist für die Praxis meist am wichtigsten, aber schwer zu ermitteln. Der Worst Case ist meist der relevantere der beiden Extremfälle. Spricht man einfach von Zeitkomplexität, ist meistens der Worst Case gemeint.

Beispiel Suche: In einer Liste mit zwanzig Namen wird von vorn gesucht, bis der Name gefunden ist. Best Case: Die Suchzeit ist 1, wenn der Name der erste ist. Worst Case: Die Suchzeit ist 20, wenn der Name der letzte ist. Sie stellt sich auch ein, wenn der Name nicht in der Liste ist. Average Case: 10,5, wenn der Name definitiv in der Liste ist. Beim Quicksort sind es angenähert Tbest(n) = n·log₂(n) im günstigsten und Tworst(n) = n·(n−1)/2 im ungünstigsten Fall.

So analysierst du eine Schleife: Jede einfache Anweisung kostet O(1). Dass ein print mehr Ressourcen braucht als eine Zuweisung, wird in der Landau-Notation vernachlässigt. Läuft eine Schleife n-mal und steht im Rumpf eine feste Anzahl einfacher Anweisungen, multiplizierst du: O(f(n))·O(g(n)) wird zu O(f(n)·g(n)). Danach addierst du alle Teile und behältst nur den größten. Wichtig: n muss für die Größe der Eingabe stehen, zum Beispiel als Parameter. Ist n im Code fest auf 5 gesetzt, läuft die Schleife immer 5-mal, und der Aufwand ist konstant.

Fall und Schranke sind zwei verschiedene Fragen. Der Fall sagt, welche Eingabe du betrachtest. Das Symbol O, Ω oder Θ sagt, welche Art von Schranke du für die Kosten dieses Falls angibst. Das folgt aus den Definitionen oben. Weil man meist am Worst Case interessiert ist, gibt man dafür meist eine obere Schranke an. Das ist aber nur eine Gewohnheit: Auch für den Best Case des Insertionsort gibt man eine obere Schranke an, nämlich O(n).

Wachstum allein reicht für einen Vergleich nicht. Du musst auch fragen, welche Vorbedingungen ein Algorithmus braucht.

Die lineare Suche geht die Liste Element für Element durch, bis sie das Element gefunden hat. Sie liegt in O(n), weil sie im schlechtesten Fall (gesuchter Wert nicht gefunden) n Vergleiche benötigt. Sie funktioniert auch in unsortierten Arrays. Wenn die Liste klein ist, ist sie oft auch das effizienteste Verfahren.

Die binäre Suche halbiert die Länge des Suchbereichs in jedem Schritt. Ihre Zeitkomplexität ist O(log n). In einem Array mit n Einträgen sind maximal ⌈log₂(n+1)⌉ Vergleichsschritte nötig (aufgerundet). Sie ist deutlich schneller als die lineare Suche, aber sie hat Vorbedingungen. Die Elemente müssen nach einer totalen Ordnungsrelation angeordnet (sortiert) sein. Außerdem muss die Datenstruktur direkten Zugriff auf das n-te Element erlauben. Auf einer einfachen verketteten Liste würde die Effizienz verloren gehen. Und die Ordnung muss zur Suche passen: Gesucht wird nach dem Schlüssel, nach dem sortiert ist.

Beispiel mit 13 sortierten Buchstaben: Bis der Buchstabe G gefunden war, mussten nur 3 Buchstaben verglichen werden. Auch im schlechtesten Fall hätten nur 4 verglichen werden müssen. Ein naiver Algorithmus, der die Liste von vorne nach hinten durchgeht, müsste im ungünstigsten Fall bis zu 13 Elemente untersuchen. Der Vorteil der binären Suche fällt umso stärker ins Gewicht, je größer die Liste ist.

Globale Aussagen über Kostenfunktionen sind oft nicht möglich: In einem Bereich kann die eine günstiger sein, in einem anderen die andere. Darum gehören zu einem Vergleich immer beide Fragen: Wie wächst der Aufwand, und was muss vorher erfüllt sein?