zdj
9 (3)

Równania rekurencyjne

Rozmiar problemu jest zmniejszany o połowę stałym kosztem.

1    r := n:

2    while r 1 do begin

3    i = 0(1):

4    r := Lr 2_|:

5    end;

T(1) = 0 T(n) = T(Ln 2 J)+c dla n 1 Niech n = 2 ^k . Wtedy

T(2^k ) = T(2 ^k*‘ )+c = T(2 ^k'^: )+c+c ... = T(2⁰ )+kc = c la. n

W

czyIi T(n) = © (1« n)

Wykład Pi osraiuowaiue komputerów I 20