Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Grundlegende rekurrente Beziehungen

Wie wir in den nachfolgenden Kapiteln sehen werden, beruhen sehr viele Algorithmen auf dem Prinzip der rekursiven Zerlegung eines umfangreichen Problems in kleinere Probleme, wobei die Lösungen der Teilprobleme benutzt werden, um das ursprüngliche Problem zu lösen. Die Laufzeit eines solchen Algorithmus wird durch die Größe und Anzahl der Teilprobleme sowie durch den Aufwand bei der Zerlegung bestimmt. Im vorliegenden Abschnitt betrachten wir grundlegende Verfahren für die Analyse solcher Algorithmen und leiten Lösungen für einige Standardformeln her, die bei der Analyse von vielen der von uns untersuchten Algorithmen auftreten. Das Verständnis der mathematischen Eigenschaften der Formeln in diesem Abschnitt gibt einen Einblick in die die Leistungsfähigkeit betreffenden Eigenschaften von Algorithmen im gesamten Buch.

Aus der Natur eines rekursiven Programms selbst ergibt sich zwangsläufig, daß seine Laufzeit für Eingabedaten vom Umfang N von seiner Laufzeit für Eingabedaten von geringerem Umfang abhängt; dies kommt in einer mathematischen Formel zum Ausdruck, die rekurrente Relation genannt wird. Solche Formeln beschreiben die Leistungsfähigkeit des entsprechenden Algorithmus exakt; um die Laufzeit zu bestimmen, benutzen wir solche rekurrenten Beziehungen. Genauere Überlegungen, die sich auf spezielle Algorithmen beziehen, werden wir anstellen, wenn wir zu den Algorithmen kommen; einstweilen interessieren uns die Formeln und nicht die Algorithmen.

Formel 1. Die folgende rekurrente Beziehung entsteht bei einem rekursiven Programm, bei dem die Eingabedaten eine Schleife durchlaufen, wobei jedesmal ein Element aus ihnen entfernt wird:

CN = CN-1 + N, für N >= 2, mit C1 = 1.
Lösung: CN beträgt ungefähr N2/2.

Um eine solche rekurrente Beziehung aufzulösen, »ziehen wir sie auseinander«, indem wir sie auf sich selbst anwenden, und zwar in der folgenden Weise:

Formel

Die Berechnung der Summe 1 + 2 +...+ (N - 2) + (N - 1) + N ist elementar: Man erhält das oben angegebene Ergebnis, indem man die gleiche Summe, jedoch in umgekehrter Reihenfolge, Term für Term addiert. Dieses Ergebnis, das doppelt so groß ist wie der gesuchte Wert, besteht aus N Termen, die alle den Wert N + 1 haben.

Formel 2. Die folgende rekurrente Beziehung entsteht bei einem rekursiven Programm, das die Menge der Eingabedaten in einem Schritt halbiert:

CN = CN/2 + 1, für N >= 2, mit C1 = 0.
Lösung: CN beträgt ungefähr lg N.

In der angegebenen Form ist diese Gleichung nur dann sinnvoll, wenn N gerade ist, oder wenn wir annehmen, daß N/2 eine ganzzahlige Division bezeichnet. Nehmen wir einstweilen an, daß N = 2n ist, so daß die rekurrente Beziehung stets exakt definiert ist. (Beachten Sie, daß n = lg N gilt.) Doch dann läßt sich die rekurrente Beziehung sogar noch einfacher als unsere erste rekurrente Beziehung ausführlich schreiben:

Formel

Es zeigt sich, daß die exakte Lösung für allgemeines N von Eigenschaften der Binärdarstellung von N abhängt, doch CN ist ungefähr lg N für alle N.

Formel 3. Die folgende rekurrente Beziehung entsteht bei einem rekursiven Programm, das die Eingabedaten halbiert, doch vielleicht jedes Element der Eingabedaten betrachten muß:

CN = CN/2 + N, für N >= 2, mit C1 = 0.
Lösung: CN beträgt ungefähr 2N.

Durch Auflösen ergibt sich die Summe N + N/2 + N/4 + N/8 + . . . (wie oben ist dies nur dann exakt definiert, wenn N eine Zweierpotenz ist). Wenn die Reihe unendlich wäre, wäre das eine einfache geometrische Reihe, deren Summe genau 2N beträgt. Für allgemeines N hängt die exakte Lösung auch hier wieder von der Binärdarstellung von N ab.

Formel 4. Die folgende rekurrente Beziehung entsteht bei einem rekursiven Programm, das die Eingabedaten der Reihe nach durchläuft, bevor, während oder nachdem diese in zwei Hälften geteilt worden sind:

CN = 2CN/2 + N, für N >= 2, mit C1 = 0.
Lösung: CN beträgt ungefähr N lg N.

Dies ist unsere am häufigsten auftretende Lösung, denn sie ist typisch für viele Standard-Algorithmen vom Typ »Teile und Herrsche«.

Formel

Die Herleitung der Lösung erfolgt ganz ähnlich wie bei Formel 2, jedoch mit dem zusätzlichen »Trick«, daß beim zweiten Schritt beide Seiten der rekurrenten Beziehung durch 2n dividiert werden, um die rekurrente Beziehung »auseinanderzuziehen«.

Formel 5. Die folgende rekurrente Beziehung entsteht bei einem rekursiven Programm, welches die Eingabedaten in einem Schritt in zwei Hälften aufspaltet, von der Art unseres Programms zum Zeichnen eines Lineals im Kapitel 5.

CN = 2CN/2 + 1, für N >= 2, mit C1 = 0.
Lösung: CN beträgt ungefähr 2N.

Dies wird auf die gleiche Weise gezeigt wie bei Formel 4.

Leicht abgeänderte Varianten dieser Formeln, bei denen andere Anfangsbedingungen oder geringfügige Unterschiede im additiven Term vorliegen, können unter Anwendung der gleichen Lösungsmethoden behandelt werden; der Leser sei jedoch gewarnt, daß manche rekurrente Beziehungen, die ähnlich zu sein scheinen, in Wirklichkeit sehr schwer lösbar sein können. (Es gibt eine Reihe weiterentwickelter allgemeiner Techniken, um solche Gleichungen mathematisch exakt zu behandeln.) Wir werden in späteren Kapiteln auf einige kompliziertere rekurrente Beziehungen stoßen, schieben jedoch die Erörterung ihrer Lösung bis dahin auf.


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