Re: [理工] [資結]-台大98-資工
※ 引述《EntHeEnd (...)》之銘言：
: Prove that the average height of the BST after inserting n integer values
: {1,2,...,n}in a random order is O(log n)
: 請問這題要怎樣證呢 ?
這題要按照定義來做。
之前版上的作法是證明第n個節點插入時候的深度的期望值，雖然也是O(lg n)，
我想兩者並不等價，因為該節點未必會增加樹高，有可能是插在靠近root的地方。
很多書上也有證明隨機插入n個節點之後，每個節點深度的期望值，也是O(lg n)，
但是也不是這題要的。
假設X(n)是隨機插入n個節點之後的期望高度。
按照定義，一個樹的高度是1 + Max(左子樹高度, 右子樹高度)
如果root是第i大的整數，在這種條件下樹的期望高度就是
1 + Max(X(i-1), X(n-i))
又插入的順序是隨機的，所以root是第i大的機率是1/n
n
因此 X(n) = (1/n)Σ 1 + Max(X(i-1), X(n-i))
i=1
然後解遞迴，就可得到X(n)的Closed Form。
話雖如此，但是分析很複雜
（http://en.wikipedia.org/wiki/Random_binary_tree#The_longest_path）
不過這題只是要求一個上限值，所以也不用去解開。
按照Cormen書上的方法，必需要用多一個隨機變數Y(n) = 2^X(n)
（我想大概是沒有其他簡單的辦法吧）
root是第i大的整數的時候，Y(n) = 2 * Max( Y(i-1), Y(n-i))
所以可得遞迴關係式
n
Y(n) = (2/n)Σ Max( Y(i-1), Y(n-i))
i=1
n
<=(2/n)Σ Y(i-1) + Y(n-i)
i=1
n-1
<=(4/n)Σ Y(i)
i=0
接下來就用一般方法解開，是一個多項式。X(n) = lg Y(n) = O(lg n)
（省略了很多細節，不過大致上是如此，想要看嚴謹的證明就看書吧）
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
02/14 12:44, , 1F
02/14 12:44, 1F
→
02/14 13:28, , 2F
02/14 13:28, 2F
→
02/14 13:30, , 3F
02/14 13:30, 3F
→
02/14 14:13, , 4F
02/14 14:13, 4F
→
02/14 14:13, , 5F
02/14 14:13, 5F
→
02/14 14:14, , 6F
02/14 14:14, 6F
→
02/14 14:14, , 7F
02/14 14:14, 7F
→
02/14 14:15, , 8F
02/14 14:15, 8F
推
02/14 14:17, , 9F
02/14 14:17, 9F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 7 篇)：