運行時間的算法

Question

嗨，這是一個考試複習的問題。我必須找到以下代碼片段的運行時間（在Big-O中）。

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

我認爲它是O（n^4）。最裏面的循環執行到n，第二個執行到n^2，最外面的執行n次。謝謝大家的幫助

Answer 1

不，它不是O（4）。

更好的方法來看這是計算循環執行多少次（實際上，這就是代碼的工作）。

總和（求和（總和（1，K = 0..j）中，j = 0..i * I）中，i = 0到n）

=總和（總和（J，J = 0 * i * i），i = 0..n）= sum（i * i *（i * i + 1）/ 2，i = 0..n） 其中sum（i^4，i = 0..n），其數量級爲n^5。

本質上是因爲中間循環是i * i並且正在爲每個最內層的循環執行，所以需要額外計算一次。

在C++

http://codepad.org/nKJ9IUnt

1 0 
2 0 
3 6 
4 42 
5 162 
6 462 
7 1092 
8 2268 
9 4284 
10 7524 
11 12474 
12 19734 
13 30030 
14 44226 
15 63336 
16 88536 
17 121176 
18 162792 
19 215118 

可以使用此表並計算有限差（取導數），直到結果是一個常數或0你會發現，這需要5個衍生物有一個恆定的名單。這意味着它的名單大約是n^5。

例如，如果我們有一個列表，其中兩個元素之間的每個差異是常量，那麼列表可以用線性函數表示。如果差異的差異是恆定的，那麼它將是一個四極等等（它對於較低階項而言並不重要，因爲它們被導數/差值翻譯）

Answer 2

形式上，使用Sigma符號將有助於精確地推導增長的順序。

Answer 3

你可以簡單地認爲：在最裏面的循環

In the first loop: i = n 
second loop: j = i*i => j = n^2 
third loop: k = j => k = n^2 
So, the bigO = n * n^2 * n^2 = n^5