什麼是合併的關鍵比較的最壞情況數量？

在Mergesort算法中，合併函數將大小相等的兩個排序的數組作爲輸入。但是，合併算法也可用於合併兩個大小不同的已排序數組。假設兩個數組A和B的大小分別爲3和1000，並且都按升序排序。什麼是合併的關鍵比較的最壞情況？證明你的答案。什麼是合併的關鍵比較的最壞情況數量？

我在想，假設大小爲1000的數組的第999個元素小於大小爲3的數組頭部的元素。然後假定所有3個元素都小於1000個數組的最後一個元素。我應該可以得到1002比較。這是最大的比較？我可以採取什麼方法來解決它。現在我只是猜測一些價值。

來源

2016-10-02 user292965

http://sorting.at/排序算法可視化網站 – sova

它是O（n + m）。每個陣列的每個元素都會與某些東西進行比較。

你可以看看用類似問題Time complexity for merging two sorted arrays of size n and m描述的算法。最好的情況是你在'複製休息'部分花了很多時間，最糟糕的情況是你必須提前兩個數組的計數器直到全部長度。隨時提出更具體的問題。

您可以通過考慮特定數據集來計算特定數字。例如。爲A{1001,1002,1003}和B{1,2, ..., 999, 1005}。最壞的情況是通過對最後一個元素（即嚴格的數字是n + m-1）執行「複製休息」片段來實現的。

999 comparisons: A{1001} vs B{1,..,999} -> B elements merged 
1 comparison: A{1001} vs B{1005} -> A merged 
1 comparison: A{1002} vs B{1005} -> A merged 
1 comparison: A{1003} vs B{1005} -> A merged

我們與一個做在這一點上和B的最後一個元素是使用「複製休息」一塊合併

來源

2016-10-02 11:52:15 Ivan

答案是1003，如果它是n + m？我似乎無法想象它達到1003. – user292965

我已經更新了我的答案，併爲您的數字指定了一個數據集 – Ivan

什麼是合併的關鍵比較的最壞情況數量？

回答

相關問題