堆排序复杂性

Question

下面是数组上HEAPSORT的伪代码

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的复杂性。我知道我们有n次迭代，每次迭代都有一个MAX-HEAPIFY。但是他MAX-HEAPIFY调用在每次迭代中都得到一个大小递减的HEAP。那么为什么每次迭代都有O（lgn）的复杂性？它是紧密绑定的吗？我可以看到相同的数学证明吗？

Answer 1

大O符号表示上限。正如你所说：

MAX-HEAPIFY的复杂度为O（h），其中h是堆的高度，最大值为log n。

我们不在乎堆是否变小。我们知道，在最坏的情况下，堆具有高度log n。我们这样做了n次，因此得到了n log n。

Answer 2

观察那个

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

现在，根据斯特灵的近似值，

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

因此：

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

这是O（n log n），因为n log n项支配着n项（我省略了O（log n）项，因为没有你的MathJax很难输入）。