Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Rahmen

Der erste Schritt bei der Analyse eines Algorithmus besteht darin, die Daten zu charakterisieren, die als Eingabedaten für den Algorithmus verwendet werden sollen, und zu entscheiden, welcher Typ einer Analyse geeignet ist. Im Idealfall wäre man in der Lage, für eine beliebige gegebene Wahrscheinlichkeitsverteilung der möglichen Eingabedaten die entsprechende Verteilung der möglichen Laufzeiten des Algorithmus herzuleiten. Da wir jedoch nicht imstande sind, dieses Idealziel für einen nichttrivialen Algorithmus zu erreichen, konzentrieren wir uns normalerweise darauf, Schranken für die Leistungskenngrößen anzugeben. Dabei streben wir den Beweis an, daß die Laufzeit stets kleiner ist als eine gewisse »obere Schranke«, unabhängig von den Eingabedaten. Außerdem versuchen wir, die durchschnittliche Laufzeit für eine »zufällige« Eingabe herzuleiten.

Der zweite Schritt bei der Analyse eines Algorithmus ist die Bestimmung der abstrakten Operationen, auf denen der Algorithmus beruht, um die Analyse von der Implementation zu trennen. Somit trennen wir zum Beispiel die Untersuchung der Frage, wie viele Vergleiche ein Sortieralgorithmus durchführt, von der Bestimmung der Anzahl der Mikrosekunden, die ein bestimmter Computer zur Ausführung des Maschinencodes benötigt, den ein bestimmter Compiler für den Programmabschnitt if a[i] < v then... erzeugt. Beide Komponenten werden benötigt, um die tatsächliche Laufzeit eines Programms auf einem speziellen Computer zu ermitteln. Die erste wird durch die Eigenschaften des Algorithmus bestimmt, die zweite durch die Eigenschaften des Computers. Diese Trennung gibt uns oft die Möglichkeit, Vergleiche von Algorithmen anzustellen, die zumindest in gewissem Maße von speziellen Implementationen oder speziellen Computern unabhängig sind.

Während die Anzahl erforderlicher abstrakter Operationen im Prinzip groß sein kann, hängt die Leistungsfähigkeit der betrachteten Algorithmen gewöhnlich nur von wenigen Größen ab. Im allgemeinen ist es sehr einfach, die entscheidenden Größen für ein spezielles Programm zu identifizieren; ein Weg dazu besteht in der Benutzung einer »profilierenden« Option (»profiling«, in vielen Pascal-Implementationen verfügbar), um für einige Beispielläufe die Häufigkeitsverteilungen der einzelnen Anweisungen zu ermitteln. Im vorliegenden Buch konzentrieren wir uns auf die wichtigsten derartigen Größen für jedes Programm.

Als dritten Schritt führen wir die mathematische Analyse selbst durch, um für jede der grundlegenden Größen die Werte für den durchschnittlichen Fall und für den ungünstigsten Fall zu ermitteln. Es ist nicht schwierig, eine obere Schranke für die Laufzeit eines Programms zu finden; das Problem besteht darin, die beste obere Schranke zu bestimmen, als eine Schranke, die tatsächlich erreicht wird, wenn die ungünstigsten Eingabedaten verwendet würden. Dies liefert den ungünstigsten Fall; der durchschnittliche Fall erfordert gewöhnlich eine sehr komplizierte mathematische Analyse. Nachdem solche Analysen für die grundlegenden Größen einmal erfolgreich vorgenommen worden sind, ist es möglich, für jede Größe die zugehörige Zeit zu bestimmen und Ausdrücke für die Gesamtlaufzeit zu erhalten.

Im Prinzip kann die Leistungsfähigkeit eines Algorithmus oft mit beliebig hoher Genauigkeit analysiert werden, wobei sich Einschränkungen nur aus der Unsicherheit hinsichtlich der Leistungsfähigkeit des Computers oder aus Schwierigkeiten bei der Bestimmung der mathematischen Eigenschaften mancher abstrakter Größen ergeben können. Es lohnt sich jedoch selten, eine vollständige, detaillierte Analyse vorzunehmen, so daß wir immer bestrebt sind abzuschätzen, um auf Einzelheiten verzichten zu können. (Tatsächlich erweisen sich grob erscheinende Schätzungen oft als recht genau.) Solche groben Schätzungen lassen sich sehr oft leicht aus der alten Faustregel ableiten, welche da lautet: »90% der Zeit werden für 10% des Programms benötigt.« (In der Vergangenheit wurde diese Aussage für viele von 90% verschiedene Werte formuliert.)

Die Analyse eines Algorithmus ist ein zyklischer Prozeß des Analysierens, Schätzens und Verfeinerns der Analyse, bis der gewünschte Detailliertheitsgrad erreicht worden ist. Im übrigen sollte der Prozeß, wie im folgenden Kapitel erläutert wird, auch Verbesserungen bei der Implementation mit einbeziehen, und tatsächlich ergeben sich aus der Analyse oft Anregungen für solche Verbesserungen.

Unter Beachtung dieser Vorbemerkungen wird unsere Vorgehensweise darin bestehen, zwecks Klassifikation grobe Schätzungen für die Laufzeit unserer Programme zu ermitteln, wobei wir wissen, daß eine vollständigere Analyse für wichtige Programme bei Bedarf vorgenommen werden kann.


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