Bottom Up合併排序有用嗎？

我一直在閱讀「算法，第四版」Sedgewick & Wayne。本書介紹了使用合併排序的兩種方法。使用標準的自頂向下遞歸合併排序或自下而上的合併排序。Bottom Up合併排序有用嗎？

在自頂向下的版本中，哪種情況下自底向上合併排序比較受歡迎？

來源

2013-07-02 Nikunj Banka

http://stackoverflow.com/questions/10153393/mergesort-is-bottom-up-faster-than-top-down –

@MitchWheat這個問題討論了兩個排序例程的分析。不是應用程序。 –

根據複雜性分析選擇應用程序！大聲笑！ –

遞歸mergesort需要遞歸堆棧的O(log n)空間，但自下而上的版本可以讓你做得更好（沒有遞歸堆棧，只是一些整數跟蹤你在輸入中的位置）。

如果您遇到某種不支持遞歸的語言，並且只爲您提供有限的內存（可能是嵌入式系統？），則自下而上版本將是您的唯一選擇。

Here's一個自下而上的版本，顯示我的意思。

來源

2013-07-27 22:11:38 Mehrdad

不完全......在通常的「統一成本」模型中，我們假設我們可以在O（1）內存中存儲一個包含問題大小n的整數，自下而上的mergesort只需要O（1）空間。它可能（並且實際上更精確，雖然也更麻煩）改爲使用「對數成本」模型，其中空間以實際比特而不是足夠大的整數測量，在這種情況下，自下而上合併隊列需要O（log n）空間（就像*任何*算法一樣，它使用數組訪問來讀取它的完整輸入！），但是在這個模型中，遞歸合併需要O（log^2 n）空間。 –

@j_random_hacker：對不起，你是完全正確的......由於某種原因，我認爲跟蹤輸入位置需要O（log log N）位，我的不好;感謝您指出。 – Mehrdad

具有相同的複雜性，只有很小的差異，就像它合併的順序一樣。Left-Right-Up是遞歸的，而水平的是自下而上的。也遞歸使它有點slower sometimes，我覺得不太直觀。

來源

2013-07-02 07:59:07 user2485149

自上而下排序可以在幾乎沒有內存的情況下工作，數據在外部設備（例如磁帶）上進行排序。我認爲這是它在50年代和60年代的工作原理，我們在老電影中看到那些高大的磁帶機。

換句話說，自底向上合併是在線算法。它可以在沒有隨機訪問的情況下工作。

我們首先處理輸入磁帶，並在每次讀取輸入磁帶時寫入2個元素的分類塊，寫入兩個磁帶，在兩個磁帶之間交替寫入。然後我們從我們剛剛寫入的兩個磁帶中讀取2個塊，然後寫出4個合併塊，同時在輸出磁帶之間交替。然後，我們再次切換輸入和輸出，並以8個塊等進行。在上一次運行中，只有一個磁帶被寫入 - 這就是結果。

這可以在現代RAM硬件上模擬，只需O（1）個附加內存，並且在原地進行合併。要處理「短懸尾」問題（對於像2^n+k那樣的長度，對於小號k），沿着輸入序列的掃描可以交替地向前或向後進行。

來源

2013-07-29 11:31:08

Bottom Up合併排序有用嗎？

回答

相關問題