運行時間分析，三個內for循環

這是我的第一個問題，我敢肯定，我也會接受我的第一個答案：P運行時間分析，三個內for循環

我必須做的一個算法的漸進分析，從一個數組A[1...n]計算一個矩陣M[n][n]其中包含了每種M[i][j]的值由下式給出：

M[i][j] = (A[i] + ... + A[j])/(j-i+1), if i<=j

和

M[i][j] = 0, if i>j

for i=1 to N do    [N] 
    for j=1 to N do    [N] 
    if(i<=j)     [cost] 
     start=i     [cost] 
     end=j     [cost] 
     sum=0     [cost] 
     for a=start to end do [??] 
     sum += A[a]   [cost] 
     M[i][j]=sum/(j-i+1  [cost] 
    else      [cost] 
     M[i][j]=0    [cost]

考慮，給予前兩個for循環我有期望至少Ø的運行時間（n^2），與第三內的循環，我會得到這樣的O（N * N * [ ??]）。第三for循環執行每次J-i + 1個的操作和僅對於i < = j的。矩陣將具有，第二的第一個元素等於0，然後計算平均值...

最終矩陣將導致幾乎一半填充（但不是N/2）所以，填充有平均計算的第一行對於第三循環中的值不爲[N/2]

如何可以計算用於最裏面For和也運行時間爲整個算法的運行時間？

來源

2013-03-07 Daved

對我來說，它仍然看起來像（大約）N/2爲最內圈。 – 2013-03-07 21:39:55

是的，但整個矩陣仍然可以爲O通過消除第三環路建（N^2）的時間（和保持A的運行總和[1] ... A [J]）。 – 2013-03-07 21:46:34

在這種情況下，我可以說運行時間是O（N^3）？對於算法分析來說這是一個可以接受的估計？ – Daved 2013-03-07 21:48:26

你可以嘗試只計算的時間內循環語句被執行的數量。

您遍歷i從1到N.現在你只會做內環路（含總和）當j大於或等於N所以Ĵ循環從我到N.內最環路，則包括ji補充。在你得到的（在楓樹語法）

sum(sum(j-i,j=i..N), i=1..N)= 1/6*N^3-1/6*N

然後，您需要考慮到M [i] [j]，這是做了N^2次的分配。

以前是指令的總量。然而，如果你只是在尋找整體的複雜性，那麼你應該看到內部循環依賴於N，這會給你O（N^3）的整體複雜性。

請注意，該代碼可以通過從一開始就存儲A [1]總和避免了內部循環的複雜性和不嘗試每次都重新計算它們

來源

2013-03-07 21:50:22 Origin

小錯字：-1/6 * N^3應該是1/6 * N^3。 – anumi 2013-03-07 22:26:28

運行時間分析，三個內for循環

回答

相關問題