Pourquoi le tableau accède-t-il à 6NlogN dans une fusion descendante descendante?

Question

Je ne comprends pas vraiment pourquoi trier un tableau de longueur N par un tri de fusion descendante, il n'a besoin que de 6NlogN accès au tableau. (Chaque niveau nécessite 6N, la hauteur est LGN, il est donc 6NlgN au total)

Chaque fusion utilise au plus ensemble 6N accès (2N pour la copie, 2N pour le mouvement de retour, et au plus 2N pour comparer)

Ne copie-t-il pas les éléments N dans le tableau auxiliaire et le copie-t-il dans le tableau original, qui est 2N? Qu'est-ce que le 2N "recule"?

La question est en réalité de la Progosition G dans Mergesort d'Algorithmes. Je pense pour ça.

Il est le code dans le livre ci-dessous:

public static void merge(Comparable[] a, int lo, int mid, int hi) 
{ // Merge a[lo..mid] with a[mid+1..hi]. 
    int i = lo, j = mid+1; 
    for (int k = lo; k <= hi; k++) // Copy a[lo..hi] to aux[lo..hi]. 
     aux[k] = a[k]; 
    for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi]. 
     if  (i > mid)    a[k] = aux[j++]; 
     else if (j > hi)    a[k] = aux[i++]; 
     else if (less(aux[j], aux[i])) a[k] = aux[j++]; 
     else       a[k] = aux[i++]; 
} 

public class Merge 
{ 
    private static Comparable[] aux;  // auxiliary array for merges 
    public static void sort(Comparable[] a) 
    { 
     aux = new Comparable[a.length]; // Allocate space just once. 
     sort(a, 0, a.length - 1); 
    } 
    private static void sort(Comparable[] a, int lo, int hi) 
    { // Sort a[lo..hi]. 
     if (hi <= lo) return; 
     int mid = lo + (hi - lo)/2; 
     sort(a, lo, mid);  // Sort left half. 
     sort(a, mid+1, hi);  // Sort right half. 
     merge(a, lo, mid, hi); // Merge results (code on page 271). 
    } 
} 

Answer 1

Ce que je peux voir que vous appelez uniquement les opérations de lecture « tableau accès », alors que le livre se réfère à la fois à la lecture et les opérations d'écriture comme « tableau accès ". Regardez le code merge. Vous avez 2 choix accès ici:

aux[k] = a[k]; 

Une opération de lecture a et une écriture sur aux. Puis ici:

a[k] = aux[j++]; //or aux[i++]; 

Vous avez encore deux autres, cette fois-ci une lecture sur aux et une écriture sur a. Et enfin, vous pouvez avoir deux autres lectures ici:

less(aux[j], aux[i]) 

Au total: 6 accès tableau (4 lectures et 2 écritures).

Comme vous l'avez mentionné, l'algorithme se logN deep et donc nous obtenons 6NlogN.