Robert Sedgewick: Algorithmen

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


6. Analyse von Algorithmen



Klassifikation von Algorithmen

Wie oben erwähnt wurde, besitzen die meisten Algorithmen einen Hauptparameter N, (gewöhnlich die Anzahl der zu verarbeitenden Datenelemente) der die Laufzeit am stärksten beeinflußt. Der Parameter N könnte der Grad eines Polynoms sein, die Größe einer zu sortierenden oder zu durchsuchenden Datei, die Anzahl der Knoten in einem Graph usw. Bei praktisch allen Algorithmen in diesem Buch ist die Laufzeit zu einer der folgenden Funktionen proportional:

1 Die meisten Anweisungen in der Mehrzahl der Programme werden einmal oder höchstens einige Male ausgeführt. Falls alle Anweisungen eines Programms diese Eigenschaft haben, sagen wir, daß seine Laufzeit konstant ist. Offensichtlich ist das die Situation, die bei der Entwicklung von Algorithmen angestrebt werden sollte.
log N Wenn die Laufzeit eines Programms logarithmisch ist, wird das Programm mit wachsendem N allmählich langsamer. Diese Laufzeit tritt gewöhnlich bei Programmen auf, die ein umfangreiches Problem lösen, indem sie es in ein kleineres Problem umwandeln, wobei sie den Umfang auf einen gewissen konstanten Anteil verringern. Für unsere Belange kann angenommen werden, daß die Laufzeit kleiner ist als eine »große« Konstante. Die Basis des Logarithmus beeinflußt die Konstante, jedoch nicht sehr: Hat N den Wert eintausend, so hat logN zur Basis 10 den Wert 3, zur Basis 2 den Wert 10; beträgt N eine Million, so ist logN jeweils doppelt so groß. Bei jeder Verdopplung von N wächst logN um einen gewissen konstanten Wert; eine Verdopplung des Wertes findet jedoch erst statt, wenn N auf N2 angewachsen ist.
N Wenn die Laufzeit eines Programms linear ist, entfällt im allgemeinen ein kleiner Anteil der Verarbeitung auf jedes Element der Eingabedaten. Wenn N eine Million beträgt, dann ist die Laufzeit ebenso groß. Jedesmal, wenn N sich verdoppelt, trifft das auch für die Laufzeit zu. Dies ist die optimale Situation für einen Algorithmus, der N Eingabedaten verarbeiten muß (oder N Ausgabewerte erzeugen muß).
N log N Diese Laufzeit tritt bei Algorithmen auf, die ein Problem lösen, indem sie es in kleinere Teilprobleme aufteilen, diese unabhängig voneinander lösen und dann die Lösungen kombinieren. Mangels eines passenderen Adjektivs (linearithmisch?) werden wir sagen, daß die Laufzeit eines solchen Algorithmus »N log N« beträgt. Wenn N eine Million ist, beträgt N log N vielleicht zwanzig Millionen. Wenn sich N verdoppelt, wird die Laufzeit mehr als doppelt so groß (aber nicht wesentlich mehr).
N2 Wenn die Laufzeit eines Algorithmus quadratisch ist, läßt er sich praktisch nur für relativ kleine Probleme anwenden. Quadratische Laufzeiten sind typisch für Algorithmen, die alle paarweisen Kombinationen von Datenelementen verarbeiten (eventuell in einer doppelt verschachtelten Schleife). Wenn N eintausend beträgt, ist die Laufzeit eine Million. Wenn N sich verdoppelt, vervierfacht sich die Laufzeit.
N3 Analog gilt, daß ein Algorithmus, der Tripel von Datenelementen verarbeitet (zum Beispiel in einer dreifach verschachtelten Schleife), eine kubische Laufzeit hat und praktisch nur für kleine Probleme verwendbar ist. Wenn N einhundert beträgt, ist die Laufzeit eine Million. Wenn sich N verdoppelt, erhöht sich die Laufzeit auf das Achtfache.
2N Bei wenigen Algorithmen mit exponentieller Laufzeit kann man erwarten, daß sie für praktische Zwecke geeignet sind, obwohl solche Algorithmen in natürlicher Weise als »gewaltsame« Lösungen von Problemen auftreten. Wenn N zwanzig beträgt, ist die Laufzeit eine Million. Bei jeder Verdopplung von N, wird die Laufzeit quadriert!

