Einordnung in Komplexitätsklassen
Wachstumsprototypen
Das asymptotische Wachstumsverhalten von Kostenfunktionen beschreibt man oft in Relation zu gängigen Wachstumsprototypen.
Beispiel: Selectionsort
Der Vergleichsaufwand beim Selectionsort-Algorithmus lässt sich durch die Kostenfunktion T1(n) = n2/2 - n/2 beschreiben. Diese Kostenfunktion wächst genauso schnell wie die quadratische Funktion f(n) = n2.
Hier wird die Funktion f(n) = n2 als Prototyp zur Beschreibung von quadratischem Wachstum benutzt. Quadratisches Wachstum ist ein häufig anzutreffendes Wachstumsverhalten mit der Grundeigenschaft: Wenn n sich verdoppelt, dann vervierfacht sich f(n).
Beispiel: Quicksort
Der durchschnittliche Vergleichsaufwand beim Quicksort-Algorithmus (average-case) lässt sich durch die Kostenfunktion T2(n) = n*log2(n) beschreiben. Diese Kostenfunktion wächst schneller als die lineare Funktion f(n) = n, aber langsamer als die Funktion f(n) = n2.
Hier wird das Wachstumsverhalten des Vergleichsaufwand durch die Prototypen f(n) = n (für lineares Wachstum) und f(n) = n2 (für quadratisches Wachstum) eingegrenzt. Diese Aussage liefert eine erste grobe Vorstellung über das zu beschreibende Wachstumsverhalten. Lineares Wachstum zeichnet sich durch die folgende Grundeigenschaft aus: Wenn n sich verdoppelt, dann verdoppelt sich auch f(n). Beim quadratischen Wachstum vervierfacht sich f(n), wenn n sich verdoppelt. Dazwischen ist das Wachstumsverhalten des Vergleichsaufwands des Quicksort-Algorithmus anzusiedeln.
Die folgende Tabelle zeigt die wichtigsten Prototypen zu Beschreibung des Wachtumsverhaltens von Wachstumsfunktionen.
| Wachstumsart | Prototyp | Grundeigenschaft |
|---|---|---|
| logarithmisches Wachstum | f(n) = log(n) (mit beliebiger Logarithmenbasis) | Wenn n sich verdoppelt, dann wächst f(n) um einen konstanten Betrag. |
| lineares Wachstum | f(n) = n | Wenn n sich verdoppelt, dann verdoppelt sich f(n) ebenfalls. |
| logarithmisch-lineares Wachstum | f(n) = n*log(n) (mit beliebiger Logarithmenbasis) | |
| quadratisches Wachstum | f(n) = n2 | Wenn n sich verdoppelt, dann vervierfacht sich f(n). |
| kubisches Wachstum | f(n) = n3 | Wenn n sich verdoppelt, dann verachtfacht sich f(n). |
| polynomiales Wachstum | f(n) = nk | Wenn n sich verdoppelt, dann vervielfacht sich f(n) mit 2k. |
| exponentielles Wachstum | f(n) = bn | Wenn n sich um 1 erhöht, dann vervielfacht sich f(n) mit b |
Beachte, dass die in der Tabelle vorkommenden Funktionen nach der Wachstumsgeschwindigkeit angeordnet sind: Die Funktion f(n) = log(n) wächst langsamer als die Funktion f(n) = n, dieser wiederum langsamer als die Funktion f(n) = n*log(n) usw.. Die Funktionsprototypen legen somit auch Größenordnungen zur Einschätzung des Wachstumsverhaltens von (Kosten-) Funktionen fest.
Aufgabe 1
Ergänze die Werte in der Tabelle und verdeutliche anhand der Werte das Wachstumsverhalten verschiedener Wachstumsprototypen. Beachte, dass (die Problemgröße) n hier schrittweise um eine Zehnerpotenz vergrößert wird.
| Wachstumsart | Wachstumsprototyp | n = 10 | n = 100 | n = 1000 | n = 104 | n = 105 | n = 106 |
|---|---|---|---|---|---|---|---|
| logarithmisch | f(n) = log2(n) | ||||||
| linear | f(n) = n | ||||||
| logarithmisch-linear | f(n) = n*log2(n) | ||||||
| quadratisch | f(n) = n2 | ||||||
| kubisch | f(n) = n3 | ||||||
| exponentiell | f(n) = 2n |
Komplexitätsklassen
Eine genaue Zuordnung zu einem der Wachstumsprototypen gelingt manchmal nicht. Dennoch ist ein Vergleich mit den Wachstumsprototypen sinnvoll. Wir führen hierzu die folgenden Bezeichnungen ein.
Eine (Kosten-) Funktion f wächst nicht schneller als eine (Kosten-) Funktion g, wenn f genauso schnell oder langsamer als g wächst.
Die Klasse aller Funktionen, die nicht schneller wachsen als eine vorgegebene
(Kosten-) Funktion f, wird mit O(f) bezeichnet.
Man liest das so: Groß O von f
.
Beispiel: Die Klasse O(n3) umfasst alle (Kosten-) Funktionen, die nicht schneller wachsen als f(n) = n3. Zu dieser Klasse gehören also alle linearen, alle logarithmisch-linearen, alle quadratischen und alle kubischen Funktionen. Zu dieser Klasse gehört aber z.B. auch die Funktion T(n) = n2*(log2n)3.
Aufgabe 2
Welche der folgenden Aussagen sind wahr bzw. falsch? Begründe.
(a) Die Funktion T(n) zur Beschreibung des Vergleichsaufwands beim Selectionsort-Algorithmus gehört zur Klasse O(n2).
(b) Die Funktion T(n) zur Beschreibung des durchschnittlichen Vergleichsaufwands beim Quicksort-Algorithmus gehört zur Klasse O(n2).
(c) Die Funktion T(n) zur Beschreibung des Vergleichsaufwands beim Insertionsort-Algorithmus gehört im best-case-Fall zur Klasse O(n).
(d) Die Funktion T(n) zur Beschreibung des Vergleichsaufwands beim Quicksort-Algorithmus gehört im worst-case-Fall zur Klasse O(n*log(n)).
