java - 具有特殊情况的循环的时间复杂度 (theta)

Question

我无法找到某些类型代码的 theta，例如。

for(i=1;i<=n;i++){
 for(j=i;j>=1;j=j/3){
 ....
 }
}

如何找到上述代码的 theta。

如果有人帮助我在一般情况下如何找到它，那将非常有帮助。

for(i=1;i<=n;i++){
 for(j=i;j>=1;j=j/K){
 ....
 }
}

Ps: 我知道 k=2 是 n*logn

提前致谢

Answer 1

从内循环开始。
内循环的每次迭代都需要Theta(log_K(i)) 次迭代，因为迭代器j 从i 开始并衰减呈指数增长。

因此，您现在必须将其与外部循环结合起来，这是一个简单的增量循环。
因此，外循环需要:

Theta(log_K(1) + log_K(2) + log_K(3) + ... + log_K(n)) = 
= Theta(log_K(1*2*...*n)) = Theta(log_K(n!)) = 
= Theta(n*log_K(n)) = Theta(nlogn)

The last equality is because log_K(x) = log_2(x) / log_2(K) , 但 log_2(K) 是一个常数。

---

我假设您的意思是 for(j=i;j>=1;j=j/3){，而不是 for(i=j;j>=1; j=j/3){(i 和 j 开启初始化)