algorithm - 递归T(n)= T(n ^(1/2))+ 1

我一直在观察这种复发，并想检查我是否采取了正确的方法。

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界

最佳答案

提示:假设n = 22m或m = log2log2n，并且您知道22m-1 * 22m-1 = 22m，因此，如果定义S(m)= T(n)，则S为:



将其扩展为一般情况。

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