Laufzeit von Algorithmen
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 notwendig sind, um die der Algorithmus braucht. Dabei gilt folgende vereinfachende Grundannahmen:
- Die Anzahl der Operationen wird bestimmt in Abhängigkeit von der Größe des Problems, d.h. die Laufzeit ist in der Regel eine Funktion.
- In der Regel reicht es, die am häufigsten vorkommende Operation abzuschätzen - oft fallen die anderen Operationen nicht ins Gewicht.
- Jede Operation gilt als gleich "teuer".
Die Algorithmen lassen sich - gemäß ihrer Laufzeit - in verschiedene Klassen, die sogenannten Landau-Klassen einteilen.
Vorgehensweise
In der Regel ist es hilfreich, erst die Laufzeit für eine vorgegebene 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 abgeschätzt.
| Element Nr. | Anzahl Vergleiche beim Einfügen |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| ... | ... |
| 999 | 998 |
| 1000 | 999 |
Insgesamt braucht man also [math]\displaystyle{ 1+2+...+998+999 = {999 \mult 1000} \over {2} = 499.500 }[/math] Vergleiche.