大歐米茄分析

我一直在努力理解就是最好的可能運行時間：大歐米茄分析

for t = 1 to n 
    sum = 0 

    for i = 1 to t 
     sum = sum + x[i]

據我所知，第一個循環會n次。這是我與之鬥爭的內部循環。內部循環將在第一次進入n（n + 1）/ 2，但下一次將進入n（n + 1）/ 2 -1。我不確定如何將此轉換爲最佳運行時間。

如果可能，我可以在正確的方向上使用推送。謝謝！

2014-09-19 csonq

請詳細說明---這裏的「t」是什麼（t的值）？另外，我想你需要更嚴格的分析！ – 2014-09-19 20:49:59

爲了形象化這個，我拿想象充滿了正方形或瀰漫着骰子體積區域的方法更復雜的情況。每個方塊代表一個原子步驟。外循環迭代的所有步驟放在同一行上。對於你來說，它看起來像這樣：

t=1 # 
t=2 ## 
t=3 ### 
t=4 #### 
t=5 #####

正如你所看到的，這些形成一個三角形，誰的高度爲N和誰的寬度也N.如果你現在算平方（N *（N + 1 ）/ 2）你有內循環的迭代次數。乘以該項並刪除不相關的術語會帶來複雜性Θ（N * N）。

2014-09-19 23:35:51

您爲分析O（n）的嘗試增加了一點複雜性。這可能是你爲什麼感到困惑的原因。

我們知道外環for 1到t是線性的。內部循環隨着時間的推移運行更多。在t = 1時，它運行一次，在t = n時，它運行n次。

我們運行for循環的平均次數是多少？

avg = (1 + n)/2

這是你發現了，雖然你試圖來遍歷它的價值。我們所需要的是我們計算的平均值。

因爲1對n的高值n相對不重要，所以我們可以近似爲n/2。

所以外循環運行n次。內部循環運行n/2次。

n * n/2 = 0.5n^2

因爲我們通常會忽略最乘值，我們可以說，O(n) = n^2

2014-09-19 21:01:14 Compass

回答