合併然後進行排序或排序然後合併會更快嗎？

我有2個數組沒有排序。將它們單獨分類然後合併它們會更快嗎？或者只是先串聯數組並排序組合巨大數組會更快？合併然後進行排序或排序然後合併會更快嗎？

來源

2013-04-10 Kunal Kapoor

似乎第二種方法更快，因爲串聯速度更快，然後合併。 – Egor 2013-04-10 11:30:13

我寧願分而治之。快速排序和合並排序從中受益。 – 2013-04-10 11:31:55

@Egor排序是一種比串聯和合並更少線性的操作（除非我們正在談論基數排序）。 – 2013-04-10 11:33:04

很明顯，大O在這個問題上並沒有真正的說什麼。假設你正在使用的算法是快速排序。 It has a average running time of:

enter image description here

所以，現在，如果排序然後合併，我們得到：

F1 = 1.39n *的log（n）* 2 + 2N

合併然後排序：

F2 = n + 1.39 * 2n * log（2n）

區別是

f2 -f1 = -n + 2。78N> 0

在一般情況下，如果一個排序算法具有複雜

C = K * n日誌（n）的

然後由於k應該是通常大於1，並且是不太可能在0.5附近的任何地方，如果您假設合併成本最多爲2n，那麼合併將會更快。

來源

2013-04-10 13:42:58

我認爲用這種方法分析算法的運行時間並不是很有意義。大O符號忽略的實際常量的使用表明它更加準確，但您仍然只計算選定的操作（比較次數，複製次數）並忽略其他許多操作（方法調用，緩存效果等）。國際海事組織（IMO），如果你想執行比big-O更接近實際的分析，你還應該考慮所有系統/語言/實現特定的常量，並使用分析器來代替。 – blubb 2013-04-11 08:59:21

@blubb你絕對是對的;我忘了在我的回答中提到，這只是比較輸入隨機時的平均比較次數。上述分析必須擴展，並定義計算模型。我會盡量編輯答案，使其更加真實世界，而不是在稍後的某一段時間只是一個粗俗的廢話。 – 2013-04-11 11:28:43

我認爲這將取決於排序算法和數據的大小。

但一個瘋狂的猜測是合併，然後排序整個批次是可取的。因爲在這種情況下的合併只是追加。

而在另一種情況下，您將需要應用排序合併。

來源

2013-04-10 11:32:24

儘管您的答案可能會更簡單，但問題的要求並不會更快。 – Alan 2013-04-10 11:38:14

我認爲在具體代碼運行之前沒有確定的答案。 – 2013-04-10 11:54:15

如果確保第二個數組中的所有條目都大於第一個數組中的所有條目，那麼可以在對每個數組進行排序後連接數組。每種排序算法的複雜性都比線性更差，所以當您可以將排序任務分解爲可以單獨排序的子集時，應該這樣做。

但是當條目在合併數組之後需要重新排序時，事先對每個數組進行排序不可能使其更快。

如果您想準確知道它，請創建一大組測試數據並自行測量性能。

來源

2013-04-10 11:34:21 Philipp

這取決於您使用的技術。

排序第一，然後合併會給你更好的結果在一個現代的多處理器體系結構，你可以在兩個陣列上運行排序算法並行線程O(nlogn)左右（但有更少的常量），然後合併它們在O(n)時間。

來源

2013-04-10 11:35:04 Ali

假設串聯在O(1)完成，合併需要O(n)和排序O(n log n)，您有以下選擇：

排序和合並：O(n log n) + O(n) = O(n log n)
連擊和排序：O(1) + O((2n) log (2n)) = O(n log n)

因此，兩個選項漸近地相等。

當然，如果你使用使用MergeSort，那麼整個討論都是無稽之談。

來源

2013-04-10 11:35:10 blubb

+1「整個討論無論如何......」 – 2013-04-10 11:47:19

我不認爲串聯將是Java中的「O（1）」。 – assylias 2013-04-10 12:14:05

@assylias：很可能。然而，只要連接不會超過'O（n log n）'操作，參數仍然有效。 – blubb 2013-04-10 12:34:55

合併然後進行排序或排序然後合併會更快嗎？

回答

相關問題