Effizienz
Bedeutung
Ein Algorithmus A heißt effizienter als ein Algorithmus B, wenn der „Aufwand“ zur Ausführung von A geringer ist als der „Aufwand“ zur Ausführung von B und zwar für die zulässigen Eingabedaten.
Mit den gemachten Präzisierungen lässt sich der Aufwand einer Ausführung quantifizieren:
Zeitkomplexität: Wie viele Schritte braucht der Algorithmus in Abhängigkeit von den Eingabewerten?
Raumkomplexität: Wie viel Speicherplatz braucht der Algorithmus in Abhängigkeit von den Eingabewerten?
Bemerkungen
Oft wird nur erwartet, dass der Aufwand für alle bis auf endlich viele Eingaben geringer ist oder nur im Mittel über die zulässigen Eingaben.
Üblicherweise wird der Aufwand in Abhängigkeit von der Größe der Eingabe bestimmt, nicht des eigentlichen Werts.