2.5 Effizienz von Algorithmen

Ein wesentliches Merkmal eines Algorithmus ist seine Effizienz, insbesondere wenn man für ein gegebenes Problem mehrere Algorithmen zur Auswahl hat und sich sinnvoll entscheiden muß.

Die Effizienz kann aber nicht einfach als ein Kriterium betrachtet werden, sondern besteht letztlich aus:

Laufzeit- und Speichereffizienz sind genau genommen nicht alleine eine Eigenschaft des Algorithmus, sondern werden auch von der konkreten Implementation und der zugrundeliegenden Hardware beeinflußt (sowie von den konkreten Eingabedaten), zumindest sofern man unter Laufzeit tatsächlich eine Zeit in Sekunden versteht, beziehungsweise den Speicherbedarf in Byte ausdrückt.

Erstrebt wird dennoch eine Bewertung unabhängig von Implementation und Hardware. Dies wird erreicht, indem man die Zeit nicht mehr in Sekunden angibt, sondern stattdessen die benötigte Anzahl Rechenschritte (gegebenenfalls aufgeschlüsselt nach Anzahl Vergleiche, Anzahl Additionen etc.), und anstelle des tatsächlichen Speicherbedarfs eine Anzahl Speicherplätze unbestimmter Größe für die Variablen berechnet; dazu später mehr.

In vielen Algorithmen ist eine irgendwie geartete Problemgröße als freier Parameter enthalten (,,Wieviele Elemente sind zu sortieren¿`, ,,Aus wievielen Elementen soll ein bestimmtes herausgesucht werden¿`, ,,Wie groß ist eine Zahl, die in Primzahlen zerlegt werden soll¿`). Diese Problemgröße geht in aller Regel stark in das Laufzeit- und Speicherverhalten ein. Deshalb wird die Effizienz in Abhängigkeit dieser Problemgröße angegeben.

Die kognitive Effizienz ist auf den ersten Blick alleine vom Algorithmus abhängig, weil die Implementation ja erst anschließend kommt. Dennoch ist sie von der jeweiligen Denkweise des Lesers stark beeinflußt, und die wiederum ist ganz klar abhängig von der Programmiersprache (oder dem dahinter stehenden Paradigma), mit der der Leser vertraut ist: ein typischer Algorithmus aus der linearen Algebra wird von einem langjährigen Fortranprogrammierer leichter erfaßt werden als von einem Programmierer, der mit Smalltalk aufgewachsen ist; bei einem rekursiven Algorithmus zum Abarbeiten einer Liste mag es umgekehrt sein2.5.



Unterabschnitte
www.wachtler.de