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

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),但第三循环对我来说很困惑.K小于扩展的东西,这个循环也是O(n)吗？如果是这样,那么另一个循环的时间复杂度中的两个循环在这种情况下会出现什么？我假设O(n ^ 2)由于中间的两个n没有以任何方式相乘.它是否正确？另外,如果我是正确的并且第二个循环是O(n),那么如果它是O(logn),时间复杂度会是多少？

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

Answer 1

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

如有疑问,请从里到外工作!

在这里,让我们从分析两个内部循环开始,然后向外工作以获得整体时间复杂度.这里显示了两个内部循环:

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)次(它运行3次,因为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,所以我永远不会大于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;    
}

这个分析有点棘手,因为我从循环的一次迭代变为下一次循环.在这种情况下,通常不是通过将每次迭代完成的工作乘以迭代次数来进行分析,而是通过将循环迭代中完成的工作相加.如果我们在这里这样做,我们将看到完成的工作与之成正比

(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次)

这简化了

(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 ²)项支配.

希望这能告诉你结果来自哪里以及如何提出它.从内到外工作,计算每个循环的工作量,并用更简单的"do O(X)work"语句替换它,以便更容易理解.当你有一些工作量随着循环计数器的变化而变化时,有时通过限制值并显示它永远不会离开某个范围来解决问题是最容易的,有时候通过明确计算出多少来解决问题最容易解决问题.工作从一个循环迭代到下一个迭代完成.