Previous Up Next

4  Analyse

Literatur: Verschiedene Kapitel aus [CLR90]. Daneben Abschnitt 2.5 aus [Heu97].
Inhalt Analyse von Divide and Conquer lineare, O(nlogn), 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
)
  =
alogb n T ( 1) ) +
(logb n)-1
i=0
ai f(
n
bi
)
  =
alogb n T(1) +
(logb n)-1
i=0
ai f(
n
bi
)
  =
d nlogb a +
(logb n)-1
i=0
ai f(
n
bi
)
Spezialfall: lineare Zeitkomplexitt


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



a
b



i



 
  O(n)

Spezialfall: O(nlogn)

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



a
b



i



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

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


a
b



i



 
 
d nlogb a + c n



a
b



logb n



 
-1
a
b
-1
 
O





nlogb a + n


a
b



logb n



 






 
O


nlogb a + n
alogb n
blogb n



 
O ( nlogb a )


Page last (re-)generated May 21, 2003 (Martin Steffen)
Previous Up Next