重现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)的θ界限

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).