Effizienz (Informatik)

Begriff und Bedeutung

Die Effizienz eines Algorithmus beschreibt, wie sparsam er die Ressourcen Rechenzeit und Speicherplatz nutzt, um ein festgelegtes Problem zu lösen. Effiziente Algorithmen lösen ihr Problem schnell. Sie sind jedoch oft schwerer zu verstehen, weil sie auf ausgeklügelten Ideen beruhen.

Effizienz ist kein unveränderliches Merkmal eines Algorithmus. Sie wird auch von der konkreten Implementierung in einer Programmiersprache, der verwendeten Hardware und den Eingabedaten beeinflusst. Für vergleichbare Bewertungen verwendet man daher möglichst von diesen Einflüssen unabhängige Größen.

Bewertungsgrößen und Landau-Notation

Zentrale Bewertungsgrößen sind:

• Laufzeiteffizienz: Sie bewertet die Laufzeit anhand der benötigten Rechenschritte.
• Speichereffizienz: Sie bewertet den Speicherbedarf, der durch Variablen entsteht.

Die Landau-Notation, gelegentlich auch „Omikron-Kalkül“ genannt, dient dazu, Laufzeitverhalten und Platzbedarf überschlägig für große Eingabegrößen darzustellen. Dabei werden konstante Vorfaktoren vernachlässigt. Das ist sinnvoll, weil elementare Operationen auf unterschiedlichen Chipsets unterschiedlich viele Takte benötigen, sich aber meist nur um einen konstanten Faktor unterscheiden.

Die Landau-Notation sagt allerdings nicht unmittelbar aus, ob ein Algorithmus praktisch geeignet ist: In der Praxis werden häufig relativ kleine Eingaben verarbeitet, während die Notation besonders große Eingabegrößen betrachtet.

Theorie und praktische Eignung

In der theoretischen Informatik wird ein effizienter Algorithmus meist als ein Algorithmus verstanden, dessen Laufzeit polynomial in der Größe der Eingabe ist. Trotzdem kann ein solcher Algorithmus praktisch unbrauchbar sein, wenn der feste Exponent k im Polynom n^k zu groß ist.

Auch ein Linearzeit-Algorithmus kann ungeeignet sein, wenn sein konstanter Vorfaktor c in c · n zu groß ist. Deshalb kann Algorithmus A theoretisch deutlich effizienter als Algorithmus B sein, während in der Praxis dennoch B verwendet wird: Die Eingaben sind dann nicht groß genug, damit A seinen theoretischen Vorteil ausspielen kann.

Speicherbedarf und Abwägungen

Der Speicherbedarf einer Datenstruktur muss im Verhältnis dazu bewertet werden, wie häufig sie während eines Programmlaufs vorkommt. Eine Speicheroptimierung lohnt sich besonders, wenn viele Objekte eines Typs im Hauptspeicher angelegt oder dauerhaft gespeichert werden. Weniger Speicherverbrauch kann Kosten senken und den Systemdurchsatz erhöhen.

Speicher einzusparen kann jedoch bestimmte Zugriffe verlangsamen, etwa wenn Teilinformationen zusammengefasst und kompakt in Basistypen gespeichert werden. Dann müssen Teilinformationen beim Lesen dekodiert und beim Schreiben kodiert werden. Die Effizienz dieser Operationen sowie die Häufigkeit von Lese- und Schreibzugriffen sind getrennt zu berücksichtigen. Bei abstrakten Datentypen kann die interne Repräsentation teilweise auch ohne Zerlegung in Komponenten verarbeitet werden.

Ziel ist eine ausgewogene Lösung: Komplexität und Optimierungsaufwand müssen durch den Gewinn gerechtfertigt sein. Im Zweifelsfall ist eine klare Implementierung einer trickreichen vorzuziehen. Neben dem Ressourcenbedarf eines einzelnen Algorithmus zählt je nach Anforderungen die Effizienz des gesamten Systems.

Redundanz bei gespeicherten Objektzuständen soll möglichst vermieden werden, weil sie die Wartungsfreundlichkeit vermindert. Gezielt eingesetzte Redundanz kann aber in bestimmten Anwendungen die Zugriffsgeschwindigkeit auf Daten deutlich erhöhen.

Beurteilung von Algorithmen

Ob ein Algorithmus effizient ist, hängt von der Perspektive der Analyse und vom Wissen über die Komplexität des behandelten Problems ab. Eine grobe Beurteilung unterscheidet drei Fälle:

• Worst-Case: das schlechtestmögliche Verhalten bei der Lösung eines festgelegten Problems.
• Average-Case: ein durchschnittliches Verhalten bei der Lösung eines festgelegten Problems.
• Best-Case: das bestmögliche Verhalten bei der Lösung eines festgelegten Problems.

Für solche Beurteilungen sind Kenntnisse über Algorithmen und Komplexität erforderlich.