탑 다운 병합에서 어레이가 6NlogN에 액세스하는 이유는 무엇입니까?

Question

왜 N 길이의 배열을 하향식 병합 정렬로 정렬해야하는지 이해할 수 없지만 6NlogN 배열 액세스 만 필요합니다. (각각의 레벨이 6N 필요 높이 LGN이므로 총에 6NlgN있어)에 액세스하는 각각의 병합 가장 6N 어레이에서 사용

(복사 용 2N, 2N 다시 이동 대, 가장 2N에 대해는 비교)

N 요소를 보조 배열로 복사하고 원본 배열 (2N?)으로 다시 복사하지 않습니까? 2N "뒤로 이동"이란 무엇입니까?

질문은 실제로 Mergesort of Algorithms의 Progosition G에서 온 것입니다. 나는 이것을 생각한다. 책 읽기와 "배열로 쓰기 작업에 모두를 의미하는 반면"배열 액세스 "

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

내가 볼 수있는 것은 만 읽기 작업을 호출 할 것입니다 :

그것은 아래의 책에있는 코드입니다 액세스 ". merge 코드를 확인하십시오. 당신은이 배열은 여기에 액세스 있습니다

aux[k] = a[k]; 

A는 a에 작업을 읽고 aux에 쓰기 하나. 그리고 여기 :

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

당신은 또 다른이,이 시간 aux의 읽기 및 a에 쓰기가 있습니다. 그리고 마지막으로, 당신은 두 개 더 여기 읽어있을 수 있습니다 모두

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

모든 : 6 배열 액세스 (4 읽기 및 2 개 쓰기).

언급했듯이 알고리즘은 logN이 깊어서 6NlogN이됩니다.