2.5.1 Laufzeiteffizienz

Um die Laufzeiten von Algorithmen vergleichen zu können, ist es meist reizlos, alle Algorithmen zu implementieren und einfach die Laufzeiten zu messen, da sowohl die Codierung als auch das zugrundeliegende System (Hardware, Wahl der Sprache, Optimierungen des Compilers und so weiter) einen enormen Einfluß auf die Laufzeiten haben können; vergleiche dazu auch die Laufzeitunterschiede zwischen Java und C in der Beispiellösung Größter gemeinsamer Teiler.

Dazu kommt, daß man natürlich auch gerne die Arbeit vermeidet, etliche Algorithmen erst zu implementieren, um anschließend doch nur einen davon zu verwenden.

Gesucht wird also eine Möglichkeit, Aussagen zum Laufzeitverhalten von Algorithmen ohne deren Implementation zu machen.

Der erste Ansatz wäre, für einen gegebenen Satz von Eingaben einfach alle Anweisungen des Algorithmus anhand seiner Definition zu simulieren und alle ausgeführten Anweisungen zu zählen.

Das Zählen kann

erfolgen.

Eine nach bestimmten Gruppen aufgeschlüsselte Zählung kann deshalb interessant sein, weil nicht alle Anweisungstypen gleich aufwendig sind. Es gibt bestimmte ,,teure`` (also langsame ) und dagegen relativ ,,billige`` (schnelle) Operationen.

Die Details sind systemabhängig, aber allgemein kann man sagen:

Will man also eine recht feine Analyse eines Algorithmus durchführen, dann muß man die durchlaufenen Schritte mit einem Faktor gewichten, der den Aufwand beziehungsweise die Laufzeit des einzelnen Schritts reflektiert.

Auch wenn diese Gewichtung theoretisch vom konkreten Zielsystem abhängt, kann man doch davon ausgehen, daß ein Algorithmus schneller ist als ein zweiter, wenn er eine Gleitkommadivision durch wenige ganzzahlige Additionen ersetzen kann, wenn er ansonsten gleichwertig ist.

Ein Beispiel wäre folgende Optimierung: Ein gegebener Algorithmus benötigt einen Vergleich eines Wertes x mit der Wurzel eines Wertes y:

          |     ...       |
          +---------------+
          | x < sqrt(y) ? |
          |      |        |
          +- ja --- nein -+
          |      |        |
          | ...  |   ...  |
          +---------------+
          |     ...       |

Falls die berechnete Wurzel nur für diesen Vergleich benötigt wird, und nicht mehr im folgenden Teil des Algorithmus, dann kann man die Berechnung beschleunigen:

          |     ...       |
          +---------------+
          |   x*x < y ?   |
          |      |        |
          +- ja --- nein -+
          |      |        |
          | ...  |   ...  |
          +---------------+
          |     ...       |

Grund: wohl auf allen gängigen Systemen ist eine Multiplikation deutlich schneller als die Berechnung einer Wurzel.

www.wachtler.de