看板 [ Prob_Solve ]
討論串[問題] 經典的linear-time median問題
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 經典的linear-time median問題
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者mqazz1 (無法顯示)時間14年前 (2010/04/28 22:56), 編輯資訊
1
0
0
內容預覽:
題目我想應該很多人都看過了... Suppose that you have a "black-box" worst-case linear-time median. sub-routine. Give a simple, linear-time algorithm that solves the
(還有596個字)
#2
Re: [問題] 經典的linear-time median問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者LPH66 ((short)(-15074))時間14年前 (2010/04/29 01:27), 編輯資訊
0
0
0
內容預覽:
它是指搜尋 A 陣列的第 k 個. 應該是如推文所說其實要是 SELECTION(A2, k - n/2). 原因你可以仔細想想 DIVIDE 拆開之後 你要抓的東西變成子序列的第幾名. 於是當 A 的大小為 n 時. BLACK-BOX 花費 O(n). DIVIDE 也是 O(n) (可參考 q
(還有295個字)
首頁
上一頁
1
下一頁
尾頁