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.
Definition des O-Kalküls |
||||||||||||||||||||||
Beispiele |
|
|||||||||||||||||||||
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 |
|
|||||||||||||||||||||
zu | 32.3 Abschätzungen für die Sortieralgorithmen | |||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2004 |