Aufwandsabschätzung von Algorithmen

Jeder Computeralgorithmus wird letzendendes von einem Compiler in eine endliche Abfolge von Maschinenbefehlen übersetzt. Es ist, unabhängig von der gewählten Programmiersprache, von großem Interesse, zu wissen, welchen Zeit bzw. Speicheraufwand ein bestimmter Algorithmus hat. Da aber der Maschinencode eines Programms, das einen spezifischen Algorithmus einsetzt, von seiner Prozessorarchitektur abhängt und die Ausführungszeit bzw. der Speicherbedarf eines einzelnen Maschinenbefehls grundsätzlich nicht determinierbar ist, wird i.d.R. nur die Wachstumsrate des Aufwandes bezüglich einer bestimmten Eingabegröße (allgemein: Eingabelänge n) angegeben. Dazu wird vereinbart, dass bestimmte atomare Operationen innerhalb der Sprache konstanten, von n unabhängigen Aufwand besitzen. Die tatsächliche Laufzeit bzw. der tatsächliche Speicheraufwand dieser Operationen ist für den Informatiker nicht relevant. Ziel einer Aufwandsabschätzung ist es daher herauszufinden, wie sich der Aufwand auf einer idealisierten (Turing-)Maschine verändert, wenn man die Eingabegröße verändert.

O-Kalkül

Um ein Maß für das Wachstum der Laufzeit eines Algorithmus zu finden, wird häufig das O-Kalkül verwendet. Die Wachstumsrate wird dabei in der Form O(f(n)) angegeben (siehe auch Aufwandsklassen). Die dabei angegebene Funktion f(n) ist eine Obergrenze für das Wachstum des Algorithmus. Es gilt für n gegen unendlich Aufwand(A(n)) <= f(n). Dabei kann für bestimmte n (insbesondere sehr kleine) durchaus der Aufwand größer als die Schranke sein. Es gibt also prinzipiell unendlich viele f(n), die die Bedingung A(n) ist Element von O(f(n)) erfüllen, für jeden beliebigen Algorithmus A(n). Sinnvoll ist es daher nur, eine möglichst 'kleine' Abschätzung anzugeben.

Aufwandsklassen

Es existieren folgende wesentliche Aufwandsklassen: (hier absteigend nach laufzeit sortiert)

O(log(n))
O(n)
O(n * log(n))
O(n^p) | p > 1
O(p^n) | p > 1

Abschätzung von Schleifen

void algo(int n)
{
 while(n > 0)       //maximal n-mal aufgerufen   
 {
   printf("%d",n);  //konstanter Aufwand = c1
   n--;             //konstanter Aufwand = c2
 } 
}

Der obige Algorithmus stellt einen Countdown in der Konsole dar. Offensichtlich wird die while-Schleife n-mal durchlaufen. Im Allgemeinen gibt man hier die maximale Zahl der Schleifendurchläufe an. Im Beispiel sind sowohl "printf()" als auch "--" mit konstantem Aufwand vereinbart. Es gilt also der Aufwand A(algo) >= n * (c1 + c2)

Anmerkung: Wenn man den Speicherbedarf eines Algorithmus bestimmen will, sollte man sich auf ein bestimmtes Medium beschränken (zB Stack, Festplatte). Im obigen Beispiel würde für die Festplatte gelten: c1 = c2 = 0, also A(algo)=0

Abschätzung von Rekursionen

Im Gegensatz zu Schleifen kann der Aufwand einer rekursiven Funktion nicht so ohne weiteres abgeschätzt bzw. ausmultipliziert werden. Glücklicherweise hat der Informatiker hier Rekurrenzrelationen zur Hand:

Rekurrenzrelation O(A)
A(n) =  A(n - 1) + bn^k                        O(n^k+1)
A(n) = cA(n - 1) + bn^k mit c > 1              O(c^n)
A(n) = cA(n/d) + bn^k mit c > d^k              O(n^(log_d c)) (nach dem Master-Theorem)
A(n) = cA(n/d) + bn^k mit c < d^k              O(n^k)         (nach dem Master-Theorem)
A(n) = cA(n/d) + bn^k mit c = d^k              O(nk log n)    (nach dem Master-Theorem)

c = Anzahl der rekursiven Aufrufe
k = konstanter Aufwand
d = Teiler von n im rekursiven Aufruf
 

Beispielsweise findet sich zu dem Algorithmus

int a(int n)
{
 if (n > 0) return n + a(n - 1);
 return 0;
}

Anhand der Tabelle die Rekurrenzrelation A(n - 1) + bn^k wobei b der Aufwand der if Abfrage, bzw. des return Befehls ist und k = 0. Demzufolge gilt A(a(n)) <= n. (mehr zu den Aufwandsklassen folgt)

Anwendung

Angenommen, ein Programm verwendet folgenden Algorithmus für die Berechnung der Potenz:

int pot(b, p)
{
   int r = 1;
   for (int i = 1; i <= p; i++)
       r = * b;
   return(r);
{

Der Aufwand wäre offensichtlich linear wachsend mit p. Also A(p) ist Element von O(p). Würden also die Potenzen verdoppelt, verdoppelte sich damit auch die Laufzeit der Berechnung. Die Frage ist nun, ob man den Algorithmus schneller machen kann.

Die Lösung ist relativ simpel:

int fastpot(int b, int p)
{
	if (p == 0)
	return(1);

	if (p == 1)
	return(b);

	if (p % 2 == 0)
	return(fastpot(b,p/2) * fastpot(b,p/2));
	else return(b * fastpot(b, (p -1) /2) * fastpot(b, (p - 1) / 2));
}

Wenn man nun anhand der Rekurrenzrelation (die letzte mit d = 2, c = 2, k = 1, b = 0) den Aufwand abschätzt, erhält man A(p) ist Element von O(n * log(p)), also für sehr große p deutlich schneller!