解决递归:T(n)= T(n ^(1/2))+Θ(lg lg n) [英] Solve recurrence: T(n) = T(n^(1/2)) + Θ(lg lg n)

问题描述

开始学习算法.我知道如何从T(n) = Tf(n) + g(n)之类的定期重复发生"中找到theta记号.但是我迷失了这个

Started learning algorithms. I understand how to find theta-notation from a 'regular recurrence' like T(n) = Tf(n) + g(n). But I am lost with this recurrence: problem 1-2e:

T(n)= T(√ n)+&θ;(lg lg n)

T(n) = T(√n) + Θ(lg lg n)

如何选择找到theta的方法?嗯，这种复发是什么?我只是不太了解循环符号.

How do I choose the method to find theta? And what, uh, this recurrence is? I just do not quite understand notation-inside-a-recurrence thing.

推荐答案

一个有用的技巧是将n转换为其他内容，例如2 ^k .如果执行此操作，则可以将上面的内容重写为

One trick that might useful would be to transform n into something else, like, say, 2^k. If we do this, you can rewrite the above as

T(2 ^k )= T(2 ^k/2 )+Θ(log log 2 ^k )

T(2^k) = T(2^k/2) + Θ(log log 2^k)

= T(2 ^k )= T(2 ^k/2 )+Θ(log k)

= T(2^k) = T(2^k/2) + Θ(log k)

现在这看起来像是我们实际上可能能够解决的重复现象，因为我们可以将其扩展为

Now this looks like a recurrence that we might actually be able to solve, since we can expand this out as

T(2 ^k )= T(2 ^k/2 )+ log k = T(2 ^k/4 )+ log (k/2)+对数k

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

如果将其扩展到i倍，我们就会得到

If we expand this out i times, we get

T(2 ⁱ )= T(2 ^{k/2 i} )+ log k + log(k/2)+ log (k/4)+ ... +日志(k/2 ⁱ )

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

当2 ^{k/2 i} ≤时，此重复终止. 2(例如，在这种情况下我们达到了基本情况)，这发生在

This recurrence terminates when 2^k/2i ≤ 2 (say, at which case we reach a base case), which happens when

2 ^{k/2 i} = 2

2^k/2i = 2

k/2 ⁱ = 1

k = 2 ⁱ

i = lg k

换句话说，如果我们可以写n = 2 ^k ，那么最终结果将是

In other words, if we can write n = 2^k, then the net result will be

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

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

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

=Θ((lg k) ² )

= Θ((lg k)²)

并且由于我们知道n = 2 ^k ，所以这意味着k =Θ(log n)，因此将其替换为T(n)=Θ((log log n) ² ).

And since we know that n = 2^k, this means that k = Θ(log n), so substituting this in we get that T(n) = Θ((log log n)²).

这里的关键技巧是将n重写为2 ^k .其余的是标准技术.

The key trick here was rewriting n as 2^k. The rest is standard technique.

这有意义吗?好吧，如果您考虑一下，log log n就是写出log n所需的位数.在每次迭代中，您都将取数字的平方根，这将其表示中的位数减半.这将写出的位数减少了1.因此，第一次迭代将写出log log n位，第二个(log log n)-1，第三个(log log n)-2，依此类推.总的来说，该总和为&θ;((log log n) ² )，与直觉相符.

So does this make sense? Well, if you think about it, log log n is, among other things, the number of bits required to write out log n. At each iteration, you're taking the square root of the number, which halves the number of bits in its representation. This decreases the number of bits required to write out the number of bits in in by one. Consequently, the first iteration will write out log log n bits, the second (log log n) - 1, the third (log log n) - 2, etc. Overall, this summation is Θ((log log n)²), which matches the intuition.

希望这会有所帮助！

这篇关于解决递归:T(n)= T(n ^(1/2))+Θ(lg lg n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！