Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Berechnungskomplexität

Ein Ansatz zur Untersuchung der Leistungsfähigkeit von Algorithmen besteht darin, die Leistungsfähigkeit im ungünstigsten Fall zu studieren, wobei konstante Faktoren ignoriert werden, um die funktionale Abhängigkeit der Laufzeit (oder eines anderen Maßes) von der Anzahl der Eingabewerte (oder einer anderen Variablen) zu bestimmen. Diese Vorgehensweise ist vorteilhaft, da sie es gestattet, exakte mathematische Aussagen über die Laufzeit von Programmen zu beweisen: Zum Beispiel kann man sagen, daß die Laufzeit von Mergesort (siehe Kapitel 11) garantiert proportional zu N log N ist.

Der erste Schritt in diesem Prozeß bedeutet, den Begriff »proportional zu« mathematisch exakt zu fassen und gleichzeitig die Analyse eines Algorithmus von jeder speziellen Implementation zu trennen. Die Idee besteht darin, konstante Faktoren bei der Analyse zu vernachlässigen: Wenn wir wissen möchten, ob die Laufzeit eines Algorithmus proportional zu N oder zu log N ist, ist es in den meisten Fällen ohne Bedeutung, ob der Algorithmus auf einem Mikrocomputer oder auf einem Supercomputer realisiert werden soll. Auch ist unwesentlich, ob die innere Schleife sorgfältig mit nur wenigen Anweisungen oder schlecht mit vielen Anweisungen implementiert worden ist. Vom mathematischen Standpunkt aus sind diese Implementationen äquivalent.

Der mathematische Kunstgriff, mit dessen Hilfe dieser Gedanke exakt formuliert wird, wird O-Schreibweise genannt; diese ist wie folgt definiert;

Bezeichnung. Eine Funktion g(N) wird O (f (N)) genannt, falls es Konstanten c0 und N0 gibt, so daß, für alle N > N0 , g (N ) kleiner als c0f (N ) ist.

Diese Umschreibung des Begriffs »ist proportional zu« befreit den Analytiker von der Betrachtung der Einzelheiten maschinenspezifischer Merkmale. Außerdem ist die Aussage, daß die Laufzeit eines Algorithmus O (f (N)) ist, unabhängig von den Eingabedaten des Algorithmus. Da wir daran interessiert sind, den Algorithmus zu untersuchen, nicht aber die Eingabedaten oder die Implementation, ist die O-Schreibweise ein Nützliches Hilfsmittel, um obere Schranken für die Laufzeit anzugeben, die von den Einzelheiten der Eingabedaten und der Implementation unabhängig sind.

Die O-Schreibweise erweist sich als äußerst Nützlich, indem sie Analytikern hilft, Algorithmen nach ihrer Leistungsfähigkeit zu klassifizieren, und indem sie Entwickler von Algorithmen bei der Suche nach den »besten« Algorithmen unterstützt. Das Ziel der Untersuchung der Berechnungskomplexität eines Algorithmus besteht darin zu zeigen, daß seine Laufzeit O (f (N )) für eine gewisse Funktion f ist, und daß kein Algorithmus mit einer Laufzeit O (g (N )) mit einer »kleineren« Funktion g (N ) (einer Funktion mit limn->unendlich g (N)/f (N) = 0) existieren kann. Wir versuchen, für den ungünstigsten Fall sowohl eine »obere Schranke« als auch eine »untere Schranke« für die Laufzeit die Analyse zu ermitteln. Die Herleitung oberer Schranken läuft häufig auf das Zählen und Analysieren der Häufigkeit von Anweisungen hinaus (wir werden in den folgenden Kapiteln viele Beispiele hierfür sehen); der Nachweis unterer Schranken ist eine komplizierte Angelegenheit, die es erforderlich macht, sorgfältig ein Maschinenmodell zu konstruieren und zu bestimmen, welche grundlegenden Operationen von einem Algorithmus ausgeführt werden müssen, um ein Problem zu lösen (diesen Punkt werden wir jedoch nur selten streifen). Wenn Untersuchungen zu den Berechnungen zeigen, daß die obere Schranke eines Algorithmus seiner unteren Schranke entspricht, so können wir darauf vertrauen, daß der Versuch der Entwicklung eines grundlegend schnelleren Algorithmus nutzlos ist, und können uns auf die Implementation konzentrieren. Diese Vorgehensweise erwies sich in den vergangenen Jahren für die Entwickler von Algorithmen als sehr Nützlich.

