f ist höchstens von der Größenordnung g
in Zeichen: f O(g)
falls n0, c N existieren mit
Statt f O(g) sagt man auch f = O(g)
Wegen des konstanten Faktors c ist die exakte Festlegung eines Schrittes nicht erforderlich.
Beispiel:
Sei f (n) = 31n + 12n2.
Dann ist f O(n2)
Natürlich gilt auch: f O(n7) Die wesentlichen Klassen
log n | n | n . log n | n2 | n3 | n4 | ... | 2n | 3n | n! |
binäre | lineare | schlaues | dummes | Gleichungs- | alle | alle | |||
Suche | Suche | Sortieren | Sortieren | system | Teil- | Permu- | |||
lösen | mengen | tationen |
n = | 10 | 20 | 30 | 40 | 50 | 60 |
n | 10 s | 20 s | 30 s | 40 s | 50 s | 60 s |
n2 | 100 s | 400 s | 900 s | 1.6 ms | 2.5 ms | 3.6 ms |
n3 | 1 ms | 8 ms | 27 ms | 64 ms | 125 ms | 216 ms |
2n | 1 ms | 1 s | 18 min | 13 Tage | 36 J | 366 Jh |
3n | 59 ms | 58 min | 6.5 J | 3855 Jh | 108 Jh | 1013 Jh |
n! | 3.62 s | 771 Jh | 1016 Jh | 1032 Jh | 1049 Jh | 1066 Jh |
Wächst n um 1, so wächst 2n um den Faktor 2.Analoge Aussagen sind möglich bzgl. Speicherplatz.
Wächst n um 10, so wächst 2n um den Faktor 210 = 1024.
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
best case | günstigster Fall |
worst case | ungünstigster Fall |
average case | im Mittel |
Beispiel:
Minimumsuche in einem Array der Länge n
min = a[0]; for (i = 1; i < n; i++){ if(a[i] < min) min = a[i]; }
Laufzeit O(n) für | best case |
worst case | |
average case. |
for (i = 0; i < k; i++) { for (i = 0, i < k; i++) { for (j = 0; j < k; j++) { for (j = 0; j < k; j++) { brett[i][j] = 0; if (a[i] == a[j]) treffer = true; } } } }
k2 Schritte für k2 Daten | k2 Schritte für k Daten | |
O(n) -Algorithmus | O(n2) -Algorithmus |
Beispiel:
Lineare Suche im Array
i = 0; while (i < n) && (a[i] != x) { i++; }
Laufzeit: | best case | 1 Schritt | O(1) | |
worst case | n Schritte | O(n) | ||
average case | Schritte | O(n) |
Annahme für den average case:
Es liegt Permutation der Zahlen von 1 bis n vor.
Dann ist die mittlere Anzahl
= i | /TD> |
Beispiel:
Suche 0 in einem Array, bestehend aus Nullen und Einsen.
Laufzeit: | best case | 1 Schritt | O(1) | |
worst case | n Schritte | O(n) | ||
average case | i . 2 | O(1) |
Obacht:
Alle Laufzeitangaben beziehen sich jeweils auf einen konkreten Algorithmus A (für ein Problem P) = obere Schranke für Problem P.
Eine Aussage darüber, wie viele Schritte jeder Algorithmus für ein Problem P mindestens durchlaufen muss, nennt man untere Schranke für Problem P.
Beispiel: naives Pattern-Matching
char[] s = new char[N]; // Zeichenkette char[] p = new char[M]; // Pattern
Frage: Taucht Pattern p in Zeichenkette s auf?
for (i = 0; i <= N - M; i++) { // Index in Zeichenkette for (j = 0; (j < M) && (p[j] == s[i+j]); j++); // Index im Pattern if (j == M) break; // Erfolg }
Laufzeit best case: | O(1) | |||
Laufzeit worst case: | (N - M + 1) . M Vergleiche für | s | = | AAA...AB |
p | = | A...AB |
Sei n die Summe der Buchstaben in Pattern p und String s. Sei M = x . n und N = (1 - x) . n für 0 < x < 1.
Gesucht wird x, welches ((1 - x) . n - x . n + 1) . x . n = (n2 + n) . x - 2n2 . x2 maximiert.
Bilde 1. Ableitung nach x und setze auf 0: 0 = n2 + n - 4n2 . x
Beispiel:
Die Laufzeit von fib(n) beträgt:
Gesucht ist also ein , so dass für große n gilt:
Teile durch :
für n = 20 ist | 1.62n | 15.000 |
2n | 1.000.000. |