※ 引述《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(nlgn)
: 想請問這題答案該寫O(nlogn) 還是O(n)呢？
: Top-down Bottom-up
這兩種應該是建heap的
: 感謝:)
會特地回是想借標題問一下
如果是要證random建BST是O(nlgn)
請問應該要怎麼證呢?
因為我看cormen是有牽扯到機率&期望值的東西
可是沒學過0.0
不知道有沒有高手有不用到機率的方法證呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.24.2