[理工] 台大資工 資結

看板Grad-ProbAsk作者 (weyuruiwysfjgnjf)時間9年前 (2015/02/03 20:26), 編輯推噓0(0推 0噓 10→)
留言10則, 3人參與, 最新討論串1/1
小弟有幾題問題想要問大家 98年資結 2.(4) Prove that the average height of the binary search tree after inserting n integer values{1,2....n} in a random order is O(logn). 這題毫無想法，只想到每次插入的可能性做高度平均,超複雜～～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.71.129 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422966406.A.176.html
→
02/03 22:03, , 1F
每個insert分別是O(lg1+lg2+..+lgn)=O(nlgn) 除n為averag
02/03 22:03, 1F
→
02/03 22:04, , 2F
e 所以是O(lgn) 不過這只是我的想法XDD
02/03 22:04, 2F
→
02/03 22:06, , 3F
不保證一定對XDD
02/03 22:06, 3F
→
02/03 22:19, , 4F
覺得我的寫法可能拿不到分 看看就好
02/03 22:19, 4F
→
02/03 22:21, , 5F
given a set {1,2....n} nodes
02/03 22:21, 5F
→
02/03 22:21, , 6F
each node may be a leaf in same posibility
02/03 22:21, 6F
→
02/03 22:23, , 7F
thus we know that in BST average serch time is
02/03 22:23, 7F
→
02/03 22:24, , 8F
O(lgn), for those leafs serch times = tree height
02/03 22:24, 8F
→
02/03 22:25, , 9F
then the BST will be average height O(lgn)
02/03 22:25, 9F
→
02/03 22:25, , 10F
02/03 22:25, 10F
‣ 更多 carlossp 的文章
文章代碼(AID): #1KqBw65s (Grad-ProbAsk)