힙 정렬의 공간 복잡성이 O (1) 인 이유는 무엇입니까?

Question

힙 정렬의 공간 복잡성이 O (1) 인 방법을 이해하지 못합니까? 빠른 정렬은 여분의 배열 (즉, 제자리)을 사용하지 않지만 최악의 경우에는 O (n)이고 재귀 호출의 경우 백엔드에서 스택이 사용될 때 가장 좋은 경우 O (lg n)입니다. 내가 맞습니까?

힙 정렬과 동일합니다. 하지만, 현재 위치에 있지만 Build-Heap 함수가 Max-Heapify 함수를 호출하기 때문에 공간 복잡도가 Max-Heapify와 같아야합니다 (즉, O (lg n)). 그렇지 않니? 또한, Max-Heapify 함수는 루트 노드에서 n 번 호출되며, Max-Heapify() 공간 복잡도는 O (lg n)입니다.

따라서 힙 정렬의 전체 공간 복잡성은 O (lg n) 여야합니다. 하지만 위키 백과에서 O (1)를 발견했습니다. 내가 이해하도록 도와 줘.

Answer 1

Heapsort는 정렬되는 배열의 크기, 배열 자체의 공간 및 소수의 변수에 따라 공간을 차지하지 않습니다. 분명히 O (1).

Quicksort는 정렬이 필요한 하위 배열 스택을 추적합니다. 당신이 똑똑하다면 두 개의 하위 어레이 중 큰 하나를 스택에 놓고 작은 것을 즉시 정렬하면 O (log n)가 걸립니다.

실제로는 아무런 차이가 없습니다.

Answer 2

공간 복잡도는 알고리즘에서 사용되는 추가 공간을 나타냅니다. 힙 정렬은 정렬 할 배열을 제외하고 추가 공간 (O (n)에서)을 사용하지 않습니다. 따라서 O (1)

Answer 3

heapify의 비 재귀 버전이 있습니다 (아래 예 참조). quicksort의 경우 재귀가 작은 파티션에서만 사용 된 경우 다시 큰 루틴을 2로 분할하고 (다시 2 개의 작은 파티션에서 재귀를 사용하는 등) 최대 스택 공간은 O (로그 n)), 최악의 경우 시간은 여전히 ​​O (n^2)입니다.

C++ 비 재귀 heapify 비 재귀 힙 일종의 예 :

typedef unsigned int uint32_t; 

void HeapSort(uint32_t *, size_t); 
void Heapify(uint32_t *, size_t); 
void SiftDown(uint32_t *, size_t, size_t); 

void HeapSort(uint32_t * a, size_t count) 
{ 
size_t end; 
    Heapify(a, count);  // create initial heap 
    end = count-1; 
    while(end > 0){ 
     // swap root (largest value) with end 
     std::swap(a[0], a[end]); 
     // reduce size of heap and 
     // increase size of sorted array 
     end--; 
     // repair the reduced heap 
     SiftDown(a, 0, end); 
    } 
} 

// create initial heap: for root = (count-2)/2 -> 0 
// parent = root, children = root*2+1, root*2+2 
// swap so that all a[parent] > a[child] 
void Heapify(uint32_t * a, size_t count) 
{ 
size_t root; 
    if(count < 2) 
     return; 
    // create sub-heaps of increasing size, 
    // with root going from (count-2)/2 to 0 
    root = (count - 2)/2; 
    while(1){ 
     SiftDown(a, root, count-1); 
     if(root == 0) 
      break; 
     root--; 
    } 
} 

// scan from root to end, swapping as needed to repair or create heap 
void SiftDown(uint32_t * a, size_t root, size_t end){ 
size_t parent; 
size_t child; 
    // while at least two children 
    for(parent = root; (child = parent * 2 + 2) <= end;){ 
     // choose the larger child 
     if(a[child-1] > a[child]) 
      child = child-1; 
     // if child > parent then swap, parent = child 
     if(a[child] > a[parent]){ 
      std::swap(a[child], a[parent]); 
      parent = child; 
     // else done with search for swaps 
     } else { 
      break; 
     } 
    } 
    // check for final only child 
    if((child = parent * 2 + 1) <= end) 
     if(a[child] > a[parent]) 
      std::swap(a[child], a[parent]); 
}