c++ - 具有多个内循环的循环的时间复杂度

Question

for (int i = 0; i < n; ++i ) { //n   
  for (int j = 0; j < i; ++j) { //n
    cout<< i* j<<endl;
    cout<< ("j = " + j);  
  }    
  for (int k = 0; k < n * 3; ++k) //n?
    cout<<"k = " + k);     
} 

在这个循环中，我看到第一个 for 循环是 O(n)，第二个循环也是 O(n)，但第三个 for 循环让我感到困惑。 K 小于扩展的东西对于这个循环来说这也是 O(n) 吗？如果是这样，那么在这种情况下，另一个循环的时间复杂度内的两个循环是什么？我假设 O(n^2) 由于中间的两个 n 没有以任何方式相乘。它是否正确？另外，如果我是正确的并且第二个循环是 O(n)，如果它是 O(logn)，时间复杂度是多少？

(不是作业，只是为了理解目的)

Answer 1

大 O 表示法的一个好的经验法则如下:

When in doubt, work inside-out!

这里，我们先从内部的两个循环开始分析，然后向外推算出整体的时间复杂度。此处显示了两个内部循环:

for (int j = 0; j < i; ++j) {
  cout<< i* j<<endl;
  cout<< (”j = ” + j);  
}    
for (int k = 0; k < n * 3; ++k)
  cout<<”k = ” + k);  

第一个循环运行 O(i) 次并且每次迭代执行 O(1) 次，因此它总共执行 O(i) 次。第二个循环运行 O(n) 次(它运行 3n 次，并且由于 big-O 符号处理常量，所以总时间为 O(n) )并且每次迭代 O(1) 工作，所以它 O(n)总工作。这意味着您的整个循环可以重写为

for (int i = 0; i < n; ++i) {
    do O(i) work; 
    do O(n) work;
}

如果你做 O(i) 的工作然后做 O(n) 的工作，完成的总工作是 O(i + n)，所以我们可以进一步重写为

for (int i = 0; i < n; ++i) {
    do O(i + n) work; 
}

如果我们查看此处的循环边界，我们可以看到 i 的范围从 0 到 n-1，因此 i 永远不会大于 n。结果，O(i + n) 项等同于 O(n) 项，因为 i + n = O(n)。这使得我们的整体循环

for (int i = 0; i < n; ++i) {
    do O(n) work; 
}

从这里开始，整体运行时间为 O(n²) 应该会更清楚一些，因此我们进行 O(n) 次迭代，每次迭代的总工作量为 O(n)。

---

您在另一个答案的评论中询问如果第二个嵌套循环只运行 O(log n) 次而不是 O(n) 次会发生什么。这是一个很棒的练习，让我们看看如果我们尝试一下会发生什么!

想象一下代码是这样的:

for (int i = 0; i < n; ++i) {  
  for (int j = 0; j < i; ++j) {
    cout<< i* j<<endl;
    cout<< ("j = " + j);  
  }    
  for (int k = 0; k < n; k *= 2)
    cout<<"k = " + k);     
} 

这里，第二个循环仅运行 O(log n) 次，因为 k 呈几何增长。让我们再次应用从内到外工作的想法。内部现在由这两个循环组成:

  for (int j = 0; j < i; ++j) {
    cout<< i* j<<endl;
    cout<< ("j = " + j);  
  }    
  for (int k = 0; k < n; k *= 2)
    cout<<"k = " + k); 

此处，第一个循环的运行时间为 O(i)(与之前一样)，新循环的运行时间为 O(log n)，因此每次迭代完成的总工作量为 O(i + log n)。如果我们用它重写我们原来的循环，我们会得到这样的东西:

for (int i = 0; i < n; ++i) {  
  do O(i + log n) work;    
}

这个分析起来有点棘手，因为 i 从循环的一次迭代变为下一次。在这种情况下，通常有助于进行分析，而不是将每次迭代完成的工作乘以迭代次数，而是将循环迭代中完成的工作相加。如果我们在这里这样做，我们会看到所做的工作与

(0 + log n) + (1 + log n) + (2 + log n) + ... + (n-1 + log n).

如果我们重新组合这些术语，我们得到

(0 + 1 + 2 + ... + n - 1) + (log n + log n + ... + log n) (n times)

简化为

(0 + 1 + 2 + ... + n - 1) + n log n

求和的第一部分是高斯著名的求和 0 + 1 + 2 + ... + n - 1，恰好等于 n(n-1)/2。(很高兴知道这一点!)这意味着我们可以将完成的总工作重写为

n(n - 1) / 2 + n log n

= O(n²) + O(n log n)

= O(n²)

在最后一步之后，因为 O(n log n) 由 O(n²) 项支配。

希望这能向您展示结果的来源以及如何得出结果。从内到外工作，算出每个循环做了多少工作，并用更简单的“做 O(X) 工作”语句替换它，使事情更容易理解。当您有一些工作量随着循环计数器的变化而变化时，有时通过限制值并显示它永远不会离开某个范围来解决问题是最容易的，而其他时候通过明确计算出多少来解决问题是最容易的工作从一个循环迭代到下一个循环迭代完成。