힙 정렬 복잡성

Question

다음은

HEAPSORT(A) 
    BUILD-MAX-HEAP(A) 
    for i = A.length downto 2 
    exchange A[1] with A[i] 
    A.heapsize = A.heapsize - 1 
    MAX-HEAPIFY(A,1) 

그것은 나에게 분명 그 BUILD-MAX-HEAP는 O (N)와 MAX-HEAPIFY의 복잡성을 가지고이의 복잡성을 가지고 배열에 힙 정렬의 의사 코드입니다 O (h) 여기서 h는 logn의 최대 값을 갖는 힙의 높이입니다.

내가 완전히 이해하지 못하는 이유는 HeapSort가 nlogn의 복잡성을 갖는 이유입니다. MAX-HEAPIFY 각각에 대해 n 회 반복이 있다는 것을 이해합니다. 하지만 MAX-HEAPIFY 콜은 각 반복에서 크기가 줄어드는 힙을 얻습니다. 어떻게 각 반복은 O (lgn)의 복잡성을 가질 수 있습니까? 그것은 단단히 묶여 있습니까? 내가 어디에서 같은 수학적 증거를 볼 수 있습니까?

Answer 1

그래서

n! ≈ sqrt(2πn) * (n/e)n

, 스털링 근사에 의해, 이제

log 1 + log 2 + log 3 + ... + log n 
= log (1 * 2 * 3 * ... * n) 
= log n! 

을 준수하십시오

log n! ≈ n * (log n/e) = n * (log n - 1) = n log n - n

which is O(n log n) because the n log n 용어가 n 용어를 지배 (그리고 O는 (n)이 용어 I 로그 MathJax와 함께 입력하기가 너무 어렵 기 때문에 제외되었습니다).

Answer 2

큰 O 표기법은 어퍼 바운드입니다. 당신이 말한대로 :

MAX-HEAPIFY는 로그 n의 최대 값을 갖는 힙의 높이 인 h (h)의 복잡성을가집니다.

힙이 작아도 상관하지 않습니다. 은 최악의 경우이고, 힙의 높이는 로그 n입니다. 우리는 이것을 n 번하므로, nlog n입니다.