2016-11-19 86 views
2

我讀的算法設計手冊和這個解決方案是不說明書中無。我花了30分鐘計算出來,所以我想知道它是否正確。下面是該函數的僞代碼:這是算法分析是正確的

function conundrum(n) 
    r:=0 
    for i:=1 to n do 
    for j:=i+1 to n do 
     for k:=i+j−1 to n do 
     r:=r+1 

我們解決第一個求和,我們得到

最終的公式應該是:

鑑於第n^4負,我們可以得出結論,該算法的運行時間爲

它是正確的嗎?

回答

3

最終結果是正確的,詳細計算中至少有一個錯誤:從a到b在1之上的和是b-a + 1。

此外,下一個詞的符號是不相關的(我假設你的意思是n^2)。即使n^2項是正數,運行時也是Theta(n^3)。

+0

第二次看我知道我錯把2n個爲2N^2,這就是爲什麼我有着N^4之後。關於總和的事情,你能指出錯誤嗎? – SuburbanFilth

+0

我以爲我這樣做:如果你總結1從a到b的界限,結果是b-a + 1而不僅僅是b-a。 – Henry

+0

mb again lel,我沒有正確閱讀這個句子 – SuburbanFilth