堆排序复杂

下面是堆排序的伪代码阵列上堆排序复杂

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的复杂性。我明白我们有每次MAX-HEAPIFY的n次迭代。但是他的MAX-HEAPIFY调用在每次迭代中都会缩小尺寸。那么每个迭代如何可以具有O（lgn）的复杂性？它紧紧地绑定了吗？在哪里我可以看到相同的数学证明？

来源

2016-10-04 lalatnayak

相关：http://stackoverflow.com/questions/39691923/build-max-heap-running-time-for-array-sorted-in-decreasing-order –

观察到

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

现在，斯特灵公式，

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

所以：

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

which is O(n log n) because the n log n长期占主导地位的n项（和O（log n）的学期我遗漏了，因为它太难以输入MathJax）。

来源

2016-10-04 20:47:24 rici

美丽！只是一个错字，我认为它应该是日志（n/e） – Nicholas

@nicholas：非常正确，谢谢。固定。 – rici

你是对的 – lalatnayak

大O符号表示上部界限。如您所说：

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

我们不关心堆是否变小。我们知道最差，堆有高度日志n。我们这样做n次，因此n log n。

来源

2016-10-04 15:34:29 orlp

下面是BUILD-MAX-HEAP的伪代码 _build-MAX-HEAP（A） A.heapsize =则为a.length 对于i =则为a.length/2 DOWNTO 1 MAX-HEAPIFY（A，I）在上述我们考虑堆的深度来计算O（n）的复杂度。我们为什么不在HEAPSORT中做？ – lalatnayak

@lalatnayak因为我们已经欺骗了，并且已经知道我们可以做比heapsort更好的O（n log n）（提示：我们需要一个下界）。正因为如此，我们并没有试图改善我们的上限。 – orlp

谢谢，我怀疑如果我能想出没有提示:) – lalatnayak

回答

相关问题