33237 zdj7 (5)

Analiza złożoności sortowania metoda scalania

Dla uproszczenia załóżmy, źe n jest potęgą dwójki n = 2^k

Analiza złożoności algorytmu "dziel i zwyciężaj" za pomocą równania rekinencyjnego na liczbę operacji dominujących. Tutaj;

T(n) = 0. jeśli n = 1

T(n) =2^łT(n/2) + n, jeśli n>1

Rozwiązanie równanie rekurencyjne na T(n) przez “iterowanie":

* 2T(n 2) 4*    n** 2 (2 T(n4) f n 2) -f n

2 ( 2 ( 2 T(n4 - n 4 )f + n

n

2 (. . . . 2 ( 2 T( /) + 2 ) 4 4 ) f.....i i

n /( m;,//

W\ll.nl 10 łV‘SMimmame koiMfnitctoU I >