Geek asks and answers

Solve recurrence: T (n) = T (n ^ (1/2)) + Θ (log lg n)

Initial learning algorithms. I understand how to find the theta notation from "regular repetition" like that T(n) = Tf(n) + g(n). But I got lost with this repetition: problem 1-2e :

T (n) = T (? Radic; n) +? (lg lg n)

How to choose a method to search for theta? And what is this repetition? I just don’t quite understand the notation - intra-repetition.

+5
source share
2 answers

One trick that might come in handy would be to convert n to something else, such as 2 k . If we do, you can rewrite above as

T (2 k) = T (2 k/2) + & Theta; (log log 2 k)

= T (2 k) = T (2 k/2) + & Theta; (log k)

, ,

T (2 k) = T (2 k/2) + log k = T (2 k/4) + log (k/2) + log k

,

T (2 i) = T (2 k/2 i) + log k + log (k/2) + log (k/4) +... + log (k/2 i)

, 2 k/2 i & le; 2 (, ), ,

2 k/2 i= 2

k/2 i= 1

k = 2 i

i = lg k

, n = 2 k

T (n) = lg k + lg (k/2) + log (k/4) + log (k/8) +... 1

lg k + (lg k) - 1 + (lg k) - 2 + (lg k) - 3 +... + (lg k) - lg k

= & Theta; ((lg k) 2)

, n = 2 k , k = & Theta; (log n), , , , T (n) = & Theta; ((log n ) 2).

n 2 k. - .

? , , log log n - , , , log n. , . , . , log log n , (log log n) - 1, (log log n) - 2 .. , - & Theta; ((log log n) 2), .

, !

+6

, . lnln(n) O(lnln(n)). , big-O. :

enter image description here

, :

enter image description here,

, , enter image description here

lnln(n) :

enter image description here

- n k, T(...).

. , , 0, 1, 2. 2 : enter image description here

k , , :

enter image description here

, , : enter image description here

P.S.

+2

More articles:


All Articles