Mit Google fortfahren
Landau-Notation: O, Omega und Theta einfach erklärt
Die Landau-Notation beschreibt, wie der Zeit- oder Speicherbedarf eines Algorithmus mit der Eingabegröße wächst. Sie liefert keine Stoppuhrzeit und nicht automatisch den Worst Case: Zuerst legst du fest, welchen Fall du untersuchst, und dann beschreibst du dessen Wachstum mit $O$, $\Omega$ oder $\Theta$.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum zählt Wachstum mehr als Sekunden?
Stell dir zwei Programme vor, die dieselbe Aufgabe lösen. Eine gemessene Laufzeit wie „12 Millisekunden“ gilt nur für eine bestimmte Eingabe, einen bestimmten Rechner und eine bestimmte Implementierung. Für einen allgemeineren Vergleich zählt man deshalb grundlegende Arbeitsschritte in Abhängigkeit von der Eingabegröße $n$.
Bei einer Liste ist $n$ meist die Zahl ihrer Elemente. Bei einer ganzen Zahl kann dagegen die Zahl ihrer Bits die passende Eingabegröße sein. Du musst also zuerst klären, was $n$ bedeutet.
Asymptotisches Wachstum
Asymptotisches Wachstum beschreibt das Verhalten einer Kostenfunktion für immer größere Eingaben, in der Informatik gewöhnlich für $n\to\infty$. Dabei interessiert vor allem, welcher Teil der Funktion langfristig am stärksten wächst.
Ein Programm A benötigt ungefähr $100n$ Schritte, ein Programm B ungefähr $n^2$ Schritte. Für $n=10$ sind das 1 000 Schritte bei A und 100 bei B: B ist zunächst günstiger. Für $n=1 000$ sind es 100 000 Schritte bei A und 1 000 000 bei B. Die kleinere Wachstumsordnung gewinnt also oft erst ab einer gewissen Eingabegröße.
Landau-Notation vergleicht Wachstum für große Eingaben. Konstanten, Hardware und kleine Eingaben können für die konkrete Laufzeit trotzdem wichtig sein.
O, Omega und Theta sicher unterscheiden
Für die folgenden Definitionen seien $f(n)$ und $g(n)$ ab einer gewissen Stelle nicht negativ. Die Konstanten dürfen nicht von $n$ abhängen.
Obere Schranke: O
$f(n)\in O(g(n))$ bedeutet: Es gibt Konstanten $c\gt0$ und $n_0$, sodass für alle $n\ge n_0$ gilt
$$f(n)\le c\cdot g(n).$$
Ab der Schwelle $n_0$ wächst $f$ also höchstens so schnell wie ein konstantes Vielfaches von $g$.
Untere Schranke: Omega
$f(n)\in\Omega(g(n))$ bedeutet in der Informatik: Es gibt Konstanten $c\gt0$ und $n_0$, sodass für alle $n\ge n_0$ gilt
$$f(n)\ge c\cdot g(n).$$
Ab der Schwelle wächst $f$ also mindestens so schnell wie ein konstantes Vielfaches von $g$.
Enge Schranke: Theta
$f(n)\in\Theta(g(n))$ bedeutet: Es gibt Konstanten $c_1,c_2\gt0$ und $n_0$, sodass für alle $n\ge n_0$ gilt
$$c_1g(n)\le f(n)\le c_2g(n).$$
Damit ist $g$ zugleich untere und obere Schranke bis auf konstante Faktoren.
| Symbol | Aussage | Bild im Kopf |
|---|---|---|
| $O(g)$ | obere Schranke | nicht schneller als ein Vielfaches von $g$ |
| $\Omega(g)$ | untere Schranke | nicht langsamer als ein Vielfaches von $g$ |
| $\Theta(g)$ | enge Schranke | zwischen zwei Vielfachen von $g$ |
Betrachte $f(n)=3n^2+4n+2$. Für $n\ge1$ gilt einerseits $f(n)\ge3n^2$. Andererseits sind dann $4n\le4n^2$ und $2\le2n^2$. Deshalb gilt
$$3n^2\le f(n)\le9n^2.$$
Mit $c_1=3$, $c_2=9$ und $n_0=1$ ist gezeigt: $f(n)\in\Theta(n^2)$. Damit liegt $f$ zugleich in $O(n^2)$ und in $\Omega(n^2)$.
Eine O-Schranke muss nicht eng sein. Auch $n^2\in O(n^3)$ ist richtig, aber weniger aussagekräftig als $n^2\in\Theta(n^2)$. Formal stehen hinter $O(g)$, $\Omega(g)$ und $\Theta(g)$ Mengen von Funktionen. Die verbreitete Schreibweise $f(n)=O(g(n))$ solltest du deshalb nicht wie eine gewöhnliche Gleichung behandeln.
Den dominierenden Term finden
Bei einer Summe bestimmt für große $n$ der am schnellsten wachsende Summand die enge Größenordnung. Feste positive Faktoren verändern die Klasse nicht.
Gegeben ist
$$T(n)=5n^3+20n^2+7n+40.$$
Der Term $n^3$ wächst schneller als $n^2$, $n$ und eine Konstante. Der Faktor 5 ist fest. Daher gilt
$$T(n)\in\Theta(n^3).$$
Die präzise Aussage ist $\Theta(n^3)$, weil der positive kubische Leitterm sowohl eine passende obere als auch eine passende untere Schranke liefert.
So gehst du bei einem Polynom mit positivem Leitterm vor:
- Ordne die Summanden nach ihren Potenzen von $n$.
- Wähle die höchste vorkommende Potenz.
- Lass feste Faktoren und niedrigere Potenzen für die asymptotische Klasse weg.
- Schreibe $\Theta$ statt nur $O$, wenn du obere und untere Schranke begründen kannst.
„Weglassen“ ist nur eine Abkürzung für die Einordnung des Wachstums. Wenn du konkrete Schrittzahlen oder Laufzeiten berechnest, darfst du weder Faktoren noch Summanden löschen.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Bei der Funktion „sieben n Quadrat plus drei n plus neun“ ist der höchste Exponent . Ihre enge Ordnung ist deshalb . Eine kubische obere Schranke wäre zwar , aber weniger .
Fall und Schranke sind zwei verschiedene Fragen
Ein Algorithmus kann für gleich große Eingaben unterschiedlich viel Arbeit benötigen. Deshalb legst du zuerst die betrachteten Eingaben fest:
- Best Case: günstigste Eingabe der Größe $n$;
- Worst Case: ungünstigste Eingabe der Größe $n$;
- Average Case: erwarteter Aufwand unter einer ausdrücklich angegebenen Wahrscheinlichkeitsverteilung.
Erst danach verwendest du $O$, $\Omega$ oder $\Theta$ für die entstandene Kostenfunktion.
Bei der linearen Suche wird eine Liste von links nach rechts geprüft.
| Betrachteter Fall | Zahl der Vergleiche | Enge Ordnung |
|---|---|---|
| Gesuchtes Element steht am Anfang | $1$ | $\Theta(1)$ |
| Gesuchtes Element fehlt | $n$ | $\Theta(n)$ |
Der erste Fall ist der Best Case, der zweite ein Worst Case. Beide Funktionen könnten zusätzlich mit einer O-Schranke beschrieben werden: $1\in O(1)$ und $n\in O(n)$. Daran siehst du: Das Symbol $O$ bedeutet nicht „Worst Case“.
Für einen Average Case genügt die Aussage „typische Eingaben“ nicht. Du brauchst ein Modell dafür, wie wahrscheinlich die möglichen Eingaben sind. Ohne dieses Modell ist keine eindeutige durchschnittliche Laufzeit festgelegt.
Schleifen Schritt für Schritt analysieren
Für einfache Programme kannst du zunächst zählen, wie oft eine Anweisung ausgeführt wird. Danach fasst du die entstehende Funktion asymptotisch zusammen.
Der folgende Abschnitt verarbeitet alle geordneten Paare einer Liste:
text for i = 0 bis n - 1 for j = 0 bis n - 1 verarbeite(i, j)
Die äußere Schleife läuft $n$-mal. Bei jedem Durchlauf läuft die innere Schleife ebenfalls $n$-mal. Wird verarbeite in konstanter Zeit ausgeführt, entstehen genau $n\cdot n=n^2$ Aufrufe. Die Schleifenarbeit liegt damit in $\Theta(n^2)$.
Bei voneinander unabhängigen, nacheinander ausgeführten Abschnitten addierst du ihre Kosten. Bei vollständig ineinander geschachtelten Schleifen multiplizierst du die Durchlaufzahlen nur dann direkt, wenn sie wirklich unabhängig voneinander sind.
Nun endet die innere Schleife schon vor $i$:
text for i = 0 bis n - 1 for j = 0 bis i - 1 verarbeite(i, j)
Die Zahl der Aufrufe ist
$$0+1+2+\dots+(n-1)=\frac{n(n-1)}2=\frac{n^2-n}2.$$
Der dominante Term ist $\frac12n^2$. Deshalb liegt auch diese Schleifenarbeit in $\Theta(n^2)$, obwohl sie nur ungefähr halb so viele Aufrufe wie das erste Beispiel erzeugt.
Zähle erst, vereinfache danach. „Zwei Schleifen bedeuten quadratisch“ ist ohne Prüfung ihrer Grenzen keine sichere Regel.
Wachstumsordnungen sinnvoll vergleichen
Typische Klassen lassen sich für große $n$ so anordnen:
$$1\;\lt\;\log n\;\lt\;n\;\lt\;n\log n\;\lt\;n^2\;\lt\;2^n\;\lt\;n!$$
| Ordnung | Name | Wirkung einer Verdopplung von $n$ |
|---|---|---|
| $\Theta(1)$ | konstant | asymptotisch keine Änderung |
| $\Theta(\log n)$ | logarithmisch | Zuwachs um einen konstanten Betrag |
| $\Theta(n)$ | linear | ungefähr Faktor 2 |
| $\Theta(n\log n)$ | quasilinear | etwas mehr als Faktor 2 |
| $\Theta(n^2)$ | quadratisch | ungefähr Faktor 4 |
| $\Theta(2^n)$ | exponentiell | Erhöhung von $n$ um 1 verdoppelt den Wert |
Die Basis eines Logarithmus ändert die Klasse nicht, denn Logarithmen verschiedener Basen unterscheiden sich nur durch einen konstanten Faktor.
Eine kleinere Wachstumsordnung entscheidet trotzdem nicht jede praktische Wahl. Prüfe zusätzlich:
- Erfüllt die Eingabe alle Vorbedingungen des Algorithmus?
- Welche Eingabegröße und welcher Fall werden verglichen?
- Geht es um Zeit, zusätzlichen Speicher oder beides?
- Sind die konkreten Eingaben so klein, dass Konstanten noch überwiegen?
Binäre Suche hat bei einer sortierten Liste eine logarithmische Worst-Case-Laufzeit. Ist die Liste nicht sortiert, kannst du diese Aussage nicht einfach anwenden. Das Sortieren selbst verursacht Aufwand; bei nur einer Suche kann eine lineare Suche deshalb trotz ihrer höheren Wachstumsordnung sinnvoll sein.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Landau-Notation
- Bedeutung
- Wachstum für große Eingaben
- Zeit oder Speicher
- Schranken
- O: obere Schranke
- Omega: untere Schranke
- Theta: enge Schranke
- Analyse
- Fall und Eingabegröße festlegen
- Arbeitsschritte zählen
- dominierenden Term bestimmen
- Grenzen
- keine exakte Laufzeit
- O ist nicht automatisch Worst Case
- Vorbedingungen und Konstanten mitprüfen
- Bedeutung
Abschluss-Check
Wenn du bei einer Analyse unsicher bist, stelle dir drei getrennte Fragen: Was ist $n$? Welchen Fall untersuche ich? Welche obere und untere Schranke kann ich tatsächlich begründen?