Was ist die Effizienz eines Algorithmus?
Ein Algorithmus ist dann besonders effizient, wenn er möglichst wenig Ressourcen benötigt, also kaum Rechenzeit und Speicherplatz, um ein festgelegtes Problem zu lösen. Die Effizienz eines Algorithmus lässt sich auf verschiedene Arten messen: so wird in aller Regel die Laufzeiteffizienz und die Speichereffizienz als wesentliche Kennzahl herangezogen. Diese ist besonders gut in absoluter und relativer Darstellung mess- und damit auch interpretier- beziehungsweise auswertbar.
In einer konkreten Implementierung einer bestimmten Programmiersprache kann die Effizienz als Abhängigkeit von Hardware und den Eingabedaten ermittelt werden. Es ist aber auch möglich, eine Effizienzbewertung unabhängig von der Bewertungsgröße und der Implementierung zu erstellen. Mit der Landau Notation kann die Effizienz eines Algorithmus ermittelt werden.
Auf welchem Konzept beruht diese Effizienz?
Für präzise mathematische Effizienzanalysen werden die zugrunde liegenden Daten und ein Rechenmodell benötigt. Es wird geklärt, welche Datentypen existieren, wie die Daten abgelegt werden und welche Operationen zulässig sind. Dann wird ermittelt, welche Zeit eine gewisse Operation auf einem definierten Datentyp benötigt. Es wird dazu eine Random Access Maschine mit einfachem aber „unbegrenzten“ Speicher genutzt. Die Effizienz stellt sich als Speicher-Effizienz (Speicheraufwand), Subjective-Effizienz (Erfassungsaufwand) und Laufzeit-Effizienz (Zeitaufwand) dar.
Algorithmen können vollständig hinsichtlich Korrektheit und Effizienz analysiert werden. So kann auch das Sortieren, Suchen und Optimieren betrachtet werden. Datenstrukturen weisen unterschiedliche Effizienz in der Ablage und dem Zugriff auf. Entscheidend für die Güte eines Algorithmus ist vor allem die Betrachtung von großen Eingaben. Für praktischen Nutzen muss immer berücksichtigt werden, ob die Eingabe groß oder eher doch klein ist. In der Theorie ist aber ein asymptotische Verhalten wichtig.
Die Effizienz wird maschinenunabhängig in der Anzahl von Rechenschritten angegeben. Man kann diese nach Anzahl der Vergleiche und Additionen oder anderer Rechenoperationen aufschlüsseln. Auch die Anzahl an Speicherplätzen kann angegeben werden. So kann das Konzept der Effizienz eines Algorithmus maschinenunabhängig betrachtet werden. In der Theorie wird häufig eine Turingmaschine eingesetzt, die ein Band besitzt, auf dem sich Ein- und Ausgabe aufzeichnen lässt. Das Band ist unendlich lang und es werden die einzelnen Rechenschritte betrachtet.
