03 – Abschätzung des Rechenaufwandes

 

Sei T(n) die Anzahl auszuführender elementarer Operationen in Abhängigkeit von der Größe n der Eingabe, dann ist T(n) eine Beschreibung für die Laufzeit des Algorithmus.

Es gilt:

positive Funktion: T(n) > 0
positive Anzahl an Elementaroperationen: n > 0

Die Lösung eines Problems dauert immer länger als 0 Sekunden.

Landau-Symbole

Eine positive Funktion T(n) heißt O(f(n)), wenn es ein n0 gibt, so dass
T(n) ≤ c2 · f(n) für n ≥ n0; c2 > 0

Dann ist T(n) Element von O(f(n)), man schreibt T(n) = O(f(n)) “groß Oh von f von n”.

Beispiel:
Sei T(n) = 4 n2+n
Dann ist T(n) = O(f(n)) mit f(n) = n3, also T(n) = O(n3)
Aber es gilt auch: T(n) = O(n2)

Um in diesem Fall genauer zu differenzieren, wird ein weiteres Symbol eingeführt:

Wenn c1 · f(n) ≤ T(n) ≤ c2 · f(n) für alle n > n0, dann ist die Abschätzung “scharf” und wir schreiben:

T(n) = Θ(f(n))

Anwendung auf Selection Sort

Durch die äußere Schleife entstehen n-1 Durchläufe, also O(n). Durch die innere Schleife entstehen je nach aktuellem Stand der äußeren Schleife unterschiedlich viele Durchläufe, im Mittel n/2 Durchläufe, also O(n). Durch die Zuweisungen nach der Schleife entstehen weitere c Operationen. Diese können wir aber vernachlässigen. Da die Schleifen ineinander verschachtelt sind, müssen wir ihre Laufzeiten multiplizieren und erhalten: O(n2)

Typische Laufzeitverhalten von Algorithmen

  • O(log(n)) → logarithmische Laufzeit, Optimum
  • O(n) → lineare Laufzeit, z.B. Vergleiche
  • O(n · log(n)) zum Beispiel Sortieralgorithmen
  • O(n2) → quadratische Laufzeit
  • O(np) → polynomiale Laufzeit
  • O(an) → exponentielle Laufzeit, nicht realisierbar für größere Eingaben

Ähnliche Artikel

Kommentar verfassen