Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


6. Analyse von Algorithmen



Näherungsweise und asymptotische Ergebnisse

Oft sind die Ergebnisse einer mathematischen Analyse nicht exakt, sondern es sind Näherungen in einem exakten technischen Sinn: Das Ergebnis könnte ein Ausdruck sein, der aus einer Folge von kleiner werdenden Termen besteht. Ebenso, wie uns die innere Schleife eines Programms am meisten beschäftigt, widmen wir dem führenden Term (dem größten Term) eines mathematischen Ausdrucks die größte Aufmerksamkeit. Eben für derartige Anwendungen wurde die O-Schreibweise ursprünglich entwickelt, und wenn sie richtig angewandt wird, ermöglicht sie kurze und präzise Aussagen, die gute Näherungen für die mathematischen Ergebnisse liefern.

Nehmen wir zum Beispiel an, daß wir (nach entsprechender mathematischer Analyse) ermittelt haben, daß ein bestimmter Algorithmus eine innere Schleife aufweist, die (zum Beispiel) im Durchschnitt N lg N mal durchlaufen wird, außerdem einen äußeren Abschnitt, der N mal durchlaufen wird sowie einen Abschnitt für die Initialisierung, der einmal abgearbeitet wird. Nehmen wir weiterhin an, daß wir (nach sorgfältiger Untersuchung der Implementation) herausgefunden haben, daß für jede Wiederholung der inneren Schleife a0 Mikrosekunden, für den äußeren Abschnitt a1 Mikrosekunden und für den Initialisierungsteil a2 Mikrosekunden benötigt werden. Dann wissen wir, daß die durchschnittliche Laufzeit des Programms (in Mikrosekunden)

a0 N lg N + a1N + a2

beträgt. Doch ebenso gilt, daß die Laufzeit

a0 N lg N + O (N)

beträgt. (Der Leser kann dies anhand der Definition von O (N) nachprüfen.) Das ist wesentlich, denn wenn wir eine Näherungsweise Antwort geben wollen, so lautet diese, daß wir für große N die Werte von a1 oder a2 nicht zu bestimmen brauchen. Noch wichtiger ist, daß im exakten Ausdruck für die Laufzeit weitere Terme enthalten sein könnten, deren Analyse kompliziert ist; die O-Symbolik gibt uns die Möglichkeit, für große N eine Näherungsweise Antwort zu geben, ohne solche Terme berücksichtigen zu müssen.

Theoretisch haben wir keine wirkliche Garantie dafür, daß kleine Terme in dieser Weise vernachlässigt werden können, da die Definition der O-Symbolik absolut nichts über die Größe der Konstanten c0 aussagt; sie könnte sehr groß sein. Doch (auch wenn wir uns gewöhnlich nicht diese Mühe machen) gibt es in solchen Fällen normalerweise Wege, Schranken für die Konstanten anzugeben, die im Vergleich zu N klein sind. Daher sind wir im allgemeinen berechtigt, Größen zu vernachlässigen, die mittels O-Symbolik dargestellt sind, wenn ein genau definierter (größerer) führender Term angegeben wird. Wenn wir so vorgehen, haben wir die Gewißheit, daß wir einen solchen Beweis führen können, wenn es absolut notwendig ist, auch wenn wir es selten tun.

Tatsächlich verwenden wir, wenn eine Funktion f (N ) im Vergleich zu einer anderen Funktion g (N ) asymptotisch groß ist, in diesem Buch die (zweifellos nichttechnische) Terminologie »ungefähr f (N)«, um f (N ) + O ( g(N )) zu bezeichnen. Was wir an mathematischer Exaktheit verlieren, gewinnen wir an Klarheit, denn wir interessieren uns mehr für die Leistungsfähigkeit von Algorithmen als für mathematische Einzelheiten. In solchen Fällen kann der Leser gewiß sein, daß die fragliche Größe für große N (wenn nicht für alle N ) sehr nahe bei f (N ) liegt. Zum Beispiel können wir sogar dann, wenn wir wissen, daß eine Größe N (N - 1)/2 beträgt, sagen, daß sie »ungefähr« N2/2 ist. Dies ist schneller zu verstehen und weicht zum Beispiel für N=1000 nur um ein zehntel Prozent von der Realität ab. Der Verlust an Genauigkeit ist in solchen Fällen im Vergleich zu dem Genauigkeitsverlust bei der allgemeineren Anwendung von O (f (N)) unbedeutend. Unser Ziel ist eine sowohl exakte als auch knappe Ausdrucksweise bei der Beschreibung der Leistungsfähigkeit von Algorithmen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]