Mitschriften aus dem Unterricht

Komplexitaet von suchen

• gegeben ist ein feld mit n elementen
• Benchmarking ist nicht aussagekräftig
  • Nicht die Algorithmen, sondern die Umgebung (Computer, architektur, betriebssystem, etc.) wird dabei betrachtet
• Besser ist die Betrachtung in Einzelschritten des Algorithmus
  • Bestimmung in abstrakter Zeiteinheit
  • Unabhängig von environment

Beispiel anhand der Schritte der linearen suche

pos = 0
while pos < n and a[pos] != s
  pos = pos+1
return pos

• zuweisung
• n schleifendurchläufe á 4 einzelschritte
  • 2 tests
  • feldzugriff
  • addition
• letzter test
• rückgabe

2+n*4+3 = 5+4n schritte

Bester fall: n=0: 5 schritte

Aussagen über die Algorithmenlaufzeit

• Man sucht relative Vergleichbarkeit über skaliebarkeit
• Vernachlässigung von kleinen Funktionsteilen
  • 3n² + 2n -> 3n²
  • 2n * 5 -> 2n
• Vernachlässigung von Konstanten
  • 4n -> n
  • 2n² -> n²
• Reduktion auf den wesentlichen Term
• Wesentlichste Namen:
  • n² quadratisch
  • n³ qubisch
  • n^4 quartisch
  • 2^n exponentiel
  • log n logarithmisch
  • f! fakultativ

O-Notation

• f element aus O(g)
• f wächst genauso schnell wie g
  • Es seien f: ℕ → ℝ+ und g: ℕ → ℝ+ Funktionen.
  • Dann gilt:
  • f = Θ(g) genau dann, wenn n0 ∈ ℕ und c1, c2, ∈ ℝ existieren,
  • sodass für n ≤ n0:
  • c1 * g(n) ≤ f(n) ≤ c2*g(n)
• O-Notation ist ein linearer rechenkörper