32.2 Definition des O-Kalküls
 
  Laufzeit werden in der O-Notation in Abhängigkeit von der Problemgröße n (hier: n ist die Anzahl der Datenelemente) angegeben.

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)

Definition des O-Kalküls

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
 
balancierte Suchbaum
TBin(n) = O(log n)
Warum also ist das Suchen in einem binären Suchbaum O(log n)? Wir haben in Kap '28.12 Was ist ein 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 32.3 Abschätzungen für die Sortieralgorithmen
zur Startseite www.pohlig.de  (C) MPohlig 2004