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

看板Grad-ProbAsk作者 (andrew)時間7年前 (2018/07/02 16:06), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 7年前最新討論串1/1
https://i.imgur.com/iHYmxeE.jpg
雖然明白best,worst case，但卻搞不懂average，請問一下，有辦法導出average case 的time complexity嗎？（筆記寫algo版是O(logn)，但是，題目答案是O(n).....) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.135.187 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1530518807.A.7BB.html
推
07/02 19:39, 7年前 , 1F
應該是答案錯了，洪逸的書答案錯了不意外XD，推導的
07/02 19:39, 1F
→
07/02 19:39, 7年前 , 2F
話有一個例題是找Full BST的平均比較次數，可以參考
07/02 19:39, 2F
推
07/03 12:00, 7年前 , 3F
這題目不清不楚的 average 哪部分？
07/03 12:00, 3F
→
07/03 12:00, 7年前 , 4F
BST 是隨機產生 然後隨機 search？
07/03 12:00, 4F
→
07/03 12:00, 7年前 , 5F
還是給定 BST 然後隨機 search
07/03 12:00, 5F
→
07/03 12:24, 7年前 , 6F
我也不是很懂，它沒給，大概是隨機吧！
07/03 12:24, 6F
‣ 更多 Aa841018 的文章
文章代碼(AID): #1RETqNUx (Grad-ProbAsk)