作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 资结5-81 BST 的average case！
时间Mon Jul 2 16:06:45 2018
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1530518807.A.7BB.html
1F：推 ponponjerry: 应该是答案错了，洪逸的书答案错了不意外XD，推导的 07/02 19:39
2F：→ ponponjerry: 话有一个例题是找Full BST的平均比较次数，可以参考 07/02 19:39
3F：推 FRAXIS: 这题目不清不楚的 average 哪部分？ 07/03 12:00
4F：→ FRAXIS: BST 是随机产生 然後随机 search？ 07/03 12:00
5F：→ FRAXIS: 还是给定 BST 然後随机 search 07/03 12:00
6F：→ Aa841018: 我也不是很懂，它没给，大概是随机吧！ 07/03 12:24