28.5.2 Definition des O-Kalküls
 
  Statt der vom konkreten Rechner abhängigen Laufzeit eines Algorithmus' spricht man lieber von seinem Aufwand oder seiner Komplexität. Um die Komplexität eines Algorithmus quantitativ zu fassen, benutzt man das sog. O-Kalkül. So steigt der Aufwand z.B. beim Sortieren mit der Anzahl der Elemente, die sortiert werden sollen. Die O-Notation hilft, den Aufwand in ein Kalkül zu fassen: Wir legen zunächst fest, was wir unter O(f(n)) verstehen wollen. O(f(n)) ist eine Menge und wir beschreiben das "Aussehen" dieser Menge, in dem  wir sagen, wann ein Element in dieser Menge liegt:

Definition:

g(n) Î O(f(n)) genau dann, wenn es eine Konstante c Î R und ein n0 Î N gibt, so dass für alle n ≥ n0 gilt: g(n) ≤ c . f(n) 
 

Beispiele
5n2 + 15 Î O(n2), denn 5n2 + 15 < 6 n2 für n > 3
5n2 + 15 Î O(n3), denn 5n2 + 15 < n3 für n > 5
5n + 4 Î O(n), denn 5n + 4 < 6n für n > 4
2158 Î O(1), denn 2158 < 2159 * 1
 
 

Beispiel: Laufzeit T(n) für das Einsetzen eines Elementes in eine Datenstruktur mit n Elementen.

  • binärer Suchbaum, balanciert
    TBin(n)
    Î O(log n)
  • unsortierte Liste
    TLu(n)
    Î O(1)
  • sortierte Liste
    TLs
    Î O(n)
  • schlimmster Fall für einen binären Suchbaum
    TBin
    Î O(n)
balancierte Suchbaum
TBin(n) = O(log n)
Warum also ist das Suchen in einem binären Suchbaum O(log n)? Wir haben in Kap '26.11 Binärer Suchbaum' gesehen, dass zum Finden eines Elementes in einem binären Suchbaum maximal soviel Vergleiche nötig sind, wie der Baum tief ist. Ein ausgeglichener Binärbaum der Tiefe n besitzt 2n-1 Elemente. Umgekehrt: Die Tiefe eines ausgefüllten Binärbaumes mit n Elementen ist
log2(n+1) = loga(n+1)/loga2 < (loga2+logan)/loga2 = 1+logan = (log n)
Die Basis des Logarithmus ist unwichtig, da sie nur einen konstanten Faktor ausmacht.
 
unsortierte
TLu(n) = O(1)
Das Einfügen in eine unsortierte Liste ist unabhängig von n und kann etwa dadurch geschehen, dass das Element z.B. nur angefügt wird, so dass nur eine Anweisung nur einmal ausgeführt werden muss.
 
sortierte Liste
TLs = O(n)
Um ein Element in eine sortierte Liste einzufügen sind maximal n Vergleiche nötig. Der Aufwand a(n) < n, somit gilt a(n) < 1*n für alle n > 0. Daraus folgt die Behauptung.
 
schlimmste Fall für binären Suchbaum
TBin = O(n)
Im schlimmsten Fall (worst case) ist ein Binärbaum zu einer Liste der Länge n entartet. In diesem Fall kommt das Einsetzen in den Binärbaum einem Einsetzen in einer sortierten Liste gleich, was aber zur Folge hat, dass das Einfügen einen Aufwand von O(n) hat.
 
Rechnerunab-hängigkeit Unterschiedlich schnelle Rechner benötigen für ein und den selben Algorithmus unterschiedliche Zeiten. Aber das O-Kalkül ist unabhängig vom Rechner. Das kann man so einsehen. Der Aufwand für eine Anweisung ist bei einem langsameren Rechner  etwa c* Aufwand bei einem schnellen Rechner. Handelt es sich um den gleichen Algorithmus  und gilt für den Aufwand des schnelleren Rechners O(f(n)), so ist er für den langsameren Rechner O(c*f(n)), wobei c > 1 ist. Aber nach der Definition des O-Kalküls gilt O(n*f(n)) = O(f(n)).
 
Beispiel Matrizen-multiplikation  
    Cn x n = An x n * B n x n

Welche Laufzeit erfordert die Matrizenmultiplikation?

int i,j,k;
double ct;

for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    ct = 0.0;
    for (k = 0; k < n; k++) {
      ct += a[i}[k] * b[k][j];
    }
    c[i][j] = ct;
  }
}

 

Operationen:
 
   n3 Gleitkommamultiplikationen
n3 Additionen ("+=")
2* n3 doppelte Indizierung lesen ("[][]")
n2 doppelte Indizierung schreiben ("[][]")
n3 Variable k erhöhen und vergleichen
n2 Variable j erhöhen und vergleichen
n Variable i erhöhen und vergleichen

Aufwand: O(n3). Strassen hat bewiesen dass für den Aufwand sogar O(n2,81) möglich ist.

   
zu 28.5.3 Abschätzungen für die Sortieralgorithmen
zur Startseite www.pohlig.de  (C) MPohlig 2006