Effizienz (Informatik)
Effizienz (auch engl. Performance // bzw. Performanz) bezeichnet in der Informatik die Leistung von Programmen und Hardware bezüglich des Bedarfs an Betriebsmitteln und der Qualität der Ausgabe. Meistens ist damit die Datenrate gemeint, also die Menge von Daten die innerhalb einer bestimmten Zeitspanne verarbeitet werden kann. Im Gegensatz zur Zeitkomplexität bezieht sich die Effizienz nicht auf einen abstrakten Algorithmus, sondern auf ein konkretes Programm auf einem konkreten Computer.
Da es nicht sinnvoll ist, einen Algorithmus nur bzgl. einer einzigen Eingabe zu untersuchen, betrachtet man seine Effizienz bzgl. aller Eingaben. Da die Laufzeit und der Platzbedarf mit der Größe der Eingabe erwartungsgemäß zunimmt, misst man die Effizienz meist bzgl. der Eingabegröße. Die Effizienz ist damit eine Funktion, deren Parameter die Eingabegröße ist.
Da die Zeit in Takten gemessen wird, die von Rechnergeneration zu Rechnergeneration wächst, misst man die Zeit in Takten. Da aber auch die Zahl der nötigen Takte für elementare Operationen von Rechnerarchitektur zu Rechnerarchitektur schwankt, sich in der Regel aber nur um einen konstanten Faktor unterscheidet und ferner der Laufzeit- und Platzbedarf für kleine Eingaben in der Regel unerheblich ist, nutzt man meist die Landau-Notation, die vor allem das Laufzeitverhalten und den Platzbedarf unter Vernachlässigung eines konstanten Vorfaktors für große Eingabegrößen berücksichtigt, um die Effizienz eines Algorithmus anzugeben.
Man unterscheidet bei der Effizienz den
- Worst-Case, der das schlechtmöglichste Verhalten bzgl. Zeit- bzw. Platzbedarf abbildet,
- Average-Case, der das durchschnittliche Verhalten bzgl. Zeit- bzw. Platzbedarf abbildet und machmal auch den
- Best-Case, der das bestmögliche Verhalten bzgl. Zeit- bzw. Platzbedarf abbildet.
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ß. Die Landau-Notation liefert für die meisten Fälle eine Möglichkeit Algorithmen bzgl. ihrer Effizienz zu vergleichen, sagt aber seltener direkt etwas darüber aus, ob die Algorithmen auch in der Praxis tauglich sind.
Abhängig von der Implementierung und vom zugrundeliegenden System können manche Algorithmen eine bessere Leistung zeigen als solche, die theoretisch optimal wären. Bei Sortierverfahren ist zum Beispiel entscheidend, wie zeitaufwendig das Lesen und Schreiben eines Datensatzes ist: Sollen große Datenbestände auf Magnetbändern sortiert werden, eignet sich z.B. Mergesort als Verfahren besser als Quicksort. Für Daten, die in den Arbeitsspeicher passen, ist Quicksort dagegen meistens das beste Verfahren.
siehe auch: Lasttest (Computer)