確定這些不同循環的大O運行時間？

Question

確定這些不同循環的大O運行時間？

for i = 1 to n { 
    ... 
    for j = 1 to 2*i { 
    ... 
    k = j; 
    while (k>=0) { 
     ... 
     k = k-1; 
    } 
    } 
} 

我發現答案是O（n^3），因爲三個循環嵌套在一起，我的答案是否正確？

Answer 1

作爲一種啓發式方法，這是正確的，但是這種啓發式方法會導致你誤入歧途。可以找到內部循環數的確切公式。

對於每個j，k從j運行到包含0，因此內部循環運行j + 1次。

對於每個i，j運行從1到2 * i，所以內循環對i = 1運行1 + 1和2 + 1次，然後對於i = 2運行3 + 1和4 + 1次， 等等。我希望你能看到，對於每一個我內循環運行一個比（2i + 1）的第三個三角形數少一個。第n triangular number爲n（n + 1）/ 2，所以對於每個i，我們得到的

(2i+1)(2i+1+1)/2 - 1 

計數這簡化到

2 * i**2 + 3 * i 

對於每個n，i從1運行至n，所以我們只求和從1到n的最後一個表達式。這給了我們兩倍的前n個正方形數加上三個第三個三角數的總和。爲the sum of the first n square numbers公式是

n**3/3 + n**2/2 + n/6 

所以我們簡化

2*(n**3/3 + n**2/2 + n/6) + 3*(n*(n+1)/2) 

，我們得到

2/3 * n**3 + 5/2 * n**2 + 11/6 * n 

這顯然是O（n ** 3），所以你的啓發式是正確的。

我用一些簡單的Python代碼檢查了最終表達式。