看板 [ Grad-ProbAsk ]
討論串[理工] [資結]-台大98-資工
共 7 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
2
下一頁
尾頁
#7
[理工] [資結]-台大98-資工
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者b76516 (阿聰)時間16年前 (2010/02/19 20:00), 編輯資訊
0
0
1
內容預覽:
請問98台大軟體設計第6題第1小題. 連結在此. http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf. 要證明 l(u,w)+d(v,u)-d(v,w)>=0. 可是我想到一個反例. -10. u--------->w. ^ ^. -2 \ /-
#6
Re: [理工] [資結]-台大98-資工
推噓2(2推 0噓 7→)留言9則，0人參與, 最新作者FRAXIS (喔喔)時間16年前 (2010/02/14 12:10), 編輯資訊
0
0
1
內容預覽:
這題要按照定義來做。. 之前版上的作法是證明第n個節點插入時候的深度的期望值，雖然也是O(lg n)，. 我想兩者並不等價，因為該節點未必會增加樹高，有可能是插在靠近root的地方。. 很多書上也有證明隨機插入n個節點之後，每個節點深度的期望值，也是O(lg n)，. 但是也不是這題要的。. 假設X
(還有611個字)
#5
Re: [理工] [資結]-台大98-資工
推噓0(0推 0噓 26→)留言26則，0人參與, 最新作者EntHeEnd (...)時間16年前 (2010/02/07 00:41), 編輯資訊
0
0
0
內容預覽:
請問是要從第一個大於Xj的數字還使取遞減排序的嗎(看起來是這樣 也合理). 因為21是第一個大於17的數 如果21之前再加上 2 22. 要取的Xi就變成 22 21 19 這樣 ?. 這樣是相當於網頁中的down-records嗎 ? 相當於網頁中的up-records ? (Xi~Xj Xj恰為
(還有289個字)
#4
Re: [理工] [資結]-台大98-資工
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者taitin (小南)時間16年前 (2010/02/06 23:44), 編輯資訊
0
0
1
內容預覽:
抱歉這邊錯了，應該要修正成. 1.{G|for all Xi;Xk>Xi>Xj;1<=k<=i<j<=n}. 2.{L|for all Xi;XK<Xi<Xj;1<=k<=i<j<=n} (<= 小於或等於). G的意思是，所有在位置j之前，Xk為key值大於Xj的數字. 而Xi，為Xk到Xj中所有
(還有232個字)
#3
Re: [理工] [資結]-台大98-資工
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者EntHeEnd (...)時間16年前 (2010/02/06 20:29), 編輯資訊
0
0
1
內容預覽:
為什麼Xj同時有大於和小於root兩種情況呢. 是分成兩個case討論嗎 ?請問插入第i的點 增加高度的期望值為什麼是1/i呢. 是因為第i個點要插入時 會有i個可能(目前null pointer數)嗎.... 然後最後會在最長path的只有其中一個leaf 所以機率是1/i嗎. 可是這樣想也怪怪的
(還有397個字)
首頁
上一頁
1
2
下一頁
尾頁