Die Laufzeit eines speziellen Programms ist meist ein konstantes Vielfaches eines dieser Terme (des »führenden Terms«) plus einiger kleinerer Terme. Die Werte des konstanten Faktors und der zusätzlichen Terme hängen von den Ergebnissen der Analyse und von Einzelheiten der Implementation ab. Grob gesagt hat der Koeffizient des führenden Terms etwas mit der Anzahl der Anweisungen in der inneren Schleife zu tun: Bei jedem Schritt der Entwicklung eines Algorithmus tut man gut daran, die Zahl solcher Anweisungen zu begrenzen. Für große N überwiegt der Einfluß des führenden Terms; für kleine N oder für sorgfältig gestaltete Algorithmen können mehrere Terme die Laufzeit spürbar beeinflussen und Vergleiche von Algorithmen komplizieren. In den meisten Fällen werden wir die Laufzeit von Programmen einfach als »linear«, »N log N«, »kubisch« usw. bezeichnen, wobei - auch wenn dies nicht ausdrücklich gesagt wird - klar ist, daß in Fällen, in denen die Effizienz sehr wichtig ist, eine eingehendere Analyse oder empirische Untersuchungen vorgenommen werden müssen.

>lg N
lg2N sqrtN N N lg N N lg2 N N3/2 N2
3 9 3 10 30 90 30 100
6 36 10 100 600 3.600 1.000 10.000
9 81 31 1.000 9.000 81.000 31.000 1.000.000
13 169 100 10.000 130.000 1.690.000 1.000.000 100.000.000
16 256 316 100.000 1.600.000 25.600.000 31.600.000 10 Milliarden
19 361 1000 1.000.000 19.000.000 361.000.000 1 Milliarde 1 Billion

Abbildung 6.1 Näherungsweise relative Werte von Funktionen.

Es treten noch einige weitere Funktionen auf. Zum Beispiel ist es richtiger, einen Algorithmus mit N2 Eingabedaten, der eine in N kubische Laufzeit hat, als N3/2-Algorithmus zu klassifizieren. Weiterhin weisen manche Algorithmen zweistufige Zerlegungen in Teilprobleme auf, was zu einer Laufzeit führt, die zu N log2 N proportional ist. Für beide genannte Funktionen sollte davon ausgegangen werden, daß sie für große N weit Näher bei N log N als bei N2 liegen.

Noch eine Bemerkung zur »log«-Funktion. Wie bereits erwähnt wurde, bewirkt die Basis des Logarithmus nur eine Änderung um einen konstanten Faktor. Da wir es oft mit analytischen Ergebnissen zu tun haben, die nur bis auf einen konstanten Faktor genau angegeben werden, ist es nicht von Bedeutung, welche Basis verwendet wird, so daß wir einfach von »log N« usw. sprechen. Andererseits liegt manchmal der Fall vor, daß Ideen besser erklärt werden können, wenn eine spezielle Basis benutzt wird. In der Mathematik tritt der natürliche Logarithmus (Basis e = 2,718281828...) so häufig auf, daß gewöhnlich eine spezielle Abkürzung verwendet wird: loge N == ln N. In der Informatik tritt der binäre Logarithmus (Basis 2) so häufig auf, daß normalerweise die Abkürzung log2 N == lg N benutzt wird. Zum Beispiel ist lg N, aufgerundet auf die Nächstgrößere ganze Zahl, die Anzahl der Bits, die für die Binärdarstellung von N benötigt werden.

In Abbildung 6.1 ist die relative Größe einiger dieser Funktionen angegeben: Für verschiedene N sind Näherungswerte von lg N, lg2 N, sqrtN, N, N lg N, N lg2 N, N3/2, N2 angegeben. Die quadratische Funktion dominiert klar, besonders für große N, und die Unterschiede zwischen den kleineren Funktionen entsprechen für kleine N vielleicht nicht den Erwartungen. Zum Beispiel wird N3/2 für sehr große N größer als N lg2 N, jedoch nicht für die kleineren Werte, die in der Praxis auftreten können. Diese Tabelle verfolgt nicht den Zweck, einen genauen Vergleich der Funktionen für alle N zu ermöglichen; dies bleibt Zahlen, Tabellen und Graphen vorbehalten, die sich auf spezifische Algorithmen beziehen. Doch sie vermittelt einen realistischen ersten Eindruck.


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