Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Analyse des durchschnittlichen Falles

Ein anderer Zugang zur Untersuchung der Leistungsfähigkeit eines Algorithmus ist die Betrachtung des durchschnittlichen Falles. In der einfachsten Situation können wir die Eingabedaten für den Algorithmus exakt charakterisieren: Zum Beispiel könnte ein Sortieralgorithmus mit einem Feld aus N zufälligen ganzen Zahlen operieren, oder ein geometrischer Algorithmus könnte eine Menge von N zufälligen Punkten in der Ebene mit Koordinaten zwischen 0 und 1 verarbeiten. Dann berechnen wir die durchschnittliche Anzahl der Ausführung jeder Anweisung, und berechnen die durchschnittliche Laufzeit des Programms, indem wir jede Häufigkeit einer Anweisung mit der für diese Anweisung benötigten Zeit multiplizieren und die Produkte addieren. Bei dieser Vorgehensweise treten jedoch wenigstens drei Schwierigkeiten auf, die wir nacheinander betrachten.

Erstens kann es bei manchen Computern sehr kompliziert sein, den exakten Zeitaufwand zu bestimmen, der für jede Anweisung erforderlich ist. Noch schlimmer ist, daß dieser Zeitaufwand Veränderungen unterliegt, und ein großer Teil der ausführlichen Analyse, die für einen Computer vorgenommen wurde, möglicherweise für die Laufzeit des gleichen Algorithmus auf einem anderen Computer überhaupt nicht brauchbar ist. Dies ist genau die Art von Problemen, die durch Untersuchungen zur Berechnungskomplexität vermieden werden soll.

Zweitens ist die Analyse des durchschnittlichen Falls selbst oft eine schwierige mathematische Aufgabe, die komplizierte und detaillierte Überlegungen erfordert. Die Natur der mathematischen Hilfsmittel, die für den Nachweis oberer Schranken benötigt werden, ist normalerweise weniger kompliziert, da sie nicht so präzise sein müssen. Bei vielen Algorithmen ist die Leistungsfähigkeit im durchschnittlichen Fall unbekannt.

Drittens, und dies ist die größte Schwierigkeit, charakterisiert bei der Analyse des durchschnittlichen Falls das Modell der Eingabedaten möglicherweise nicht genau die in der Praxis auftretenden Eingabedaten, oder es gibt eventuell gar kein natürliches Modell der Eingabedaten. Wie sollte man die Eingabedaten für ein Programm charakterisieren, welches natürlichsprachigen Text verarbeitet? Andererseits würde sicher kaum jemand etwas gegen die Benutzung solcher Eingabedatenmodelle einwenden, wie einer »zufällig geordneten Datei« für einen Sortieralgorithmus oder einer »zufälligen Menge von Punkten« für einen geometrischen Algorithmus; für solche Modelle ist es möglich, mathematische Ergebnisse herzuleiten, die eine genaue Vorhersage der Leistungsfähigkeit von in realen Anwendungen ablaufenden Programmen gestatten. Obwohl die Herleitung solcher Ergebnisse normalerweise über den Rahmen dieses Buches hinausgeht, werden wir einige Beispiele angeben (siehe Kapitel 9) und dort, wo es zweckmäßig ist, diesbezüglich Ergebnisse anführen.


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