for循环的运行时间

Question

查看http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.htm#Counting上嵌套for循环的运行时间的示例和说明，第二个示例对我来说看起来并不正确。

例1

sum = 0; 
for(i = 0; i < n; i++) 
    for(j = 0; j < n; j++) 
     sum++; 

有道理的时候了。外for循环是O（n）。 Inner for Loop也是O（n）。将它们相乘，O(n) * O(n) = O(n*n) = O(n^2).

第二个例子。内部for循环不与0

sum = 0; 
for(i = 0; i < n; i++) 
    for(j = i; j < n; j++) 
     sum++; 

运行内环的时间将是(1 + 2 + … + n) = n*(n+1)/2 = O(n^2)如在第一例子开始，外环在O（n）的运行。所以总的运行时间是O(n) * O(n^2) = O(n^3).我是对的，还是我错过了什么？ 谢谢！

Answer 1

您添加了内循环总运行时间 - 而不是运行时间每外环的迭代。每个外部迭代的内部循环的运行时间仍然是O（n），导致O的总体结果（n ）。

换一种方式 - 如果你理解了第一个例子，第二个例子确实比第一个例子少工作，怎么可能有更大的复杂？

Answer 2

(1 + 2 + … + n) = n*(n+1)/2 = O(n^2)是总计该计划的时间。您不需要再乘以O(n)作为外部循环;你已经考虑了外部循环。

[注意：从技术上讲，可以说算法是O(n^3)。这只是一个有点误导]

Answer 3

内部循环的运行时间平均约为n/2，所以仍然是O（n），与第一个示例中的一样。

Answer 4

回应上面的前两个答案。 我不明白怎么(1 + 2 + … + n) = n*(n+1)/2 = O(n^2)将是总运行时间

说，n = 3

sum = 0; 
for(i = 0; i < n; i++) 
    for(j = i; j < n; j++) 
     sum++; 

总运行时间为内环是1times + 2倍3倍+

所以，凡外环发挥作用？它也运行O（n）次（就像它在第一个例子中那样）