Konzept Laufzeitkomplexität

 
OInf

Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe (bzw. der Grösse des Problems). Man spricht hier auch von der asymptotischen Laufzeit und meint damit – in Anlehnung an eine Asymptote – das Zeitverhalten des Algorithmus für eine potenziell unendlich grosse Eingabemenge. Es interessiert also nicht der Zeitaufwand eines konkreten Programms auf einem bestimmten Computer für ein bestimmtes Problem, sondern vielmehr, wie der Zeitbedarf wächst, wenn mehr Daten zu verarbeiten sind. Die Frage ist also z.B., ob sich der Aufwand für die doppelte Datenmenge verdoppelt oder quadriert (Skalierbarkeit). Weniger wichtige Faktoren (z.B. Konstanten) spielen dabei keine Rolle und werden üblicherweise ignoriert.
Bei der Abschätzung der Zeitkomplexität geht man üblicherweise vom „worst case“ aus, man berücksichtigt also die Anzahl Rechenschritte, die benötigt werden, wenn das spezielle Problem innerhalb der Problemklasse maximal ungünstig gewählt ist.

Analogie

Auf das erste Feld eines Schachbretts wird ein Reiskorn gelegt. Auf jedes weitere Feld soll jeweils die doppelte Menge Reis platziert werden: Wie viele Reiskörner werden benötigt?
Mit einer einfachen Komplexitätsabschätzung (hier Reiskörner statt Verarbeitungsschritte) wird klar, dass es vermutlich auf der ganzen Welt nicht genug Reis dafür gibt.