当med从（ini + end）/ 2变为ini +（end-ini）/ 4时，Merge-Sort算法会发生什么？

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); 
} 

我必须确定哪些性能差异将到合并方法，如果我从（INI +端）/ 2改变内部mergeSortRec的配有可变制成到ini +（end-ini）/ 4。

我试着渐近评估算法，发现前者合并进入O（n），mergeSortRec进入O（ln n）（所以算法是O（n ln n），但是我无法评估它是如何站在新的窗体上。

是什么合并的方法性能上的差异时做出更改？ 的算法作为一个整体，有没有真正的区别？

我试图看看哪一个会更有效率（我知道它可能是n/2）作为练习，但我无法评估它

Answer 1

如果你把问题分成两部分（而不是两个相等部分），一部分是初始问题的四分之一，第二部分是原始问题的（3/4），那么你的递归树就会更深入第二部分，因此它会增加运行时间。

下面是底层mathematics-

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

附：阅读教科书以了解渐近分析。它会帮助你很多。