4

我正在阅读 CLRS，它说 heapsort 是

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-HEAPIFYn次，因此是O(n lg n)时候了。

但是，如果堆的大小每次迭代都缩小 1，不是O(lg n!)吗？

会的lg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!)，对吧？

4

1 回答 1

10

实际上是斯特林近似：

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

于 2014-04-07T00:59:09.987 回答