堆排序复杂度

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 是堆的高度，其最大值为登录。

完全不明白的是为什么HeapSort的复杂度是nlogn。我知道我们有 n 次迭代，每次迭代都是 MAX-HEAPIFY。但是他的 MAX-HEAPIFY 调用在每次迭代中都会得到一个大小递减的堆。那么每次迭代如何具有 O(lgn) 的复杂性？绑定的严不严？我在哪里可以看到相同的数学证明？

Answer 1

大 O 表示法表示上限界限。正如你所说：

MAX-HEAPIFY has a complexity of O(h) where h is the height of the heap which has a max value of 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)<sup>n</sup>

所以：

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 太难打字了).

Heap Sort Complexity