Laufzeit von Algorithmen

Fachbegriffe

best case, average case, worst case, Operation, Landau-Klasse

Grundidee

Mit der Laufzeit von Algorithmen ist nicht die Laufzeit in Sekunden auf einem speziellen Computer gemeint.

Stattdessen wird die Menge der Operationen abgeschätzt, die der Algorithmus braucht. Dabei gelten folgende vereinfachende Grundannahmen:

• Die Anzahl der Operationen wird bestimmt in Abhängigkeit von der Größe des Problems, z.B. der Anzahl der Elemente.
• Jede Operation gilt als gleich "teuer".
• In der Regel reicht es, die am häufigsten vorkommende Operation abzuschätzen - oft fallen die anderen Operationen nicht ins Gewicht.

Die Algorithmen lassen sich - gemäß ihrer Laufzeit - in verschiedene Klassen, die sogenannten Landau-Klassen einteilen.

Best Case - Average Case – Worst Case

Bei der Abschätzung der Laufzeit von Algorithmen werden in der Regel drei Fälle unterschieden:

• Der Best Case ist eine Situation, in der man die Lösung schnellstmöglichst finden kann.
• Der Average Case ist der durchschnittliche Fall; oft ermittelt man den Average Case aus einem Mittelwert von zufälligen Situationen.
• Der Worst Case ist die schlimmste anzunehmende Situation.

In der Praxis sind im Allgemeinen nur der Worst Case und der Average Case interessant.

Vorgehensweise

In der Regel ist es hilfreich, erst die Laufzeit für eine feste Größe des Problems (z.B. 1000) zu bestimmen.

Dann schließt man auf die Laufzeit des Problems allgemein.

Beispiel: Insertionsort

Bei Insertionsort wird die Ergebnisliste nach und nach aufgebaut.

Dazu wird jeweils das erste Element aus der ursprünglichen Liste genommen und gelöscht. Dann wird die Ergebnisliste von vorne bis zu der Stelle durchlaufen, an der das Element eingefügt werden muss; da wird es dann eingefügt.

Berechnung der Laufzeit für 1000 Elemente

Die häufigste vorkommende Operation bei Insertionsort ist der Vergleich; nur dieser wird hier für den Worst Case abgeschätzt.

Notwendige Vergleiche für jedes Element

Element Nr.	Anzahl Vergleiche beim Einfügen in die Ergebnisliste im Worst Case
1	0
2	1
3	2
...	...
999	998
1000	999

Gesamtzahl der notwendigen Vergleiche

Insgesamt braucht man also 1+2+...+998+999 Vergleiche.

Um das zu berechnen, braucht man die folgende mathematische Formel, die in der Informatik einfach ohne Herleitung verwendet wird: [math]\displaystyle{ 1+2+...+x = {{x \times {(x+1)}} \over {2}} }[/math]

Anwendung der Formel:

[math]\displaystyle{ 1+2+...+998+999 = {{999 \times 1000} \over {2}} = 499.500 }[/math] Vergleiche.

Berechnung der Laufzeit für n Elemente

In der Formel oben wird jetzt einfach 1000 ersetzt durch n.

Entsprechend ist 999 dann (n-1).

Für n Elemente braucht man also [math]\displaystyle{ 1+2+...+(n-2)+(n-1) = {{(n-1) \times n} \over {2}} = {{n^2} \over 2} - {n \over 2} }[/math] Vergleiche.

Der lineare Teil ( -n/2 ) ist für große n kaum von Bedeutung.

Deswegen gehört Insertionsort zur Landau-Klasse O(n²).