22794 zdj0 (3)

Równania rekurencyjne

W celu zmniejszenia rozmiaru zadania o połowę trzeba przejrzeć wszystkie elementy.

1 r: n;

2 whilr r I (lo bcj»in

' for i :    I to r do

U

4    I=0( 1);

5    r := Lr 2 J ;

6    cud

T( I) 0 T(n) T(Ln 2 J)+c/z dla n I Niech n 2 ^k. Wtedv

2cn-2c

T(2 ^k) T(2 ^k-‘ )+c2 ^k = T(2 ^k-^; )+c2 ^k-‘ +c2 ^k ...    T(2° )+c2° +c2 ¹ +...+c2 ^k'* -+ c2 ^A = c2(2 ^A -1) (2-1)

czvli T(n) 0 (n)

w

l*i ooi .unow.uiic kotiipntciow I

Wykład *

:_I