歸併排序複雜

我們知道，歸併排序有以下算法的時間複雜度爲O（nlogn）：歸併排序複雜

void mergesort(n elements) { 
mergesort(left half); ------------ (1) 
mergesort(right half); ------------(2) 
merge(left half, right half);

什麼將成爲下實現的時間複雜度？

(1) 
void mergesort(n elements) { 
    mergesort(first quarter); ------------ (1) 
    mergesort(remaining three quarters); ------------(2) 
    merge(first quarter, remaining three quarters); 

(2) 
void mergesort(n elements) { 
    mergesort(first quarter); ------------ (1) 
    mergesort(second quarter); ------------(2) 
    mergesort(third quarter); ------------ (3) 
    mergesort(fourth quarter); ------------(4) 
    merge(first quarter, second quarter,third quarter, fourth quarter);

請詳細說明您是如何找到複雜性的。

來源

2013-10-14 Ravindra

這似乎是一個家庭作業問題。沒有問題，但至少解釋你的想法。我們不是在這裏給你一個準備複製粘貼的答案。 –

我有一個微笑，不像作業一樣的問題。我計算了復發關係，並且每次都得到了nlogn的答案。發現奇怪。 – Ravindra

您發佈的所有三種算法都是O（n log n）常數略有不同。

其基本思想是它需要log（n）通過，並在每次通過時檢查n個項目。分區的大小並不重要，實際上你可以有不同大小的分區。它總是運行到O（n log n）。

運行時差異將在merge方法中。合併排序列表是一個O（n log k）操作，其中n是要合併的項目總數，k是列表數量。所以合併兩個名單是n * log(2)，其中工作到n（因爲log2(2) == 1）。

有關更多信息，請參閱我對How to sort K sorted arrays, with MERGE SORT的回答。

來源

2013-10-14 14:41:13

仍然是O（n log n），因爲n = log n/log 4的日誌庫4，最後是一個常數。

[編輯]

與k個分裂合併排序算法的重複週期關係如下。我假定合併ķ排序陣列，總共有n個元件的成本ÑLOG2（k）時，LOG2表示日誌基座2

T(1) = 0 
T(n) = n log2(k) + k T(n/k)

我可以解決重複週期有關：

T(n) = n log2(n)

不管k的值。

來源

2013-10-14 10:04:19 Tarik

那麼，一旦我們增加了no，那麼關係如何呢？間隔？我看到的是分母增加，減少了時間複雜度？ – Ravindra

對於2個區間，我們有T（n）= T（n/2）+ T（n/2）+ n。關係如何查找4個區間？ T（n）= 4T（n/4）+什麼？合併步驟的複雜性是什麼？ – Ravindra

它會以log 4/log 2的常數因子更快，但仍然O（n log n） – Tarik

請注意，這不是您的問題的確切答案，而是一個提示。

首先，我們需要了解缺省合併排序的時間複雜度如何變爲n（log n）。

如果我們有8個元素，默認mergesort方法，如果我們繼續每次分割它們一半，直到我們到達只包含一個元素的組，它將需要我們3個步驟。

所以這意味着mergersort在N個元素上被調用3次。這就是爲什麼時間複雜度爲3 * 8即（日誌N）* N

enter image description here

如果從一半到其他比例改變默認的分區，你將有來算，它跑了多少步你達到1個元素的組。

另請注意，此答案僅旨在解釋如何計算複雜性。所有分區方法的大O複雜度是相同的，如果以有效的方式實現其他2分區，將具有確切的複雜度N（logN）

來源

2013-10-14 10:29:44 Pranalee

但是不會合並步驟的複雜性增加？因此，隨着我們增加間隔數量，增加總體複雜性。 – Ravindra

歸併排序複雜

回答

相關問題