Effizienz (Informatik)

Die Effizienz eines Algorithmus ist seine Sparsamkeit bezüglich Ressourcen, Rechenzeit und Speicherplatz, die jener zur Lösung eines festgelegten Problems beansprucht. Jedoch sind effiziente Algorithmen meist schwerer zu verstehen, da sie oft auf ausgeklügelten Ideen beruhen. Effiziente Algorithmen sind schnell in der Lösung des entsprechenden Problems.

Effizienz von Algorithmen

Bewertungsgrößen für die Effizienzbewertung von Algorithmen

Von Implementierung, Hardware und Eingabedaten unabhängige Bewertungsgrößen

Effizienz ist nicht „bloßes Charakteristikum“ eines Algorithmus. Die Effizienz wird vielmehr auch durch die konkrete Implementierung in der jeweiligen Programmiersprache, des Weiteren durch die zugrundeliegende Hardware ebenso wie durch die Eingabedaten beeinflusst. Deshalb zieht man für die Effizienzbewertung von Algorithmen von Implementierung, Hardware und Eingabedaten unabhängige Bewertungsgrößen heran:

Laufzeiteffizienz: Bewertungsgröße ist die Laufzeit eines Algorithmus auf Basis der benötigten Rechenschritte
Speichereffizienz: Bewertungsgröße ist der Speicherbedarf durch Variablen

Die Landau-Notation

Da die Anzahlen der benötigten Takte für elementare Operationen für unterschiedliche Chipsets auf den (Main-)Boards von Rechnern variieren, sich in der Regel voneinander aber nur um einen konstanten Faktor unterscheiden und ferner der Laufzeit- und Platzbedarf für kleine Eingaben in der Regel unerheblich ist, nutzt man die sogenannte Landau-Notation, gelegentlich auch „Omikron-Kalkül“ genannt, um die Effizienz eines Algorithmus überschlägig zu ermitteln. Dadurch ist das Laufzeitverhalten und der Platzbedarf unter Vernachlässigung eines konstanten Vorfaktors für große Eingabegrößen darstellbar, was jedoch über eine Praxistauglichkeit des Algorithmus noch nichts aussagt, da in der Praxis meistens mit relativ kleinen Eingabegrößen gearbeitet wird, die Landau-Notation jedoch sehr große Eingabegrößen betrachtet.

Theorie trifft auf Praxis

Der Begriff effizienter Algorithmus wird in der theoretischen Informatik recht schwammig benutzt. Meist meint man damit einen Algorithmus, dessen Laufzeit polynomial in der Größe der Eingabe ist, aber auch solche Algorithmen können praktisch unbrauchbar sein, wenn beispielsweise der feste Exponent $k$ des zugehörigen Polynoms $n^{k}$ zu groß ist. Es gibt sogar Linearzeit-Algorithmen, die praktisch unbrauchbar sind, weil der konstante Vorfaktor $c$ in der Darstellung $c\cdot n$ zu groß ist. Somit kann es sein, dass, obwohl ein Algorithmus A in der Theorie deutlich effizienter ist als ein Algorithmus B, in der Praxis immer nur Algorithmus B verwendet wird, weil die zu bearbeitenden Eingabegrößen nicht groß genug sind, damit Algorithmus A seine Vorteile ausspielen kann.

Laufzeiteffizienz

Speichereffizienz

Die Menge belegten Speichers einer Datenstruktur muss immer im Verhältnis zur Häufigkeit ihres Auftretens zur Laufzeit eines Programms bewertet werden. Der Aufwand einer Optimierung ist häufig nur dann sinnvoll, wenn viele Objekte des betrachteten Typs im Hauptspeicher angelegt bzw. dauerhaft gespeichert werden. In diesem Fall kann durch Reduzierung des Speicherverbrauchs eine Senkung der Kosten einerseits und eine Erhöhung des Systemdurchsatzes andererseits erreicht werden.

Eine Reduzierung des Speicherverbrauchs von Objekten kann eine Verschlechterung der Ausführungsdauer bestimmter Zugriffe auf die zugrundeliegende Datenstruktur haben, nämlich dann, wenn Teilinformationen zusammengefasst werden, um in Basistypen kompakt gespeichert zu werden. Die Effizienz der eingeführten Kodierungsoperationen spielt hierbei eine Rolle. Die relative Häufigkeit bestimmter Zugriffe in einem typischen Programmlauf muss beachtet werden, um in der Summe optimal zu sein. Die Operationen auf Daten werden in zwei Kategorien eingeteilt: Lesen und Schreiben. Diese entsprechen dem Dekodieren und Kodieren der Teilinformationen und müssen deshalb getrennt betrachtet werden. Ein zusätzlicher Aspekt spielt durch das Modell des abstrakten Datentyps hinein: die interne Repräsentation kann gegebenenfalls ohne Umwandlung in die Komponenten verarbeitet werden.

Ziel ist, eine ausgewogene Lösung zu finden, die Vorteile auf einer Seite nicht mit Effizienzeinbußen auf der anderen Seite bezahlt. Aufwand und Komplexität müssen durch den erzielten Gewinn gerechtfertigt sein. Im Zweifelsfall ist die klare Implementierung der trickreichen vorzuziehen. Das heißt, nicht nur unmittelbarer Ressourcenbedarf des einzelnen Algorithmus zur Laufzeit wird betrachtet, sondern abhängig von den Anforderungen die Effizienz des gesamten Systems.

Ein weiteres Ziel ist die Vermeidung von Redundanz bei der Speicherung von Objektzuständen. Es ist auch zu beachten, dass Redundanz die Wartungsfreundlichkeit vermindert. Allerdings kann gerade gezielt eingesetzte Redundanz bei bestimmten Anwendungen die Zugriffsgeschwindigkeit auf Daten deutlich erhöhen.

Effizienzbewertungsauswertung und -beurteilung

Ob ein Algorithmus nun als effizient gelten kann oder nicht, hängt vor allem von der Perspektive ab, aus der man den Algorithmus analysiert und was man über die Komplexität des vom Algorithmus behandelten Problems weiß.

Unter Umständen kann es zu einer Grob-Beurteilung bei der Effizienzbewertung kommen:

Worst-Case – der Algorithmus zeigt das schlechtestmögliche Verhalten zur Lösung eines festgelegten Problems
Average-Case – der Algorithmus zeigt ein durchschnittliches Verhalten zur Lösung eines festgelegten Problems
Best-Case – der Algorithmus zeigt das bestmögliche Verhalten zur Lösung eines festgelegten Problems

Entsprechende Kenntnisse zu Algorithmen und Komplexität sind erforderlich, um zu derartigen Grobbeurteilungen zu gelangen.

Literatur

Armin P. Barth: Algorithmik für Einsteiger: Für Studierende, Lehrer und Schüler in den Fächern Mathematik und Informatik. 2., überarb. Aufl., Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-02281-5, „Kap.3 Effizienz von Algorithmen“: S. 95–135.
Volker Heun: Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2., verb. u. erw. Aufl., Vieweg+Teubner Verl., Wiesbaden 2003, ISBN 978-3-528-13140-1.
Christian Wagenknecht: Algorithmen und Komplexität. Fachbuchverl. Leipzig im Carl-Hanser-Verl., München 2003, ISBN 3-446-22314-2.
Ingo Wegener: Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer Verl., Berlin 2003, ISBN 3-540-00161-1.