algorithm - 归并排序复杂度

Question

我们知道归并排序的时间复杂度为 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);

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

Answer 1

仍然是 O (n log n)，因为 n 的以 4 为底的对数 = log n/log 4，它最终成为一个常数。

[编辑]

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

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

我可以将递归关系解析为:

T(n) = n log2(n)

无论 k 的值如何。