離散數學Big-O符號算法複雜性

如果你能幫我做part a，我大概可以找出b部分。我一整天都在看這個和類似的問題，而我只是在解決如何處理嵌套循環時遇到問題。對於第一個循環，有n次迭代，第二次有n-1次，第三次有n-1次。我是否正確思考這個問題？離散數學Big-O符號算法複雜性

考慮下面的算法，
，其作爲輸入n個整數a1的一個序列，A2，...，一個
，併產生作爲輸出的矩陣M = {}自我介紹
其中自我介紹是最小術語
在整數ai，a + 1，...，aj的序列中，j> = i，否則mij = 0。

初始化中號以便自我介紹=人工智能如果j> = i和自我介紹= 0

for i:=1 to n do 
    for j:=i+1 to n do 
     for k:=i+1 to j do 
      m[i][j] := min(m[i][j], a[k]) 
     end 
    end 
end 
return M = {m[i][j]}

的（a）表明，該算法使用BIG-O（N^3）比較，以計算矩陣M. （b）證明該算法使用Big-Omega（n^3）比較來計算矩陣M.使用這個面和部分（a），推斷該算法使用Big-theta（n^3））比較。

來源

2012-10-14 kkm

在部分A中，您需要找到min操作數的上限。

爲了做到這一點，很顯然，上述算法具有少min OPS然後執行以下操作：

for i=1 to n 
    for j=1 to n //bigger range then your algorithm 
    for k=1 to n //bigger range then your algorithm 
     (something with min)

上面有正是ñ^ 3 min OPS - 因此你的算法，有減去然後n^3分鐘操作。

由此我們可以得出結論：#minOps <= 1 * n^3（對於每個n> 10，其中10是任意的）。
通過definition of Big-O，這意味着該算法O(n^3)

你說你可以單獨圖B，所以我就讓你試試吧:)

提示：環路中間有更迭代那麼for j=i+1 to n/2

來源

2012-10-14 15:21:57 amit

謝謝！這比教材中的其他例子更有意義。現在，對於b部分。看看你的提示，如果我只看前半部分，操作次數會少一些，但算法仍然會執行Cn^3操作，其中C <= 1。因此，該算法是Big-Omega（n^3）。那是對的嗎？ – kkm

@helmeplease：這個想法是正確的，但是如果你正式需要，那麼應該做更多的步驟來展示它，然後如此直截了當。試試看，使用我用來展示big-O的方法，經過幾次試驗後，我相信你會到達那裏。 – amit

我必須說明這個新算法有多少操作，或者我可以說「Cn^3操作，其中C <= 1？」這是我遇到的最大問題 - 計算操作次數，當它不像您提供的示例那樣簡單時。 – kkm

對於外部循環內部的每次迭代，如果有i == n，則兩個嵌套循環將給出n^2複雜度。外環將運行i = 1 to n。所以總的複雜性將是一個系列，如：1^2 + 2^2 + 3^2 + 4^2 + ... ... ... + n^2。該總和值是n(n+1)(2n+1)/6。忽略此總和術語的低階條款最終的順序是O(n^3)

來源

2012-10-14 15:40:18 taufique

離散數學Big-O符號算法複雜性

回答

相關問題