[理工] [資結] 95台大電機

[mickeyha (M*schief)]

The complexity of inserting a node into an arbitrary

binary search tree is (n is the number of nodes in the tree):

[註]arbitrary - 任意

問：ramdonized data建立BST時間複雜度 => ?

想請問這題答案該寫O(nlogn) 還是O(n)呢？
                  Top-down    Bottom-up

感謝:)

--
Why Not ：-P

http://whynot-p.blogspot.com/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 1.162.56.71
推 mqazz1:top-down跟bottom-up那個是建heap的複雜度吧
→ mqazz1:我記得某年台大的考題是要證random建BST是O(nlgn)
→ mickeyha:完蛋 翻錯頁XDDD
→ mickeyha:我翻Cormen查到期望高度為O(lgn)
→ mickeyha:請問因有n個資料每次皆須調整O(lgn)所以答案是O(nlgn)嗎?
推 magicnick:BST 不用balance 所以就O(logN)