ist höchstens von der Größenordnung
in Zeichen:
falls
existieren mit
Statt sagt man auch
Wegen des konstanten Faktors
ist die exakte Festlegung
eines Schrittes nicht erforderlich.
Beispiel:
Sei
.
Dann ist
Natürlich gilt auch:
Die wesentlichen Klassen
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||
binäre | lineare | schlaues | dummes | Gleichungs- | alle | alle | |||
Suche | Suche | Sortieren | Sortieren | system | Teil- | Permu- | |||
lösen | mengen | tationen |
![]() |
10 | 20 | 30 | 40 | 50 | 60 |
![]() |
2.3 ![]() |
3.0 ![]() |
4.9 ![]() |
5.3 ![]() |
5.6 ![]() |
5.9 ![]() |
![]() |
10 ![]() |
20 ![]() |
30 ![]() |
40 ![]() |
50 ![]() |
60 ![]() |
![]() |
23 ![]() |
60 ![]() |
147 ![]() |
212 ![]() |
280 ![]() |
354 ![]() |
![]() |
100 ![]() |
400 ![]() |
900 ![]() |
1.6 ms | 2.5 ms | 3.6 ms |
![]() |
1 ms | 8 ms | 27 ms | 64 ms | 125 ms | 216 ms |
![]() |
1 ms | 1 s | 18 min | 13 Tage | 36 J | 366 Jh |
![]() |
59 ms | 58 min | 6.5 J | 3855 Jh | ![]() |
![]() |
![]() |
3.62 s | 771 Jh | ![]() |
![]() |
![]() |
![]() |
WächstAnaloge Aussagen sind möglich bzgl. Speicherplatz.um
, so wächst
um den Faktor
.
Wächstum
, so wächst
um den Faktor
.
Ein 1000-mal schnellerer Computer kann eine um 10 Daten größere Eingabe in derselben Zeit bearbeiten.
Aussagen über Laufzeit und Platzbedarf beziehen sich auf
![]() |
günstigster Fall |
![]() |
ungünstigster Fall |
![]() |
im Mittel |