算法复杂度——嵌套 For 循环

Question

for(j=n; j>1; j/=2)
  ++p;
for(k=1; k<p; k*=2)
    ++q;

在第一个代码示例中，p 变量属于第一个 循环。那么，即使它们不是嵌套循环，2nd 也会返回 log(n) 吗？我的意思是，O(loglog(n))？

for(i=n; i>0; i--){
  for(j=1; j<n; j*=2){
    for(k=0; k<j; k++){
      //statements-O(1)
    }
  }
}

而这一个，它们是嵌套的，但是 k 变量属于 2nd 循环。那么，它应该类似于第一个吗？像 O(n^2.log(n)) 或 O(n.log^2(n))？

Answer 1

1. 算法:第一个循环需要 log(n) 时间。第二个循环需要 log(log(n)) 时间。所以你有 log(n) + log(log(n))。但是第一个循环更重要。所以它是 O(log(n))。

2. 算法:首先看看当您只分析两个外部 for 循环(即 n log(n))时的运行时间。但不幸的是，有一个内部三分之一的 for 循环，这使得它更加复杂。

   第三个 for 循环从 0 到 2^m，其中 m=log(n)。因此，您必须将 2^m 从 0 加到 log(n)-1，即 n-1。所以 n-1 是两个内部 for 循环的运行时间。现在您必须将它乘以外部 for 循环的线性运行时间。所以它是 (n-1)n 也就是 n²-n。所以你有 O(n²) 三个循环。