Heapsort。如何模擬最壞情況？

我很清楚如何對它進行編程，但我並不確定這個定義，例如如何用數學術語寫下來。一個正常的heapsort在O表示法中用N個元素完成。所以O（日誌（n））我剛開始heapsort，所以我可能會有點偏離這裏。但是我怎麼能找到一個隨機元素，當有N個元素？然後選擇該隨機元素並刪除它？我在想，在最壞的情況下 - 它必須穿過整棵樹（因爲元素可能在第一個地方或最後一個地方，例如最高或最低）。但是我怎樣才能用數學術語寫下來呢？Heapsort。如何模擬最壞情況？

來源

2012-10-28 XCoderX

您想爲堆排序數學專門定義最壞的情況下？我不認爲最終結果會是非常數學的。更像元元代碼/數學/文本。並且Big-O表示法用大寫字母O表示，而不是0. – keyser

對不起，我的英語有點不穩定。然而，我提出了log（2（n）），因爲在最壞的情況下，我們正在尋找的隨機元素是在樹的底部，每個下一個分支都有兩個額外的元素） - 我希望我的意思很清楚。 – XCoderX

哦，你想在大O的答案？ heapsort的最壞情況是O（n log n） – keyser

Heapsort的最壞情況下的性能是O（n log n）的，並且引用alestanis：在最大堆

最大：O（1）。最小分鐘：O（1）。 O（n）中的相反情況。

Here是一個SO-answer解釋如何在O（1）中執行相反的情況，如果您自己創建堆。

來源

2012-10-28 22:31:22 keyser

要建立maxheap陣列在最壞情況是O（n），並在最壞的情況下最大heapify complexcity是O（LOGN），所以堆排序在最壞情況是O（nlogn）

來源

2014-06-21 11:08:45 Sazib

Heapsort。如何模擬最壞情況？

回答

相關問題