合併兩個陣列有效地 - 一個排序，另一個未排序

我在具有n個元素，隨後長度合併兩個陣列有效地 - 一個排序，另一個未排序

O（logn）時間
O（SQRT的一個未排序的陣列的排序後的數組中的問題的工作（n））

如何最有效地對整個列表進行排序？在上述兩種情況下應該使用哪種排序？

來源

2012-12-13 Neel

我們可以在第一種情況下使用信息O（logn）嗎？我們可以使用任何數據結構並更有效地進行分類嗎？ – Neel

由於在數組中插入單個元素並保持排序爲O(n)，所以您無法做得更好。

因此，對於這兩種情況 - 排序較小的陣列，然後使用merge(part1,part2)將爲O(n)，因此在漸近複雜性方面是最優的。

排序較小的數組：O(logn*loglog(n))或O(sqrt(n)*log(sqrt(n))分別的情況。
merge(part1,part2)：O(n+logn)或O(n+sqrt(n))，也就是O(n) 無論如何。

所以，這兩種情況下總的複雜性是O(n)，這是最適合這個問題。

（1），因爲，log(n)^k是漸近較小然後n^m每個k>0,m>0，並且具體地爲k=1, m=1/2這是真的。
證明是基於考慮雙方的日誌：

log (log(n)^k) <? log(n^m) <=> 
k*log(log(n)) <? m*log(n)

最後是（對大型n，不斷k,m>0）顯然是真的，因此要求是真實的。
由此我們可以得出結論，sqrt(n)*log(n) < sqrt(n) * n^1/2 = n，因此它確實是O(n)。

來源

2012-12-13 15:11:40 amit

你的邏輯是正確的，只是它不是很明顯，'O（sqrt（N）* log（N）） salva

@salva：我會澄清，但基本上'log（n）^ k對於每個'k，m'，特別是對於'k = 1，m = 1/2'，漸近地小於'n^m'。 – amit

@salva：我加了一個詳細的解釋，作爲這個說法的腳註。 – amit

很簡單，對第二部分進行排序並將其與第一部分合並（與合併合併一樣）。兩個排序子陣列的合併步驟是O（n）。

來源

2012-12-13 15:10:51

您可以簡單地對未排序的數組進行排序，然後在這兩個排序的數組上執行merge（如merge sort算法）。

來源

2012-12-13 15:11:53

分別假設part1和part2尺寸分別爲r O（log n）和O（sqrt（n））。因此，如果您從part2中選擇一個元素並通過二進制搜索在log（log n）中找到part1中的位置，並遞歸執行，直到part2的元素不爲空，則總運行時間將變爲O（sqrt（n）log （log n））。

來源

2013-09-15 10:54:13

通過二分搜索找到part1中元素的位置（來自part2）將取logn。但是要將元素放置在part1中的正確位置將需要線性時間（O（n））。這裏第1部分中的排序數組有n個元素。有兩個問題。第一個問題中未排序的數組長度是logn，第二個問題是sqrt（n）。 – Neel

合併兩個陣列有效地 - 一個排序，另一個未排序

回答

相關問題