從最大堆提取的運行時間是多少？

「詹姆斯聲稱，他成功實現從需要O最大堆（ExtractMax）提取（（log n）的^ 0.5）

解釋爲什麼詹姆斯過錯

我知道，從最大堆提取需要O（log n）的，但我怎麼能證明詹姆斯是錯的？

2012-06-02 Noam Holin

可以看出here，構建堆可以做到在O（n）中。現在如果提取最大值可以在O（（log n）^ 0.5）中完成，那麼通過重複提取最大元素可以將整個集合排序爲n * O（（log n）^ 0.5）。然而，這是不可能的，因爲排序的下界是n * logn。

因此，詹姆斯的不存在。

來源

2012-06-02 22:34:33 Dino

正確！稍作修改：**比較排序**的下限是n * logn。你可以用O（n）進行基數排序。 – usr

真的聰明的做法，但我認爲這有點矯枉過正 – acattle

基數排序在O（n）？只有當你假設你想要排序的不同數量的不同數值時（例如2^32）。否則它是n * [表示長度]，其中[表示長度]將是log（n）。 – Dino

@ Duh將您的提取問題轉換爲排序問題的解決方案實際上非常有創意。找到排序爲O（n * log n）的證明應該不會太難，並且在研究將一個問題轉換爲另一個問題的算法時非常普遍（例如，所有NP-Complete問題都是轉換彼此，這就是你如何證明他們是NP-Complete）。這就是說，我認爲有一個更簡單的解決方案。

你直接在你的問題中說過：從二進制堆中提取O（log n）。想想爲什麼它是O（log n）。什麼是二進制堆的結構？需要從二進制堆中提取什麼操作？爲什麼最糟糕的情況是log n操作？這些限制是否通過實施受到影響？

現在，請記住，有兩個部分James的權利要求：

他可以在O提取物（（log n）的^ 0.5）
他使用二進制堆。

鑑於您對二進制堆的瞭解，這兩種說法都可以正確嗎？爲什麼或者爲什麼不？有矛盾嗎？如果是這樣，爲什麼會有矛盾？最後，想想這對詹姆斯意味着什麼。

來源

2012-06-03 10:06:40 acattle

從最大堆提取的運行時間是多少？

回答

相關問題