Effizienz (Informatik)

DieEffizienzeinesAlgorithmusist seine Sparsamkeit bezüglichRessourcen,Rechenzeit und Speicherplatz, die jener zur Lösung eines festgelegtenProblemsbeansprucht. Jedoch sind effiziente Algorithmen meist schwerer zu verstehen, da sie oft auf ausgeklügeltenIdeenberuhen. 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 konkreteImplementierungin der jeweiligenProgrammiersprache,des Weiteren durch die zugrundeliegendeHardwareebenso 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 dieLaufzeiteines Algorithmus auf Basis der benötigten Rechenschritte
• Speichereffizienz:Bewertungsgröße ist derSpeicherbedarfdurchVariablen

Die Landau-Notation

→Hauptartikel:Landau-Notation

Da die Anzahlen der benötigtenTaktefür elementareOperationenfür unterschiedlicheChipsetsauf den (Main-)Boards vonRechnernvariieren, 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 sogenannteLandau-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 dertheoretischen Informatikrecht 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örigenPolynoms$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 AlgorithmusAin der Theorie deutlich effizienter ist als ein AlgorithmusB,in der Praxis immer nur AlgorithmusBverwendet wird, weil die zu bearbeitenden Eingabegrößen nicht groß genug sind, damit AlgorithmusAseine Vorteile ausspielen kann.

Speichereffizienz

Die Menge belegten Speichers einerDatenstrukturmuss 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ührtenKodierungsoperationenspielt 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 desabstrakten Datentypshinein: 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 vonRedundanzbei 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 dieKomplexitätdes 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.