java - 当 med 从 (ini + end)/2 更改为 ini + (end-ini)/4 时，合并排序算法会发生什么变化？

Question

关于以下形式的归并排序算法:

    public static void merge(int [] a, int ini, int med, int end){

    int [] b = new int[end - ini + 1];
    int i = ini;
    int j = med + 1;
    int k = 0;

    while(i <= med && j <= end) {

        if(a[i] <= a[j]){

            b[k] = a[i];
            i++;
        }
        else {

            b[k] = a[j];
            j++;
        }

        k++;
    }

    while(i <= med) {

        b[k] = a[i];
        i++;
        k++;
    }

    while(j <= end) {

        b[k] = a[j];
        j++;
        k++;
    }

    for(k = 0; k < b.length; k++){

        a[ini + k] = b[k];
    }
}

public static void mergeSortRec(int [] a, int ini, int end){

    if(ini < end){

        int med = (ini + end) / 2;

        mergeSortRec(a, ini, med);
        mergeSortRec(a, med + 1, end);
        merge(a, ini, med, end);
    }
}

public static void mergeSort(int [] a){

    mergeSortRec(a, 0, a.length - 1);
}

如果我将 mergeSortRec 中的 med 变量从 (ini + end)/2 更改为 ini + (end-ini)/4，我必须确定合并方法会有哪些性能差异。

我尝试渐进地评估算法，发现前者的合并时间为 O(n)，而 mergeSortRec 的时间为 O(ln n)(因此该算法为 O(n ln n)，但我不能'评估它在新表格上的表现。

进行更改后，Merge 方法的性能有何不同？对于整个算法，有什么真正的区别吗？

作为实践，我正在尝试查看两者中哪一个更有效(我知道它可能是第 n/2 个)，但我无法对其进行评估

Answer 1

如果您将问题分成两部分(而不是两个相等的部分)，一部分是初始问题的四分之一，第二部分是原始问题的 (3/4)，那么您的递归树将在第二部分变得更深，因此它会增加运行时间。

下面是基础数学-

T(N) = T(N/4) + T(3*N/4)

 = T(N/16) + T(3*N/16) + T(3*N/16) + T(9*N/16)
 = T(N/16) + 2*T(3*N/16) + T(N*(3/4)*(3/4))
                ...
                ...

从这里您可以看到，当 (3/4) 的某个幂等于或超过 N 时，递归调用将结束。

(3/4)^x = N

x = logN 以 3/4 为底

现在您可以比较以 2 为底的 logN 和以 3/4 为底的 logN 的图形，并理解为什么分成两等份具有更好的渐近行为。

This is recursion tree for an array of size 16 with your mid as ini + (end-ini)/4

附言阅读教科书以了解渐近分析。它会对你有很大帮助。