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

看板Grad-ProbAsk作者 (M*schief)時間14年前 (2012/01/24 22:45), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串4/5 (看更多)
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
推
01/24 22:48, , 1F
top-down跟bottom-up那個是建heap的複雜度吧
01/24 22:48, 1F
→
01/24 22:49, , 2F
我記得某年台大的考題是要證random建BST是O(nlgn)
01/24 22:49, 2F
→
01/24 22:52, , 3F
完蛋 翻錯頁XDDD
01/24 22:52, 3F
→
01/24 23:18, , 4F
我翻Cormen查到期望高度為O(lgn)
01/24 23:18, 4F
→
01/24 23:19, , 5F
請問因有n個資料每次皆須調整O(lgn)所以答案是O(nlgn)嗎?
01/24 23:19, 5F
推
01/25 15:41, , 6F
BST 不用balance 所以就O(logN)
01/25 15:41, 6F
‣ 更多 mickeyha 的文章
文章代碼(AID): #1F7iGd6i (Grad-ProbAsk)
‣ 更多 mickeyha 的文章
文章代碼(AID): #1F7iGd6i (Grad-ProbAsk)