[理工] [演算法] Prune and Search

看板Grad-ProbAsk作者 (小YO)時間13年前 (2011/01/13 20:55), 編輯推噓1(1推 0噓 5→)
留言6則, 5人參與, 最新討論串1/1
有關演算法Prune and Search，從n個元素找第k小的數的問題 在挑選變數p時(將數列分成 <p,=p,>p)， 為什麼在排序選組中位數時，排序的時間是Θ(1)? 挑選p的演算法步驟如下： step1 : 將n個元素分成n/5組 step2 : 將每一集合中的5個點排序，並找出每一個集合的中位數，令此集合為S step3 : 取p為S的中位數 謝謝各位解答 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.224.131.15
→
01/13 21:19, , 1F
是問step2嗎 @.@?
01/13 21:19, 1F
→
01/13 21:29, , 2F
因為是5個「固定」的數找中位數，所以時間會是固定的O(1)
01/13 21:29, 2F
→
01/13 21:30, , 3F
^^^^^^^ ouch，應該說「做排序」
01/13 21:30, 3F
推
01/13 21:31, , 4F
因為5個很少的關係吧 不管用什麼方式排序都可以很快完成
01/13 21:31, 4F
→
01/13 21:43, , 5F
原來是這樣 謝謝^^
01/13 21:43, 5F
→
01/15 19:23, , 6F
固定五個數可以寫一排code爆破得出中間的數，跟n沒關係
01/15 19:23, 6F
‣ 更多 boy5548 的文章
文章代碼(AID): #1DBlOqoZ (Grad-ProbAsk)