Landau-Notation

Wenn eine App zehn Namen sortiert, merkst du kaum, ob sie schnell oder langsam arbeitet. Bei zehn Millionen Namen sieht das anders aus. Dann zählt nicht nur, dass ein Algorithmus richtig ist, sondern auch, wie stark seine Arbeit wächst. Genau dafür benutzt du die Landau-Notation.

Deine Lernziele

• Du erklärst, wofür die Landau-Notation in der Informatik gebraucht wird.
• Du erkennst typische Wachstumsarten wie konstant, linear und quadratisch.
• Du bestimmst aus einfachen Laufzeitfunktionen die passende O-Notation.
• Du unterscheidest O, Theta und Omega in ihrer Grundidee.

Warum man Wachstum vergleicht

Ein Algorithmus ist eine genaue Schritt-für-Schritt-Anleitung, mit der ein Computer ein Problem löst. Zum Beispiel kann ein Algorithmus eine Liste durchsuchen, Zahlen sortieren oder den kürzesten Weg finden.

Die Eingabegröße ist die Größe der Daten, die der Algorithmus bekommt. In vielen Aufgaben schreibt man dafür \(n\). Wenn du eine Liste mit Namen durchsuchst, ist \(n\) die Anzahl der Namen.

Eine Funktion ordnet jedem erlaubten Wert einen anderen Wert zu. In diesem Thema kann eine Funktion zum Beispiel sagen: Zu einer Eingabegröße \(n\) gehören ungefähr so viele Rechenschritte.

Die Laufzeit meint in der Analyse nicht die Sekunden auf genau deinem Computer. Gemeint ist eher: Wie viele grundlegende Schritte braucht der Algorithmus ungefähr, wenn \(n\) größer wird?

Definition

Die Landau-Notation beschreibt, wie stark eine Laufzeit- oder Speicherfunktion wächst, wenn die Eingabegröße sehr groß wird.

Beispiel

Stell dir vor, du suchst einen Namen in einer unsortierten Klassenliste.

Bei 10 Namen schaust du im schlimmsten Fall 10 Einträge an.
Bei 100 Namen schaust du im schlimmsten Fall 100 Einträge an.
Bei 1000 Namen schaust du im schlimmsten Fall 1000 Einträge an.

Die Arbeit wächst hier ungefähr im gleichen Verhältnis wie die Liste. Wenn sich die Liste verzehnfacht, verzehnfacht sich auch die Anzahl der Prüfungen.

Merke

Die Landau-Notation fragt nicht: Wie viele Sekunden dauert es heute? Sie fragt: Wie verändert sich der Aufwand, wenn die Eingabe viel größer wird?

Die O-Notation als obere Schranke

Die bekannteste Form ist die O-Notation. Das große \(O\) liest du oft als „O von ...“.

Eine obere Schranke ist eine Grenze nach oben. Bei Laufzeiten bedeutet das: Ab einer ausreichend großen Eingabe wächst die echte Laufzeit höchstens so stark wie die angegebene Vergleichsfunktion, bis auf einen festen Faktor.

Definition

\(f(n) \in O(g(n))\) bedeutet: Die Funktion \(f(n)\) wächst für große \(n\) nicht schneller als ein festes Vielfaches von \(g(n)\).

Der feste Faktor ist wichtig. Ob ein Algorithmus ungefähr \(n\) Schritte, \(2n\) Schritte oder \(100n\) Schritte braucht, bleibt in der O-Notation in \(O(n)\). Noch genauer gesagt: Alle drei haben dieselbe enge Wachstumsordnung \(Θ(n)\).

Beispiel

Eine Laufzeit sei

$$ f(n)=3n+7 $$

Für große Listen ist der Teil \(3n\) entscheidend. Die zusätzliche \(7\) fällt im Vergleich zu \(n\) immer weniger ins Gewicht. Deshalb schreibt man:

$$ 3n+7 \in O(n) $$

