Previous Contents Next

4   Analyse

Literatur: Verschiedene Kapitel aus [CLR90]. Daneben Abschnitt 2.5 aus [Heu97].
Inhalt Analyse von Divide and Conquer lineare, O(nlog n), polynomielle Komplexitt
Laufzeitanalyse fr Divide & Conquer
Lsen der Rekurrenzgleichung


Sei n = bk. Auflsen durch Iteration.
T(n) =
a T(
n
b
) + f(n)
  =
a2 T(
n
b2
) + a f(
n
b
) + f(n)
...
  =
ak T(
n
bk
) +
k-1
i=0
ai f(
n
bi
)
  =
a
logb n
 
T



n
b
logb n
 




+
(logb n)-1
i=0
ai f(
n
bi
)
  =
a
logb n
 
T(1) +
(logb n)-1
i=0
ai f(
n
bi
)
  =
d n
logb a
 
+
(logb n)-1
i=0
ai f(
n
bi
)
Spezialfall: lineare Zeitkomplexitt


T(n) =
d n
logb a
 
+
(logb n)-1
i=0
ai f(
n
bi
)
  =
d n
logb a
 
+
(logb n)-1
i=0
c ai
n
bi
  =
d n
logb a
 
+ c n
(logb n)-1
i=0



a
b



i



 
  O(n)

Spezialfall: O(nlog n)




T(n) =
d n
logb a
 
+
(logb n)-1
i=0
c ai
n
bi
  =
d n
logb a
 
+ c n
(logb n)-1
i=0



a
b



i



 
  =
d n + c n
(logb n)-1
i=0
1
  O(nlog n)
Spezialfall: polynomiale Laufzeit
T(n) =
d n
logb a
 
+
(logb n)-1
i=0
c


a
b



i



 
 
d n
logb a
 
+ c n



a
b



logb n



 
-1
a
b
-1
 
O





n
logb a
 
+ n


a
b



logb n



 






 
O



n
logb a
 
+ n
a
logb n
 
b
logb n
 




 
O
n
logb a
 



January 23, 2001
Previous Contents Next