合併排序合併運行時間anaylsis

我對合並排序中的合併函數的運行時分析存在一些混淆。合併排序合併運行時間anaylsis

Merg(A,p,q,r) 
1 n1=q-p+1 
2 n2=r-q 
3 let L[1..n1+1] and R[1..n2+1] be new arrays 
4 for i=1 to n1 
5  L[i] = A[p+i-1] 
6 for j =1 to n2 
7 R[j] = A[q+j] 
8 L[n1+1] = infinity 
9 R[n2+1] = infinity 
10 i =0 
11 j=0 
12 for k=p to r 
13 if L[i]<=R[j] 
14  A[k]=L[i] 
15  i=i+1 
16 else A[k] = R[j] 
17  j=j+1

在我的書，它說以下內容：看到，合併過程運行在O（n）的時間，其中n = R-P + 1，觀察到每個線1-3和8-11的需要一定的時間，第4-7行的for循環佔用O（n1 + n2）= O（n）時間，並且對於第12-17行的循環有n次迭代，每次迭代需要恆定的時間

我的問題是爲什麼第12-17行每次迭代需要不變的時間，並且不會影響運行時間，但是第4至7行的不需要一定的時間。對我來說，似乎兩個循環都在做同樣的事情。有人可以幫我澄清一下嗎？謝謝！

來源

2011-10-05 Wonger

這是令人困惑的寫。兩個循環（4-7和12-17）具有相同的長度（n），並且兩個循環的內部都是恆定時間（沒有嵌套循環）。所以它們都是O（n），對於整個例程總共爲O（n）。

關於傑瑞的回答，第4-7行很重要，因爲他們仍然是O（n）。如果你可以神奇地刪除12-17行，你仍然會有一個O（n）例程。

來源

2011-10-05 22:23:16

OH WOW。 IM啞巴哈哈。出於某種原因，我想他們是嵌套的，這會使它成爲O（n^2），但它確實是2n，它只是O（n）。書的解釋絕對不是以最好的方式寫的，但我現在明白了。謝謝！ – Wonger

第1到第9行只是將輸入（A）分成兩部分（L和R）。第10行和第11行正在進行一些初始化以準備合併。合併本身來自12-17行。

督察，第12行（或者可以說，而不是它真正的問題）無關分析合併因爲沒有它確實是合併的一部分，在衆人面前的一切。編輯：然而，最終，從1到27的單次迭代是線性的：在第4-7行中，您只需走過一次輸入數組，將每個輸入精確地分配給L或R.在第12行中， 27，然後你通過這兩個部分，並將其複製回原始輸入。忽略其他一些小的細節，如初始化i和j，操作的總數恰好是2N。對於大O符號，常數因子被忽略，所以它是O（N）。

來源

2011-10-05 22:21:33

那麼，這也是我會承擔的，但書中說，O（n）運行時間來自4-7行，而不是12-27行 – Wonger

合併排序合併運行時間anaylsis

回答

相關問題