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

[Aa841018 (andrew)]

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
推 ponponjerry: 應該是答案錯了，洪逸的書答案錯了不意外XD，推導的
→ ponponjerry: 話有一個例題是找Full BST的平均比較次數，可以參考
推 FRAXIS: 這題目不清不楚的 average 哪部分？
→ FRAXIS: BST 是隨機產生 然後隨機 search？
→ FRAXIS: 還是給定 BST 然後隨機 search
→ Aa841018: 我也不是很懂，它沒給，大概是隨機吧！