1. PTT
  2. Grad-ProbAsk

[理工] 資結5-81 BST 的average case！

作者: Aa841018 (andrew)   2018-07-02 16:06:45
https://i.imgur.com/iHYmxeE.jpg
雖然明白best,worst case，但卻搞不懂average，請問一下，有辦法導出average case
的time complexity嗎？（筆記寫algo版是O(logn)，但是，題目答案是O(n).....)
作者: ponponjerry (ponpon)   2018-07-02 19:39:00
應該是答案錯了，洪逸的書答案錯了不意外XD，推導的話有一個例題是找Full BST的平均比較次數，可以參考
作者: FRAXIS (喔喔)   2018-07-03 12:00:00
這題目不清不楚的 average 哪部分？BST 是隨機產生 然後隨機 search？還是給定 BST 然後隨機 search
作者: Aa841018 (andrew)   2018-07-03 12:24:00
我也不是很懂，它沒給，大概是隨機吧！
繼續閱讀
[理工] 線代 2-39 範例8 LILUNC[理工] 離散 partial sumwilson50101[理工] 離散 數學歸納法sylvia9511[理工] 離散 1-8susukila[理工]線代子嘉題庫7-190wilson50101[理工] 資料結構 執行次數的問題AAQ8[理工] 線代子嘉題庫7-165wilson50101[理工] 線代子嘉題庫7-132wilson50101[理工] 線代子嘉題庫7-157wilson50101[理工] 線代子嘉題庫7-150wilson50101

Links booklink

Contact Us: admin [ a t ] ucptt.com