相关疑难解决方法(0)

我一直在看这个重复,并想检查我是否采取了正确的方法.

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

我试图找到重现的时间复杂性:

T(n)= 2T(n ^1/2)+ log n

我非常接近解决方案,但是,我遇到了障碍.我需要解决:

n ^{(1/2 k)} = 1

为了简化我的替换模式.我不是在寻找复发的答案,只是一个解决方案k.

开始学习算法.我理解如何从'常规复发'中找到theta-notation T(n) = Tf(n) + g(n).但是我对这种复发感到迷茫:问题1-2e:

T(n)= T(√n)+Θ(lg lg n)

如何选择找到theta的方法？什么,呃,这种复发是什么？我只是不太明白符号 - 内部复发的事情.