求解递归T(n)= 2T(sqrt(n)) [英] Solving the recurrence T(n) = 2T(sqrt(n))

问题描述

我想解决以下重复关系:

I would like to solve the following recurrence relation:

T(n)= 2T(√ n);

T(n) = 2T(√n);

我猜是T(n) = O(log log n)，但是我不确定如何证明这一点.我如何证明这种重复解决了O(log log n)?

I'm guessing that T(n) = O(log log n), but I'm not sure how to prove this. How would I show that this recurrence solves to O(log log n)?

推荐答案

一个想法是通过引入一个新变量k使得2 ^k = n来简化重复.然后，递归关系可以计算出

One idea would be to simplify the recurrence by introducing a new variable k such that 2^k = n. Then, the recurrence relation works out to

T(2 ^k )= 2T(2 ^k/2 )

T(2^k) = 2T(2^k/2)

如果然后让S(k)= T(2 ^k )，您将获得复发

If you then let S(k) = T(2^k), you get the recurrence

S(k)= 2S(k/2)

S(k) = 2S(k / 2)

请注意，这等同于

S(k)= 2S(k/2)+ O(1)

S(k) = 2S(k / 2) + O(1)

因为0 = O(1).因此，根据主定理，我们得到S(k)=&θ;(k)，因为我们有a = 2，b = 2和d = 0且log _b a> d

Since 0 = O(1). Therefore, by the Master Theorem, we get that S(k) = Θ(k), since we have that a = 2, b = 2, and d = 0 and log_b a > d.

由于S(k)=&θ;(k)并且S(k)= T(2 ^k )= T(n)，我们得到T(n)=&θ;(k ).由于我们选择了2 ^k = n，这意味着k = log n，因此T(n)=θ(log n).这意味着您最初对O(log log n)的猜测是不正确的，并且运行时仅是对数的，而不是双对数的.但是，如果仅进行一个递归调用，则运行时将为O(log log n).

Since S(k) = Θ(k) and S(k) = T(2^k) = T(n), we get that T(n) = Θ(k). Since we picked 2^k = n, this means that k = log n, so T(n) = Θ(log n). This means that your initial guess of O(log log n) is incorrect and that the runtime is only logarithmic, not doubly-logarithmic. If there was only one recursive call being made, though, you would be right that the runtime would be O(log log n).

希望这会有所帮助！

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