递归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 = 2 2 m或m = log 2 log 2 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 2 log 2 n）

将其扩展为一般情况。

在像T（n）= T（n / 2）+

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

log n）。