Das heißt nicht, dass \(3n+7\) gleich \(n\) ist. Es heißt nur: Die Funktion wächst nach oben höchstens linear.

Gut zu wissen

Streng genommen ist \(O(g(n))\) eine Menge von Funktionen. Viele Texte schreiben trotzdem \(f(n)=O(g(n))\). Gemeint ist dann: \(f(n)\) gehört zu dieser Wachstumsklasse.

Typische Wachstumsarten

Eine Wachstumsart beschreibt, wie schnell der Aufwand zunimmt, wenn \(n\) größer wird. In der Informatik tauchen einige Klassen besonders oft auf.

Konstant bedeutet: Der Aufwand bleibt ungefähr gleich, egal wie groß \(n\) wird. Linear bedeutet: Wenn \(n\) doppelt so groß wird, wird der Aufwand ungefähr doppelt so groß. Quadratisch bedeutet: Wenn \(n\) doppelt so groß wird, kann der Aufwand ungefähr viermal so groß werden.

Beispiel

Du hast eine Liste mit \(n\) Zahlen.

Ein Algorithmus geht einmal durch die Liste und zählt alle geraden Zahlen. Das ist \(O(n)\).

Ein anderer Algorithmus vergleicht jede Zahl mit jeder anderen Zahl. Dann entstehen ungefähr \(n \cdot n\) Vergleiche. Das ist \(O(n^2)\).

Merke

Je steiler die Wachstumsart ist, desto wichtiger wird sie bei großen Eingaben. Bei kleinen Eingaben können feste Faktoren noch täuschen.

Wie du eine O-Notation bestimmst

Eine Laufzeitfunktion ist eine Formel, die den Aufwand in Abhängigkeit von \(n\) beschreibt. In Schulaufgaben bekommst du oft eine Funktion wie \(5n^2+3n+20\) und sollst die O-Notation angeben.

Dafür suchst du den Teil, der für sehr große \(n\) am stärksten wächst. Dieser Teil heißt oft der dominierende Term. Ein Term ist ein einzelner Bestandteil einer Summe, zum Beispiel \(5n^2\) oder \(3n\).

Beispiel

Betrachte

$$ f(n)=5n^2+3n+20 $$

Für \(n=10\) ist \(5n^2\) schon \(500\), während \(3n\) nur \(30\) ist. Für \(n=1000\) ist \(5n^2\) schon \(5\,000\,000\), während \(3n\) nur \(3000\) ist.

Der quadratische Term setzt sich immer stärker durch. Deshalb gilt:

$$ 5n^2+3n+20 \in O(n^2) $$

Merke

Bei Polynomen zählt für die O-Notation der höchste Exponent. Konstanten und kleinere Potenzen fallen für große n weg.

Beispiel

$$ 7n^3+100n^2+9 \in O(n^3) $$

Der Term \(7n^3\) wächst am stärksten. Der Faktor \(7\) bleibt ein fester Faktor und wird für die Klasse nicht mitgeschrieben.

O, Theta und Omega

Neben \(O\) gibt es weitere Landau-Symbole. Sie beantworten ähnliche, aber nicht gleiche Fragen.

Die Theta-Notation \(Θ\) beschreibt eine enge Größenordnung. Das heißt: Die Funktion wächst nach oben und nach unten wie dieselbe Vergleichsfunktion, wieder bis auf feste Faktoren.

Die Omega-Notation \(Ω\) beschreibt in der Informatik meist eine untere Schranke. Das heißt: Ab großen Eingaben wächst die Funktion mindestens so stark wie eine Vergleichsfunktion, bis auf einen festen Faktor.

Definition

\(O\) beschreibt eine obere Schranke.
\(Θ\) beschreibt eine enge Schranke.
\(Ω\) beschreibt eine untere Schranke.

Beispiel

Für

$$ f(n)=6n+4 $$

gilt:

$$ f(n) \in O(n) $$

Die Funktion wächst höchstens linear. Es gilt aber auch:

$$ f(n) \in Θ(n) $$

