Big-O for-loop運行時分析

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

我的猜測是這只是一個O（N^2），但是我給了我懷疑。Big-O for-loop運行時分析

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

似乎是一個O（N^3）

int n = 500; 
    for(int i = 0; i < n; i++) 
     for(int j = 0; j < i*i; j++) 
      if(j % i == 0) 
       for(k = 0; k < j; k++) 
        sum++

O（N^5）？

因此，對於每個循環j有不同的值。如果這是一個非常棘手的問題，那麼請幫忙。謝謝。

來源

2015-02-07 btrballin

大哦定義請記住，O符號只是縮放行爲。只要問問自己，如果輸入的大小發生了變化，操作的數量如何相應地增加 - 並且你擁有它。 – Trilarion 2015-02-07 22:27:44

我已投票結束該問題。已經有數百個類似的問題，並且它們太窄而無法用於一般。我所說的問題是重複提供的工具，以允許人們自己計算big-O。 – 2015-02-08 03:28:32

你是對的，但所有的最後一個，具有結合的O(n^4)更緊：請注意，如果j是i多最後for循環時，纔會執行。有x/i的i的倍數低於或等於x和i * i/i = i。因此最後一個循環僅在i * i中執行i值。

請注意，大哦給出了一個上限，所以i*i與n*n沒有什麼區別。嚴格地說，他們都是O(n^2015)也是正確的（因爲這是一個有效的上限），但它沒有什麼幫助，所以在實踐中通常使用緊密的界限。

來源

2015-02-07 22:05:19 IVlad

在第一種情況下，sum++執行0 + 1 + ... + n-1次。如果您應用arithmetic progression公式，則會得到n (n-1)/2，即O(n^2)。

在我們會有0 + 1 + 4 + 9 + ... + (n-1)^2第二種情況下，這是第一n-1數的平方和，和那裏是a formula：(n-1) n (2n-1)

最後一個是有趣的。你可以看到，其實，最嵌套for循環稱爲只有當j是i被乘數，這樣你就可以如下重寫程序：

int n = 500; 
for(int i = 0; i < n; i++) { 
    for(int m = 0; m < i; m++) { 
     int j = m * i; 
     for(k = 0; k < j; k++) 
      sum++ 
    } 
}

它更容易使用的數學符號的工作：

Derivation

的公式從通過分析所述代碼導出：我們可以看到，sum++得到最內層循環中，這被稱爲i倍，這被稱爲所謂的倍次。最後，問題歸結爲第一個n數字加上低階項（不影響漸近線）的立方數之和

最後一個注意事項：它看起來很明顯，但我想說明在d的第一個N自然數的總和總和爲Ω(N^(d+1))（請參閱Wikipedia的Big-Omega notation），即它的增長速度不會低於該函數。您可以應用相同的推理來證明滿足更強的條件，即它屬於Θ(N^(d+1))，它結合了Ω和O。

Derivation

來源

2015-02-07 22:11:23

嗨。欣賞你冗長的答案，但我不能完全理解你想要爲最後一個問題準確表達的意思。我沒有看到你以一個答案結束，所以我有點困惑。 – btrballin 2015-02-08 02:00:26

@btrballin，你的意思是你的最後一個問題，或者我的「d」次方的總和？第一個結論是，運行時間是'O（n^4）'，而不是'O（n^5）'，最後一個註釋是一個「證明」，如果你有一個循環'for k在[1..n]'哪個主體具有'O（k^d）'運行時間，那麼循環將在'O（n ^（d + 1））'中運行。我列入這個推導的原因是，在前3個例子中，我使用了自然數，平方和，立方和之和的事實 - 所有這些都有一個高階閉合公式。最後一段概括了這些結果。 – 2015-02-08 08:03:54

IVlad已經給了正確的答案。

我覺得讓你困惑的是「大哦」的定義。

N^2具有O（N^2）
1/2N^2具有O（N^2）
1/2N^2 + C * N + B也具有 O（ N^2） - 由下式給出c和b爲常數獨立從N個

檢查從here

來源

2015-02-07 22:11:27 finxxi

Big-O for-loop運行時分析

回答

相關問題