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 |
|
|||||||||||||||||||||
Beispiel: Laufzeit T(n) für das Einsetzen eines Elementes in eine Datenstruktur mit n Elementen.
|
||||||||||||||||||||||
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 |
|
|||||||||||||||||||||
zu | 28.5.3 Abschätzungen für die Sortieralgorithmen | |||||||||||||||||||||
zur Startseite | www.pohlig.de (C) MPohlig 2006 |