Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Zeitkomplexität

1. Erläuterung / Beschreibung
2. Landau-Notation
3. Berechnung des Zeitbedarfs mit Hilfe der Zeitkomplexität
    

1. Erläuterung / Beschreibung

Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. 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 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).
 

2. Landau-Notation

Da es sich bei uns in erster Linie um Algorithmen und nicht um Funktionen handelt, wird bei uns die Zeitkomplexität so geschrieben (Beispiele):

  O(n)             - für lineare Suche
  O(n2)            - Sortieren mit Bubble- bzw. Selectionsort
  O(n log n)       - Sortieren mit Quick- oder Mergesort

3. Berechnung des Zeitbedarfs mit Hilfe der Zeitkomplexität

Das Programm für die pythagoräischen Zahlentripel wird auf einen alten Computer gestartet. Als Parameter wird 600 eingegeben. Da dieser Rechner schon etwas betagt ist, braucht er dafür 80s. Es soll jetzt berechnet werden, wie lange der Computer braucht, wenn als Parameter 3000 eingegeben wird. Die Zeitkomplexität wird mit O(n³) gegeben.
 

Gegeben ist: n₁ = 600,   n₂ = 3000     das bedeutet, die Anzahl für n hat sich verfünffacht.

wegen O(n³)  bzw. t ~ n³ bedeutet das, dass die Zeit t₂ das 125-fache des alten Wertes t₁ ist (5³ = 125).

Damit ist t₂ das 125-fache von 80s gleich 10.000s! (Das sind rund 167 Minuten oder 2 Std. 47 min.)
 

Weblinks

1. Zeitkomplexität (Wikipedia)
2. Landau-Symbole (Wikipedia)

zurück