當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

附：閱讀教科書以瞭解漸近分析。它會幫助你很多。