我想解决以下递归关系：
T(n) = 2T(√n)；
我猜是这样T(n) = O(log log n)，但我不确定如何证明这一点。我将如何证明这种重复可以解决O(log log n)？
问问题
22573 次
2 回答
11
一个想法是通过引入一个新变量 k 来简化递归，使得 2 k = n。然后，递归关系计算为
T( 2k ) = 2T( 2k/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) 是正确的。
希望这可以帮助！
于 2013-11-05T01:02:31.557 回答
5
您可以通过展开递归轻松解决此问题：
现在重复将在何时结束T(1) = a，您可以找到合适的a. 什么时候a = 0或1它没有意义，但是什么时候a=2你会得到：
代k入第一个等式的最新部分，您将得到 的复杂度O(log(n))。
在此处检查其他类似的递归：
于 2015-12-16T10:41:08.410 回答