Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Für die meisten Probleme stehen viele unterschiedliche Algorithmen zur Verfügung. Wie soll man die beste Implementation auswählen? Dies ist gegenwärtig ein gut erforschtes Gebiet der Informatik. Wir werden oft Gelegenheit haben, uns auf Forschungsergebnisse zu berufen, die die Leistungsfähigkeit grundlegender Algorithmen beschreiben. Der Vergleich von Algorithmen kann jedoch sehr kompliziert sein, weshalb gewisse allgemeine Richtlinien von Nutzen sind.

Im allgemeinen haben die von uns zu lösenden Probleme eine natürliche »Größe« (im Normalfall die zu verarbeitende Datenmenge), die wir gewöhnlich mit N bezeichnen. Wir möchten die aufzuwendenden Ressourcen (meist die benötigte Zeit) als Funktion von N beschreiben. Wir interessieren uns für die zu erwartende Zeit, die ein Programm im durchschnittlichen Fall bei »typischen« Eingabedaten benötigt, und für die Zeit, die ein Programm im ungünstigsten Fall bei der denkbar ungünstigsten Konfiguration der Eingabedaten benötigen würde.

Einige der Algorithmen in diesem Buch sind sehr gut erforscht, so gut, daß exakte mathematische Formeln für die durchschnittliche Laufzeit und die Laufzeit im ungünstigsten Fall bekannt sind. Solche Formeln werden hergeleitet, indem das Programm sorgfältig untersucht wird, um die Laufzeit als Funktion grundlegender mathematischer Größen auszudrücken, und indem dann eine mathematische Analyse der betreffenden Größen vorgenommen wird. Andererseits sind die leistungsbezogenen Eigenschaften für andere Algorithmen in diesem Buch überhaupt nicht erforscht, teils weil ihre Analyse zu ungelösten mathematischen Fragen führt oder weil bekannte Implementationen zu komplex sind, als daß eine detaillierte Analyse sinnvoll wäre, oder (was am wahrscheinlichsten ist) weil die auftretenden Typen von Eingabedaten nicht genau charakterisiert werden können. Die meisten Algorithmen sind irgendwo zwischen diesen Extremfällen einzuordnen: Einige Tatsachen über ihre Leistungsfähigkeit sind bekannt, doch sie sind noch nicht wirklich vollständig analysiert.

Bei dieser Analyse spielen einige wichtige Faktoren eine Rolle, die gewöhnlich vom Programmierer nicht beeinflußt werden können. Erstens werden Pascal-Programme für einen gegebenen Computer in Maschinencode übersetzt, und es kann eine schwierige Aufgabe sein, selbst für eine einzige Pascal-Anweisung genau zu berechnen, wieviel Zeit für ihre Ausführung benötigt wird (insbesondere in einem System, in dem die Ressourcen geteilt werden, so daß sogar für ein und dasselbe Programm die Kenngrößen der Leistung variieren können). Zweitens sind viele Programme äußerst empfindlich gegenüber Änderungen ihrer Eingabedaten, und die Leistung kann in Abhängigkeit von der Eingabe sehr unterschiedlich sein. Der durchschnittliche Fall könnte eine mathematische Fiktion sein, die für die tatsächlichen Daten - mit denen das Programm verwendet wird - nicht repräsentativ ist, und der ungünstigste Fall könnte eine ausgefallene Konstruktion sein, die in der Praxis niemals auftreten würde. Drittens sind viele Programme, die von Interesse sind, noch nicht gut erforscht, und spezifische mathematische Ergebnisse sind eventuell nicht verfügbar. Schließlich liegt oft der Fall vor, daß Programme überhaupt nicht vergleichbar sind: Das eine läuft bei einer bestimmten Art von Eingabe effizienter ab, das andere unter anderen Bedingungen.

Ungeachtet der obigen Bemerkungen ist es oft möglich, genau vorherzusagen, wieviel Zeit ein bestimmtes Programm benötigt, oder auszusagen, daß ein Programm in bestimmten Situationen besser geeignet ist als ein anderes. Aufgabe des Algorithmenanalytikers ist es, soviel Informationen wie möglich über die Leistungsfähigkeit von Algorithmen zu erlangen; Aufgabe des Programmierers ist es, solche Informationen bei der Auswahl von Algorithmen für spezielle Anwendungen zu Rate zu ziehen. Im vorliegenden Kapitel konzentrieren wir uns auf die idealisierte Welt des Analytikers; im nächsten erörtern wir praktische Fragen der Implementation.


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