| Proseminar | |
| Programming Pearls | |
| Algorithm Design Techniques | |
| von Andreas Lenerz | |
Zeiten im Vergleich
Die ganze Zeit verwendet man begriffe wie O( n ) oder O( n² ) und sagt, daß das eine besser das andere schlechter ist. Aber was bedeutet überhaupt für eine praktische Anwendung, daß sie O( n² ) ist, aber O( n ) sein könnte ?
Genau das wird auf dieser Seite gezeigt:
| Laufzeit | Zeitmultiplikator für Eingabe der Größenordnung 10n | Faktor für Problemgröße bei zehnfacher Zeit |
| O( n³ ) | 1000 | 2,15 |
| O( n² ) | 100 | 3,16 |
| O( n log( n ) ) | >10 | <10 |
| O( n ) | 10 | 10 |
Hier sieht man was unterschiedliche Laufzeiten ausmachen. A2 benötigt bei einer Verzehnfachung der Problemgröße 100 Mal länger, Algorithmus A5 nur 10 Mal. Das bedeutet, daß A5 für die 100-fache Problemgröße den gleichen Zeitfaktor besitzt wie A2 oder A3 für die 10-fache PG.
Interessant auch die Vergrößerung der Zeit um Faktor 10. Deutlich sieht man hier A1 bei knapp mehr als der doppelten Länge des zu lösenden Problems verweilen, wohingegen A5 die 10-fache Eingabelänge bewältigt. Das ist ein Faktor von mehr als 4. Ein 10 Mal so schneller Rechner wie der, der einem zur Verfügung steht, kann also lediglich die 2,15-fache Problemgröße mit A1 erledigen. Schnellere Computer können so starke Geschwindigkeitseinbußen hinnehmen, denn nicht immer liegt die langsame Geschwindigkeit an der CPU. Manchmal ( wobei ich niemandem etwas unterstelle ) kann ein extremer Geschwindigkeitsverlust auch durch die benutzten Algorithmen kommen, und häufig kann man seine Programme durch schlichtes Nachdenken noch weiter optimieren.
Die Zeiten der Algorithmen A1-5 im Vergleich:
| Algorithmus | A1 | A2 | A3 | A4 | A5 | ||||||||||
| n | min | sec | msec | min | sec | msec | min | sec | msec | min | sec | msec | min | sec | msec |
| 10 | 0 | 0 | <1 | 0 | 0 | <1 | 0 | 0 | <1 | 0 | 0 | <1 | 0 | 0 | <1 |
| 100 | 0 | 0 | 10 | 0 | 0 | <1 | 0 | 0 | <1 | 0 | 0 | <1 | 0 | 0 | <1 |
| 1.000 | 0 | 2 | 394 | 0 | 0 | 20 | 0 | 0 | 30 | 0 | 0 | <1 | 0 | 0 | <1 |
| 10.000 | 39 | 23 | 709 | 0 | 1 | 522 | 0 | 1 | 773 | 0 | 0 | 10 | 0 | 0 | <1 |
| 100.000 | - | 3 | 9 | 552 | 3 | 34 | 589 | 0 | 0 | 90 | 0 | 0 | 20 | ||
| 1.000.000 | - | - | - | 0 | 0 | 991 | 0 | 0 | 70 | ||||||
| 10.000.000 | - | - | - | 0 | 10 | 996 | 0 | 0 | 590 | ||||||
Diese Ergebnisse stammen von einem Pentium3 733 MHz, Win2000, Java
Wie man hier sieht bestätigt sich das, was auf den vergangenen Seiten bereits mehrfach gesagt wurde. Die Ergebnisse der Algorithmen A1-3 für große n wurden daher mit "-" ausgefüllt, da eine Berechnung der Werte mit dem Computer zuviel Zeit in Anspruch genommen hätte.
| Algorithmus | A1 | A2 | A4 | A5 |
| n | Zeit | Zeit | Zeit | Zeit |
| 1.000 | 1,3 sec | 10 msec | 0,4 msec | 0,05 msec |
| 10.000 | 22 min | 1 sec | 6 msec | 0,5 msec |
| 100.000 | 15 days | 1,7 min | 78 msec | 5 msec |
| 1.000.000 | 41 years | 2,8 hours | 0,94 sec | 48 msec |
| 10.000.000 | 41 millennia | 1,7 weeks | 11 sec | 0,48 sec |
Diese Ergebnisse stammen von einem Pentium2 400 MHz, C
Dies sind nicht die genau berechneten Werte, sondern die durch Hochrechnung enstandenen. A3 wurde weggelassen, weil es die gleiche Zeitkomplexität wie A2 besitzt. Hier wird auf ganz extreme Weise gezeigt, was ein wenig Nachdenken bewirken kann, denn der Unterschied zwischen 0,48 sec und 41 Jahrtausenden ist doch deutlich.
Um dieses Spiel fortzusetzen, nun ein weiteres kleines Beispiel um die Geschwindigkeit von A1 und A5 zu verdeutlichen:
| n | Alpha 21164A 533MHz C Cubic Algorithm |
TRS-80 2,03 MHz Baujahr 1980 Basic Linear Algorithm |
| 10 | 0,6 microsecs | 200msec |
| 100 | 0,6 msec | 2 sec |
| 1.000 | 0,6 sec | 20 sec |
| 10.000 | 10 min | 3,2 min |
| 100.000 | 7 days | 32 min |
| 1.000.000 | 19 years | 5,4 hours |
Wie man sieht, läßt man auf dem schnellen Rechner unter C den kubischen Algorithmus A1 laufen, wohingegen der TSR-80 unter Basic ( deutlich langsamer als C ) den linearen Algorithmus beherrscht.
Anfangs ist der Alpha aufgrund seiner höheren Rechengeschwindigkeit vorne, aber bereits nach etwa 2 Minuten ( und ca. n = 5800 ) sind beide in der Berechnung gleich weit fortgeschritten und bei wachsenden Problemgrößen liegt der scheinbar langsamere TSR-80 durch den besseren Algorithmus doch deutlich vorne.
Somit kommt es also nicht nur auf die richtige Wahl des Rechners an, den man benutzt, auch die Wahl des Algorithmus will wohl getroffen sein !!!