zdj
3 (3)

Analiza algorytmu

T _ (//) = max \t(d ): d e D_u } =

nuty

2 dla			//
< T	f	n	\
nuty		?
\		_ ~ _

n = 1

+ 2

dla n > 1

Przyjmijmy, że n jest potęgą dwójki, czyli n

T    (n)=T(2*“')+ 2 =

mar V / mar \    /

= T (l^k~²)+ 2 + 2 =    =

E    ¹ mar \    /

= 2 + 2 +... + 2 = 2k = 2 log , n =

--v---'

k

= 2* Wtedy:

Wykład 9

Proąamowawe komputerów I

0 (log _: n)

li

&