algorithm - 重复 T(n) = T(n^(1/2)) + 1

Question

我一直在关注这种复发情况，想检查一下我是否采取了正确的方法。

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

所以答案是 n^(1/2) 的 theta 边界

Answer 1

这里介绍了如何在没有任何提示的情况下仅使用数学就可以找到答案。

开始展开递归: .

递归会在某个点停止，所以我们必须找到一个合理的停止点。尝试 0、1、2，你会发现 2 看起来不错，因为你可以很容易地求解方程: .

解决它，你得到 .

因此递归将继续 log(log(n)) 次，这就是您的时间复杂度。

P.S. 解决了稍微难一点的复发问题here .