c-时间复杂度的计算是否合法

Question

我有以下函数，我需要找到Theta符号：

void aux(int n){
for(int i = n; i>2; i = sqrt(i))
printf("*");}
void f1(int n){
aux(n);
aux(n*n);
aux(n*n*n);}

我可以假设sqrt(I(具有Theta(1(的时间复杂性。

我看这个系列是这样的：

i = n^(1/(2^0)), n^(1/(2^1)), n^(1/(2^2)), ... , n^(1/(2^k))

以及：

2 = n^(1/2^k) -> 1/2^k = log(n) -> 1/log(n) = 2^k

现在：

k = log(1/log(n)) = log((log(n))^(-1)) = -1*log(log(n)) =Theta(log(log(n)) 

我知道最终的解决方案是Theta(log(log(n((，但我想知道我的计算是正确的，可以这样说：

-1*log(log(n)) = Theta(log(log(n))

Answer 1

首先，计算中可能存在错误。问题中的工作显示

2 = n^(1/2^k) -> 1/2^k = log(n) -> 1/log(n) = 2^k

然而

2 = n^(1/2^k) -> 1/2^k = log(base n) 2 -> log(n) = 2^k

所以你得到的是k=+log(logn)，而不是-log(logn)。负的时间复杂性意味着你的程序运行需要负的时间。

所以，是的，算法是θ(log(logn((