使用合併排序算法所需的最少比較次數？

Question

對於那些熟悉合併排序的人，我試圖找出合併兩個大小爲n/2的子數組所需的最小比較次數，其中n是原始未排序數組中的項目數。我知道該算法的平均和最壞情況的時間複雜度是O（nlogn），但我無法弄清楚所需的比較數量（根據n）的確切數量。

Answer 1

合併步驟的最小比較次數大約爲n/2（順便說一句，仍然是O(n)），假設一個列表中的其中一個已經完全遍歷，那麼假設一個合理的實現。例如，如果兩個已有效排序的列表正在被合併，則將較大列表的第一個成員與較小列表進行比較n/2直到它被用盡;那麼可以複製較大的列表而無需進一步比較。

List 1 List 2 Merged List   Last Comparison 
[1, 2, 3] [4, 5, 6] []     N/A 
[2, 3] [4, 5, 6] [1]     1 < 4 
[3]  [4, 5, 6] [1, 2]    2 < 4 
[]  [4, 5, 6] [1, 2, 3]   3 < 4 
[]  [5, 6] [1, 2, 3, 4]  N/A 
[]  [6]  [1, 2, 3, 4, 5]  N/A 
[]  []  [1, 2, 3, 4, 5, 6] N/A 

請注意，進行了3​​次比較，列表中有6名成員。

再說一次，即使在最好的情況下，合併步驟仍被有效地考慮爲O(n)。合併排序算法的時間複雜度爲O(n*lg(n))，因爲整個列表中的合併步驟爲O(n)，並且劃分/合併發生在O(lg(n))級別的遞歸中。

Answer 2

對於每個比較，您從兩個列表中的一個列表中排除一個元素。所以比較的數量至多是兩個列表長度的總和。正如Platinum所示，如果達到一個數組的末尾並且另一個數組中仍有項目，則可能會更少。

所以比較的數量在n/2和n之間。

Answer 3

這個答案給出了一個確切的結果，不僅使用一些Landau symbol寫的漸近行爲。

合併長度米和Ñ的列表至少需要分鐘（米，Ñ）比較。原因是，只有當其中一個輸入列表已被完全處理時，您才能停止比較元素，即您至少需要迭代兩個列表中較小的一個。請注意，這種比較次數僅對於一些輸入而言是足夠的，所以它是最小的，因爲它假設了可能的輸入數據的最佳情況。對於最壞情況的輸入，你會發現更高的數字，即n ⌈lg n⌉ − 2⌈lg n⌉ + 1。

讓Ñ = 2 ^ķ是二的冪。讓i成爲合併級別，其中0≤i < k。在級i你執行2 ^{ķ - 我 - 1}合併，其中的每一個需要2個^我比較。將這兩個數字相乘，可以得出2 ^{k - 1}比較，其等於n/2。總結在ķ水平的合併你NK/2 =（ñ LG ñ）/ 2比較。

現在讓n小於2的冪。假設k = 012lg n⌉仍然表示合併級別的數量。與2 ^k的情況相比，您現在每個級別都少了一個比較。這樣合併的總數由ķ降低，導致2 ^ķķ/2 - ķ =（2 ^ķ/2 - 1）ķ比較。但是，如果您刪除多個元素，導致n = 2 ^k - 2，那麼您不會減少最上面的合併數，因爲另一個列表已經是較短的合併數。這表明這裏的事情可能會變得更加困難。

因此，讓我們有一點點的演示程序，我們可以同時使用來檢查我們以前的結果，並計算比較了其他值數：

mc = [0, 0]         # dynamic programming, cache previous results 
k = 1          # ceil(lg n) in the loop 
for n in range(2, 128): 
    a = n // 2        # split list near center 
    b = n - a        # compute length of other half list 
    mc.append(mc[a] + mc[b] + min(a, b)) # need to sort these and then merge 
    if (n & (n - 1)) == 0:     # if n is a power of two 
     assert mc[-1] == n*k/2    # check previous result 
     k += 1        # increment k = ceil(lg n) 
print(', '.join(str(m) for m in mc))  # print sequence of comparison counts, starting at n = 0 

這使您可以按以下順序：

0, 0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 
37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 
88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 
136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186, 192, 
193, 195, 197, 200, 202, 205, 208, 212, 214, 217, 220, 224, 227, 231, 
235, 240, 242, 245, 248, 252, 255, 259, 263, 268, 271, 275, 279, 284, 
288, 293, 298, 304, 306, 309, 312, 316, 319, 323, 327, 332, 335, 339, 
343, 348, 352, 357, 362, 368, 371, 375, 379, 384, 388, 393, 398, 404, 
408, 413, 418, 424, 429, 435, 441 

您可以在On-Line Encyclopedia of Integer Sequences中查找以發現該序列描述total number of 1's in binary expansions of 0, ..., n。這裏也有一些公式，但它們不準確（涉及一些Landau符號術語），或者它們依賴於其他一些不重要的序列，或者它們非常複雜。我最喜歡的一個表達了我上面的程序：

a（0）= 0，a（2n）= a（n）+ a（n-1）+ n，a（2n + 1 ）= 2a（n）+ n + 1。 - Ralf Stephan，2003年9月13日

鑑於這些替代方案，我想我會堅持使用上面的腳本來計算這些數字。您可以刪除斷言以及與此相關的所有內容，依賴於事實a < b，並刪除輸出以及如果將其包含到更大的程序中。結果應該如下所示：

mc = [0, 0] 
for n in range(2, 1024): 
    a = n // 2 
    mc.append(mc[a] + mc[n - a] + a) 

請注意，例如，對於ñ = 3你只有兩個比較。顯然這隻有在你將兩個極值元素與中值元素進行比較時才能起作用，這樣你就不必再將極值元素與另一個元素進行比較。這說明了爲什麼上述計算僅適用於最佳情況輸入。最差情況下的輸入會讓你在某個點上計算最小和最大元素，導致按照n ⌈lg n⌉ − 2⌈lg n⌉ + 1公式計算的三個比較。