合併兩個分類數組的最差情況下的比較數？

Question

給定兩個排序陣列A, B，大小爲n和m。我正在尋找合併這兩個數組的最差數據比較。

1）N + M-1

2）MAX（N，M）

3）分鐘（M，N）

4）MN

我知道這是不是一個好的問題，因爲合併算法沒有提到，但我認爲，正常合併排序算法 - 合併步驟與正常應用n + m -1比較，其中一個列表的大小爲n，另一個列表的大小爲m。使用這種算法是組合兩個排序列表最簡單的方法。任何專家都可以幫助我，我正確地選擇（1）？

Answer 1

人，閱讀documentation！

複雜

在大多數的std ::距離（first1，last1）+的std ::距離（first2，last2） - 1個比較。

因此，它是第一號。 （是的，它假設標準委員會的複雜性是正確的，但這不是一個延伸。）

選項4顯然是錯誤的，因爲n + m - 1增長比n * m慢，所以我們已經有了一個更好的估計。

選項3是與此反假：

[4], [1, 2, 6, 7] 

需要至少兩次比較。選項2反：

[1,6], [2,5] 

將需要3個比較：

1 < 2?, 6 < 2?, 6 < 5? 

Answer 2

假設米< N，至少m個比較和至多n + m-1個比較（最壞情況）。因此，假定最小列表中的所有元素都是第一個，則最小比較次數是min（n，m）。假設最簡單的意思是最好的情況，那麼答案3是正確的答案。答案1對於最壞的情況是正確的。