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)

最后一个等式是因为log_K(x) = log_2(x) / log_2(K), butlog_2(K)是一个常数。

---

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