0

我们知道合并排序对于以下算法的时间复杂度为 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);

请详细说明您如何找到复杂性。

4

3 回答 3

4

仍然是 O (n log n)，因为 n 的 log base 4 = log n / log 4，最终是一个常数。

[编辑]

k split 的归并排序算法的递归关系如下。我假设将 k 个排序数组与总共 n 个元素合并成本 n log2(k)，log2 表示 log base 2。

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

我可以解决递归关系：

T(n) = n log2(n)

与 k 的值无关。

于 2013-10-14T10:04:19.000 回答
3

请注意，这不是您问题的确切答案，而是一个提示。

首先，我们需要了解默认归并排序的时间复杂度是 n(log n)。

如果我们有 8 个元素并且默认使用合并排序方法，如果我们每次将它们分成两半，直到我们到达仅包含一个元素的组，这将需要 3 个步骤。

所以这意味着mergesort在N个元素上被调用了3次。这就是为什么时间复杂度是 3*8 即 (log N)*N

在此处输入图像描述

如果要将默认分区从一半更改为其他比例，则必须计算达到 1 个元素组需要多少步。

另请注意，此答案仅旨在解释如何计算复杂性。所有分区方法的大 O 复杂度是相同的，如果以有效的方式实现，即使其他 2 个分区也将具有 N(logN) 的精确复杂度

于 2013-10-14T10:29:44.267 回答
2

您发布的所有三种算法都是 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）。

有关更多信息，请参阅我对如何使用 MERGE SORT 对 K 排序数组进行排序的答案。

于 2013-10-14T14:41:13.867 回答