Bei der Interpretation von Ergebnissen, die unter Benutzung der O-Schreibweise ausgedrückt wurden, muß man jedoch mit größter Vorsicht vorgehen. Dafür gibt es wenigstens vier Gründe: Erstens ist es eine »obere Schranke«, und die betreffende Größe könnte viel kleiner sein; zweitens kann es sein, daß die Eingabedaten, die den ungünstigsten Fall zur Folge haben, in der Praxis kaum auftreten; drittens ist die Konstante c0 unbekannt und muß nicht unbedingt klein sein; und viertens ist die Konstante N0 unbekannt und braucht ebenfalls nicht klein zu sein. Betrachten wir diese Gründe der Reihe nach.

Die Feststellung, daß die Laufzeit eines Algorithmus O (f (N)) ist, besagt nicht unbedingt, daß der Algorithmus jemals so viel Zeit benötigt. Sie sagt lediglich aus, daß es dem Analytiker zu beweisen gelang, daß niemals mehr Zeit benötigt wird. Die tatsächliche Laufzeit könnte stets wesentlich kürzer sein. Es wurde eine verbesserte Schreibweise entwickelt, um die Situation zu charakterisieren, wo zusätzlich bekannt ist, daß gewisse Eingabedaten existieren, für die die Laufzeit O (f (N )) ist; doch gibt es viele Algorithmen, für die es sehr kompliziert ist, Eingabedaten für den ungünstigsten Fall zu konstruieren.

Selbst dann, wenn die Eingabedaten für den ungünstigsten Fall bekannt sind, kann es sein, daß die tatsächlich in der Praxis vorkommenden Eingabedaten zu wesentlich kürzeren Laufzeiten führen. Viele äußerst Nützliche Algorithmen haben einen schlecht situierten ungünstigsten Fall. Zum Beispiel hat der vielleicht am weitesten verbreitete Sortieralgorithmus, Quicksort, eine Laufzeit von O (N2), doch kann man es so einrichten, daß die Laufzeit für die in der Praxis auftretenden Eingabedaten proportional zu N log N ist.

Die die in der O-Symbolik implizit enthaltenen Konstanten c0 und N0 verbergen oft Einzelheiten der Implementation, die in der Praxis von Bedeutung sind. Die Aussage, daß ein Algorithmus eine Laufzeit von O (f(N)) besitzt, sagt offensichtlich nichts über die Laufzeit aus, wenn N kleiner als N0 ist, und in c0 könnte eine große Menge »Spielraum« enthalten sein, um einen schlecht situierten ungünstigsten Fall zu vermeiden. Wir würden einen Algorithmus, der N2 Nanosekunden benötigt, einem Algorithmus vorziehen, für den logN Jahrhunderte erforderlich sind, doch auf der Grundlage der O-Schreibweise könnten wir diese Wahl nicht treffen. Abbildung 6.2 zeigt die Situation für zwei typische Funktionen mit realistischeren Werten der Konstanten, im Bereich 0 <= N <= 1.000.000. Die Funktion N3/2, die man irrtümlich für die größte der vier Funktionen hätte halten können, weil sie asymptotisch die größte ist, gehört in Wirklichkeit für kleine N zu den kleinsten, und sie bleibt so lange kleiner als N lg2 N, bis N einige zehntausend erreicht hat. Programme, deren Laufzeiten von Funktionen dieser Art abhängen, können nicht auf sinnvolle Weise verglichen werden, ohne sorgfältig auf konstante Faktoren und Einzelheiten der Implementation zu achten.

lg N 1/4N lg2 N 1/2N lg2 N N lg2 N N3/2
10 22 45 90 30
100 900 1.800 3.600 1.000
1.000 20.250 40.500 81.000 31.000
10.000 442.500 845.000 1.690.000 1.000.000
100.000 6.400.000 12.800.000 25.600.000 31.600.000
1.000.000 90.250.000 180.500.000 361.000.000 1.000.000.000

Abbildung 6.2 Der Einfluß konstanter Faktoren beim Vergleich von Funktionen.

Man sollte es sich auf jeden Fall gründlich überlegen, ehe man zum Beispiel einen Algorithmus verwendet, dessen Laufzeit O(N2) ist, anstelle eines anderen mit einer Laufzeit, die O(N) ist, doch man sollte ebensowenig blind dem Ergebnis der Komplexitätsuntersuchung folgen, das in der O-Schreibweise ausgedrückt wird. Für praktische Implementationen von Algorithmen des Typs, der im vorliegenden Buch betrachtet wird, sind Beweise anhand der Berechnungskomplexität oft zu allgemein, und die O-Symbolik ist zu ungenau, als das sie von Nutzen sein könnte. Die Untersuchung der Berechnungskomplexität muß als der allererste Schritt in einem fortschreitenden Prozeß der Verfeinerung der Analyse eines Algorithmus betrachtet werden, durch die mehr Details seiner Eigenschaften ermittelt werden. In diesem Buch konzentrieren wir uns auf die späteren Schritte, die enger mit realen Implementationen zusammenhängen.


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