Modellierung der Kosten

Kostenmaße und Kostenfunktionen

Betrachten wir zunächst einen Algorithmus (bzw. eine geeignete Implementierung) zur Lösung des Sortierproblems:

def selectionsort(L):
    n = len(L)
    i = 0
    while i < n-1:
        minpos = i
        m = i+1
        while m < n:
            if L[m] < L[minpos]:
                minpos = m
            m = m+1
        h = L[i]
        L[i] = L[minpos]
        L[minpos] = h
        i = i+1
    return L

Bei der Ausführung des Algorithmus (bei vorgegebener Problemgröße) spielt es eine Rolle, wie viele Operationen ausgeführt werden müssen. Operationen sind im vorliegenden Algorithmus u.a. das Ausführen eines Vergleichs und das Ausführen einer Zuweisung. Als Kostenmaß zur Beschreibung des zeitlichen Aufwands könnte man also die Gesamtanzahl der auszuführenden Vergleiche und Zuweisungen wählen.

Eine solche Festlegung des Kostenmaßes würde von folgender Vereinfachung ausgehen: Alle Vergleiche und Zuweisungen liefern denselben Beitrag zur Ausführungszeit. Ein Vergleich von Indexwerten (wie m < n) würde als gleichwertig mit einem Vergleich von Datenwerten (wie L[m] < L[minpos]) behandelt. Wenn die zu sortierende Liste nur Zahlen verwaltet, mag das angemessen sein. Wenn die Liste aber komplexere Datensätze verwaltet und der Vergleich dieser Datensätze aufwendig ist, dann ist der Gleichwertigkeitsansatz sicher nicht sinnvoll.

Bei der Festlegung eines Kostenmaßes müssen also Annahmen über den Aufwand der verschiedenen auszuführenden Operationen gemacht werden. Zwei ganz unterschiedliche Wege kann man dabei bestreiten. Ein Weg besteht darin, unterschiedliche Aufwände von Operationen möglichst genau zu erfassen und im Kostenmaß zu berücksichtigen. Ein anderer Weg beschränkt sich darauf, dominante Operationen auszuwählen und die Kosten nur grob abzuschätzen. Wir werden hier den zweiten Weg beschreiten.

Wenn man den Vergleich von Datensätzen als dominate Operation beim Sortieren ansieht, dann lässt sich das folgende Kostenmaß für Sortieralgorithmen festlegen: Alle Datensatzvergleiche werden als gleichaufwendig angesehen (egal wie die Daten im Detail beschaffen sind) und daher nur gezählt. Alle anderen Operationen werden nicht weiter berücksichtigt. Mit dieser Festlegung erhält man die folgende Kostenfunktion T(n) zur Beschreibung der Zeitkomplexität beim Sortieren:

Problemgröße n: Anzahl der Datensätze (Listenelemente)

Kosten T(n): Anzahl der Datensatzvergleiche bei der Ausführung des Algorithmus bei einer Problemgröße n

Folgende Begriffe werden bei der Aufwandsmodellierung benutzt:

Bei der Beschreibung der Zeitkomplexität mit Hilfe einer Kostenfunktion werden in der Regel eine Reihe von Vereinfachungen vorgenommen sowie Annahmen gemacht. Die Festlegung einer Kostenfunktion kann somit als eine Form der Modellierung angesehen werden, weil hier ein Berechnungsmodell entwickelt werden muss, das den Berechnungsaufwand vereinfachend beschreibt.

Wie bei jeder Modellierung kann das entwickelte Modell mehr oder auch weniger geeignet sein, um die zu beschreibende Wirklichkeit darzustellen. Bei der Modellierung der Zeitkomplexität kommt es darauf an, richtige Annahmen über den Aufwand bestimmter, im Algorithmus vorkommender Operationen zu machen.