algorithm - 算法复杂性嵌套 For 循环

Question

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

在第一个代码示例中，p变量属于第一个循环。那么，即使它们不是嵌套循环，第二个也会返回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变量属于第二个循环。那么，它应该类似于第一个吗？像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²)。