堆排序複雜

下面是堆排序的僞代碼陣列上堆排序複雜

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

回答

相關問題