Denn sie wächst nicht nur höchstens linear, sondern wirklich linear. Ab großen \(n\) liegt \(6n+4\) zwischen festen Vielfachen von \(n\), zum Beispiel zwischen \(6n\) und \(7n\). Eine passende untere Schranke ist ebenfalls:

$$ f(n) \in Ω(n) $$

Beispiel

Für

$$ f(n)=n $$

gilt auch \(f(n) \in O(n^2)\). Das ist aber keine enge Beschreibung. \(n\) wächst viel langsamer als \(n^2\).

Die genauere Aussage ist:

$$ f(n) \in Θ(n) $$

Zeitkomplexität und Platzkomplexität

Die Zeitkomplexität beschreibt, wie viele Schritte ein Algorithmus abhängig von der Eingabegröße braucht. Die Platzkomplexität beschreibt, wie viel zusätzlicher Speicher abhängig von der Eingabegröße gebraucht wird.

Beide können mit Landau-Notation angegeben werden. Ein Algorithmus kann bei der Zeit und beim Speicher unterschiedliche Klassen haben.

Beispiel

Ein Algorithmus zählt alle Zahlen in einer Liste zusammen.

Er geht einmal durch die Liste. Die Zeitkomplexität ist also \(O(n)\).

Wenn er nur eine Zwischensumme speichert, braucht er zusätzlich immer gleich viel Speicher. Die zusätzliche Platzkomplexität ist dann \(O(1)\).

Beispiel

Ein Sortierverfahren kann \(O(n^2)\) Zeit brauchen, aber nur \(O(1)\) zusätzlichen Speicher. Ein anderes Sortierverfahren kann schneller sein, dafür aber zusätzlichen Speicher proportional zu \(n\) nutzen.

Merke

Zeit und Speicher sind zwei verschiedene Fragen. Frage immer: Zähle ich Schritte oder zusätzlichen Speicher?

Typische Denkfehler

Ein häufiger Fehler ist, O-Notation als genaue Formel zu lesen. \(O(n^2)\) bedeutet nicht: Der Algorithmus macht genau \(n^2\) Schritte. Es bedeutet: Sein Wachstum lässt sich nach oben durch eine quadratische Funktion begrenzen.

Ein zweiter Fehler ist, kleine Eingaben zu stark zu bewerten. Ein Algorithmus mit \(1000n\) Schritten kann bei kleinen Daten langsamer sein als einer mit \(n^2\) Schritten. Für sehr große \(n\) gewinnt aber irgendwann das lineare Wachstum.

Ein dritter Fehler ist, nur den Namen eines Algorithmus auswendig zu lernen. Viele Algorithmen haben je nach Fall unterschiedliche Laufzeiten. Darum musst du immer wissen, welcher Fall betrachtet wird.

Gut zu wissen

Der Worst Case ist der schlechteste betrachtete Fall für eine Eingabegröße. Der Best Case ist der günstigste Fall. Der Average Case beschreibt einen durchschnittlichen Fall nach einem festgelegten Modell.

Beispiel

Bei einer linearen Suche steht das gesuchte Element vielleicht direkt vorne. Das ist ein sehr guter Fall.

Es kann aber auch gar nicht vorkommen oder ganz hinten stehen. Dann muss der Algorithmus die ganze Liste prüfen. Für den Worst Case ist die lineare Suche daher \(O(n)\).

Zusammenfassung

Die Landau-Notation hilft dir, Algorithmen nach ihrem Wachstum zu vergleichen. Du schaust dabei auf die Eingabegröße \(n\) und fragst, wie sich Schritte oder Speicherbedarf verändern, wenn \(n\) groß wird.

Die O-Notation gibt eine obere Schranke an. Sie sagt also, dass eine Funktion höchstens so stark wächst wie eine Vergleichsfunktion, bis auf feste Faktoren. Bei einfachen Polynomen nimmst du für die übliche O-Angabe den Term mit dem höchsten Exponenten.