performance - 以下函数的时间复杂度是多少？

int DoSomething(int n) {
    if(n < 2) return 1;
    else return DoSomething(floor(sqrt(n))) + n;
}

根据我的说法，相应的重复将是:

Recurence Relatio

解决这个问题...

放 Substitute 1

函数变为

Rest of the image

能否请您验证并修正解决方案？

最佳答案

你是正确的 :-

S(m) = O(log(m))

然后

T(2^m) = O(log(m))

n = 2^m

T(n) = O(log(m))

but m = log(n)

hence 

T(n) = log(log(n))

关于performance - 以下函数的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25356779/

相关文章：

c - 将特殊用途字符串转换为整数的方法