algorithm - 为什么堆排序不是 lg(n!)？

Question

我正在阅读 CLRS，它说堆排序是

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 是 O(lg n)。书中说它运行 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 :

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