求解递推T(n)= 2T(sqrt(n))

Question

我想解决以下重现关系:

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

我猜T(n) = O(log log n),但我不知道如何证明这一点.我如何证明这种复发可以解决O(log log n)？

Answer 1

一种想法是通过引入新的变量k来简化重现,使得2 ^k = n.然后,递归关系可以解决

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

如果你然后让S(k)= T(2 ^k),你会得到重复

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

请注意,这相当于

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

因为0 = O(1).因此,通过主定理,我们得到S(k)=Θ(k),因为我们得到a = 2,b = 2,并且d = 0并且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)是正确的.

希望这可以帮助!

Answer 2

您可以通过展开递归轻松解决此问题：

\n\n

\n\n

T(1) = a现在，当您可以找到合适的时，循环就会结束a。当a = 0或1它没有意义但当a=2你会得到：

\n\n

\n\n

将 代入k第一个方程的最新部分，您将得到 的复杂度O(log(n))。

\n\n

在这里检查其他类似的递归：

\n\n

\n
• T(n) = 2T(n^(1/2)) + log n
\n
• T(n) = T(n^(1/2)) + \xce\x98(lg lg n)
\n
• T(n) = T(n^(1/2)) + 1
\n

\n