二叉樹搜索的複雜性

我在查找二進制堆時發現有衝突的信息。據此，https://en.wikipedia.org/wiki/Binary_heap，它是O（n）（編輯：它實際上是O（log n）），根據這個，Search an element in a heap，它是O（n/2）。二叉樹搜索的複雜性

來源

2016-05-23 tobias_theblowhard

我很抱歉，我的意思是維基百科鏈接表示它是O（log n）。 –

由於維基百科上提到的* heap屬性，真正的二進制堆將是O（n/2）：*如果A是B的父節點，則節點A的密鑰相對於節點B的密鑰排序在整個堆中應用相同的排序*排序實際上將搜索的努力分成了兩半。但是，這種複雜性在圖上是線性的，所以它基本上平均爲O（n）。二叉搜索樹具有有序子元素，並且可以執行復雜度爲O（log n）的真二分搜索。 –

如果「搜索」意味着在堆中搜索特定的數據，那麼它應該是'O（n）'。我不確定維基頁面的實際含義。但通常堆不支持「搜索」操作 - 它們只是沒有被設計來做到這一點。也許有人應該修改wiki頁面，或者更清楚地說明它。 – WhatsUp

維基百科對此只是錯誤的。二進制堆不是爲了搜索各個元素而設計的，而是爲了訪問最小的元素而優化的。例如，這使得他們能夠在時間Θ（n）中建造;它們所需的排序並不像二分查找樹那樣嚴格。

看起來有人已經更新了維基百科，這很好。感謝您指出了這一點！

一注意 - 術語O（n/2），雖然在技術上是正確的，但被認爲是對大O符號的不良使用。 Big-O符號忽略了常數因素，所以O（n/2）與O（n）相同。如果要計算最終要完成的具體操作次數，請避免使用大O符號，並說「需要完全n/2次比較」。

來源

2016-05-25 00:26:27 templatetypedef

二叉樹搜索的複雜性

回答

相關問題