归并排序复杂

我们知道，归并排序有以下算法的时间复杂度为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

归并排序复杂

回答

相关问题