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))多次，这就是你的时间复杂度。

PS在这里解决了一些更难的复发。

Answer 2

提示：假设 n = 2 ^{2 m}或 m = log ₂ log ₂ n，你知道 2 ^{2 m-1} * 2 ^{2 m-1} = 2 ^{2 m}所以，如果你定义 S(m)=T(n) 你的S 将是：

S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log ₂ log ₂ n)

将其扩展到一般情况。

在像 T(n) = T(n/2) + 1 这样的递归中，在每次迭代中，我们将树的高度减半。这导致Θ（logn）。然而，在这种情况下，我们将输入数除以 2 的幂（而不是 2），所以结果是 Θ(log log n )。