왜 heapsort lg (n!)가 아닌가요?

Question

나는 CLRS을 읽고 있어요 그리고 힙 정렬이 MAX_HEAPIFY이 O(lg n)입니다

HEAPSORT(A): 
BUILD-MAX-HEAP(A); 
for (i = A.length; i >= 1; i++) 
{ 
    exchange A[1] with A[i]; 
    A.heap-size = A.heap-size - 1; 
    MAX-HEAPIFY(A,1); 
} 

말합니다. 책에서는 MAX-HEAPIFY가 n 번 실행되므로 O(n lg n) 시간이라고합니다.

그러나 힙 크기가 1 씩 줄어들면 각 반복은 O(lg n!)이 아니어야합니까?

lg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!)이 맞습니까?

Answer 1

실제로는 Stirling's Approximation있다 : I 함께베이스 (2)의 대수를 첨가하고있어이 경우

O(log(n!)) = O(nlogn)