MergesSort和實際計數在哪裏？

因此，讓我們說我們有一個從1-> 10的大小爲10的遞增數組。我理解數組的分裂，但我不明白的是什麼時候發生了任務。這裏是我目前的解釋是什麼意思：MergesSort和實際計數在哪裏？

(1) 1,2,3,4,5,6,7,8,9,10 
    (2) 1,2,3,4,5  6,7,8,9,10 
    (3) 1,2 3,4 5  6,7 8,9 10 
    (4) 1 2 | 3 4 | 5  | 6 7 | 8 9 | 10 
    (5) 1,2 3,4  5   6,7  8,9  10 
    //(5.5) 1,2,3,4 5   6,7,8,9 10 
    (6) 1,2,3,4,5  6,7,8,9,10 
    (7) 1,2,3,4,5,6,7,8,9,10

我不確定我們是否從步驟5到6或如果我們做了步驟5.5。除此之外，我假定第5步有10個作業，第6步有10個作業，第7步有10個作業，共30個作業。我相信這是錯誤的，因爲我不確定步驟（2），（3），（4）是否也計算在內，或者如果我甚至在計算開始時的計數。感謝您的幫助。

來源

2015-09-27 chris123

要計算變量賦值，我們必須知道這個特定的mergesort實現如何使用變量。即使我們僅對數組元素進行賦值，實現也很重要（例如，實現可能會嘗試重用數組，或者在每個步驟中使用新數組，這顯然會影響賦值的次數）。 – meriton

它甚至取決於輸入，在這種情況下0賦值，因爲1到10已經排序。 – Wouter

但不合並數組作爲分配？我們只是說它是一個通用的遞歸mergesort。 – chris123

你應該算比較。比較的數量是O（N log N）

來源

2015-09-27 15:28:16 Wouter

你怎麼知道OP應該計算比較而不是分配？ – meriton

由於OP標記爲大o並且不確定要計數什麼。 – Wouter

MergesSort和實際計數在哪裏？

回答

相關問題