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）次（就像它在第一個例子中那樣）