爲什麼合併排序被認爲是最好的

-2

爲什麼不用二進制插入插入排序被認爲是最好的？爲什麼合併排序被認爲是最好的

Merge sort : T(n) = n + 2*T(n/2) = O(n*log(n)) 
But insertion sort with binary insert : T(n) = log(n-1) + T(n-1) = O(log(n!)) 
and n^n > n! ; so n*log(n) > log(n!)

對於更大的n，它確實有助於提高性能。

或者我錯過了什麼？

請原諒我，如果我問的問題太重要，我是編程新手，我只是希望事實正確。

來源

2013-07-19 rnbcoder

使用二進制插入的插入排序仍然需要n個插入;我不確定你是如何派生出O（log（n！））的？參見wikipedia：http://en.wikipedia.org/wiki/Insertion_sort（二進制插入排序）。最壞情況下的複雜度是O（n * log（n）） – davmac

@HenkHolterman，不，只是錯誤的。例如3^3 = 3 * 3 * 3，而3！ = 3 * 2 * 1. – davmac

合併排序可以非常平行。對gpu有好處。適用於opertons和xeons。 –

我認爲你對插入排序的複雜性的估計是錯誤的。你沒有描述你如何得到結果的細節，但你似乎忘記了插入所需的時間 - 我的意思是你需要移動排序數組的一部分來爲你插入的元素創建位置。

在對n-1個元素進行排序後，需要O（log（n））時間來查找第n個元素的位置和O（n）（悲觀）時間來移動排序數組的一部分，爲第n個元素。因此，總的複雜度是O（1 + ... + n + log 1 + ... + log n）= O（n^2 + n log n）= O（n^2）。

無論如何，您都不會通過二分搜索來改進算法，因爲您必須移動部分數組（線性大小以n爲單位）。

來源

2013-07-19 12:37:06

使用二進制插入的插入排序的平均運行時間爲O（n^2）。嘗試瀏覽wiki頁面here。另外，請查看this SO貼子。

來源

2013-07-19 12:34:12 Sankalp

爲什麼合併排序被認爲是最好的

回答

相關問題