K路合併的最大K值

Question

我想知道，K路合併排序的最大K值是多少還是有最大值。 該算法的時間複雜度爲O（nlogK）。我一直在尋找它幾個小時，沒有運氣。有人可以將我鏈接到一些文章中，或者告訴我是否有一些限制，爲什麼會這樣？ 另外我想知道是否有一些推薦使用的K值，這是最有效的。

Answer 1

在內部（僅限存儲器）排序的情況下，數據上的操作總數大致保持不變，而不考慮K.設x = n log2（n）。雙向合併排序需要x次移動，最差情況x比較總計x + x =（2）次x次操作。 （從技術上講，即使在最糟糕的情況下，這個比例還是會低於x，但是x足夠接近這個概念）。一個4路合併排序需要（1/2）x運動和最壞情況（3/2）x比較，所以仍然是總共（1/2）x +（3/2）x =（2）x運算。如果比運行速度快，那麼4路合併排序比較快，如果運行速度比較快，則2路合併排序比較快。還有像指針或索引這樣的變量被保存在寄存器或堆棧中的問題，對於4路合併，您需要16個寄存器（如64位模式下的X86）。作爲移動速度更快的示例，請考慮指向對象的指針數組進行排序，只移動指針但比較對象（其中涉及每個對象的指針取消引用）的情況。

對於外部排序，在外部設備（磁盤驅動器，或過去的一堆磁帶驅動器）上創建已排序塊的內部排序可以是任何算法，K方式部分只是合併塊。在外部排序傳遞的數量和K足夠大以便K方式合併成爲cpu綁定而不是I/O綁定之間存在折衷。總時間是I/O時間+任何超過I/O時間的CPU時間。對於大數據文件，Gnu排序使用K = 16。K方式合併使用K元素最小堆完成，其中每個堆條目對應於一個結構（或等價物），它包含塊ID，記錄索引或指針，數字的剩餘內存中的塊的記錄數，塊中剩餘的記錄數）。在使用K條目初始創建最小堆之後，堆的前面元素對應於K條目當前最小元素（假定升序排列）的結構。移動該元素以輸出，從該塊讀取下一個元素，並且更新堆以反映下一個元素放置在堆內的前項的位置。一旦到達塊的末尾，合併就成爲K-1合併，然後是K-2合併，直到剩下只有1塊被複制。