[理工] 台大資工 資結

[carlossp (weyuruiwysfjgnjf)]

小弟有幾題問題想要問大家
 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
→ asjh612: 每個insert分別是O(lg1+lg2+..+lgn)=O(nlgn) 除n為averag
→ asjh612: e 所以是O(lgn) 不過這只是我的想法XDD
→ asjh612: 不保證一定對XDD
→ harryron9: 覺得我的寫法可能拿不到分 看看就好
→ harryron9: given a set {1,2....n} nodes
→ harryron9: each node may be a leaf in same posibility
→ harryron9: thus we know that in BST average serch time is
→ harryron9: O(lgn), for those leafs serch times = tree height
→ harryron9: then the BST will be average height O(lgn)
→ galapous: #1KbkLGsO