• Artikel
• Bearbeiten
• Historie
• Druckansicht

Laufzeit

Das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer, sondern viel mehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind, also z.B. ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit?). Die Laufzeit wird daher in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der O-Notation abgeschätzt. Eine genauere Laufzeitabschätzung von Rekursionsgleichungen bietet auch das Mastertheorem oder die Substitutionsmethode.

Bester Fall "best case" gibt an, wie lange der Algorithmus in jedem Fall braucht, also selbst für die Eingaben, auf denen er ideal arbeitet. Diese untere Schranke zur Lösung des Problems wird nur recht selten angegeben, da sie nur für wenige Fälle zutrifft und die best-case-Laufzeit natürlich in der für die schlechteren Fälle enthalten ist.

Mittlerer Fall "avarage-case" gibt die erwartete Laufzeit bei einer Gleichverteilung der Eingaben an. Da man allerdings bei realen Programmen selten von der Gleichverteilung der Eingaben ausgehen kann, ist auch diese Abschätzung nur bedingt nutzbar. Siehe auch: Amortisierte Laufzeitanalyse

Schlechtester Fall "worst-case" gibt an, wie lange der Algorithmus maximal braucht. Für viele Algorithmen gibt es nur wenige Eingaben, die diese worst-case-Laufzeit erreichen, weshalb sie nicht unbedingt eine realistische Abschätzung ist. Handelt es sich aber um Echtzeit-Systeme, so muss die worst-case-Laufzeit natürlich berücksichtigt werden.

Aussagen über die Laufzeit

• Man sucht nach relativen Aussagen über Skalierbarkeit
• Vernachlässigen kleiner Funktionsteile
  • aus n² + 5n wird n²
• Vernachlässigen von Konstanten
  • aus 5n² wird n²

Beispiele