O-Notation

Seien f,g : N N

f ist höchstens von der Größenordnung g

in Zeichen: f O(g)

falls n₀, c N existieren mit

n n₀ : f (n) c · g(n) .

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 + 12n ².

Dann ist f O(n ²)

Natürlich gilt auch: f O(n ⁷)

Die wesentlichen Klassen

log n n n · log n n ² n ³ n ⁴ ... 2ⁿ 3ⁿ n!

binäre lineare schlaues dummes Gleichungs- alle alle

Suche Suche Sortieren Sortieren system Teil- Permu-

lösen mengen tationen

Annahme: 1 Schritt dauert 1 s = 0.000001 s

n = 10 20 30 40 50 60 n

n ² 1.6 ms 2.5 ms 3.6 ms

n ³ 1 ms 8 ms 27 ms 64 ms 125 ms 216 ms

2ⁿ 1 ms 1 s 18 min 13 Tage 36 J 366 Jh

3ⁿ 59 ms 58 min 6.5 J 3855 Jh 10⁸ Jh 10¹³ Jh

n! 3.62 s 771 Jh 10¹⁶ Jh 10³² Jh 10⁴⁹ Jh 10⁶⁶ Jh

Für einen Algorithmus mit Laufzeit O(2ⁿ) gilt daher:

Wächst n um 1 , so wächst 2ⁿ um den Faktor 2 .
Wächst n um 10 , so wächst 2ⁿ um den Faktor 2¹⁰ = 1024 .
Ein 1000-mal schnellerer Computer kann eine um 10 Daten größere Eingabe in derselben Zeit bearbeiten.

Analoge Aussagen sind möglich bzgl. Speicherplatz.
Wir zählen nicht die Anzahl der Bytes, sondern betrachten das Wachstum des Platzbedarfs in Speicherplätzen in Abhängigkeit von der Größe der Eingabe.

Aussagen über Laufzeit und Platzbedarf beziehen sich auf

Analyse von for-Schleifen

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.

Beispiele:

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;
   }                                     }
}                                     }

k ² Schritte für k ² Daten k ² Schritte für k Daten

Analyse von while-Schleifen

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 O(n)

Annahme für den average case:
Es liegt Permutation der Zahlen von 1 bis n vor.
Dann ist die mittlere Anzahl

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 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 = (n ² + n) · x - 2n ² · x ² maximiert.

Bilde 1. Ableitung nach x und setze auf 0: 0 = n ² + n - 4n ² · x

Maximum liegt bei

Also können (n - n + 1) · n = n ² + n Vergleiche entstehen.

Die Laufzeit im worst case beträgt O(n ²) .

Analyse eines rekursiven Programms

Beispiel:

Die Laufzeit von fib(n) beträgt:

f (n) =

Offenbar gilt: f O(ⁿ) für ein < 2 (denn f (n) = f (n - 1) + f (n - 1) würde zu O(2ⁿ) führen).

Gesucht ist also ein , so dass für große n gilt:

= + + 1

Teile durch :

= + 1 + . Für n und > 1 geht 0.

= + 1 = + = 1.61803 (gemäß Formel - )

Das rekursive Fibonacci-Programm hat die Laufzeit O(1.62ⁿ) , wobei n der Wert des Inputs ist, nicht seine Länge!

für n = 20 ist 1.62ⁿ 2ⁿ