zdj1 (3)

Równania rekurencyjne

Redukcja zadania do dwóch podzadań rozmiaru n/2 kosztem liniowej liczby operacji (algorytmy „divide-and-conquer").

T< 1) = 0

T( n) 2T(|_n 2 J)+c/? dla n 1 Niech n 2^k. Wtedv T(2 ^k ) = 2T(2 ^k-' )+c2 ^k = 2( 2T( 2 ^k_: )+c2 ^k*‘ ;+c2^k 2 ² T(2 ^k‘² >+02* +c2^k

» • •

2 * T( 2 ⁰ )+A-c2 ^k = 0 + cnlg n czvli T(n) = 0 fulu n)

Wykluci "

Pi oto .nilów .unc koiupiitei ow 1

* I