4  Analyse

Literatur: Verschiedene Kapitel aus [CLR90]. Daneben Abschnitt 2.5 aus [Heu97].

Inhalt Analyse von Divide and Conquer ·lineare, O(nlogn), polynomielle Komplexität

• Aufstellen einer Rekurrenzgleichung:

  T(n)	=	O(1)   für n£ n0
  T(n)	=	a å i=1 T(ni) + D(n) + C(n)   für n > n0

• T(n): Laufzeit für Problem der Größe n, D und C Kosten für das Divide resp.  Conquer
• Vereinfachung: Teilprobleme gleichgroß, n₀ = 1. ferner f(n) = D(n) + C(n).
• Þ

  T(n) = a T(n/b) + f(n)

    a³ 1, b > 1 konstant
• Beispiel: Merge-Sort:
  • Zwei rekursive Aufrufe a=2
  • Halbierung der Problemgröße: b=2
  • Kosten des Mergens: O(n).

• Sei f(n) = D(n) + C(n) linear, f(n) = c n.

• Summe der Größen der Teilprobleme a n/b echt kleiner als n
• Þ a < b

• Summe der Größen der Teilpobleme = Größe des Ausgangsproblems:Þ a = b

• Beispiel: Mergesort

• Summe der Größen der Teilpobleme größer als das Ausgangsproblem Þ a > b