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 geling 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 Quicksortt-Algorithmus gehört im worst-case-Fall zur Klasse O(n*log(n)).

X

Fehler melden

X

Suche