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

[boy5548 (小YO)]

有關演算法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
→ mqazz1:是問step2嗎 @.@?
→ ybite:因為是5個「固定」的數找中位數，所以時間會是固定的O(1)
→ ybite:                     ^^^^^^^ ouch，應該說「做排序」
推 weiyung:因為5個很少的關係吧 不管用什麼方式排序都可以很快完成
→ boy5548:原來是這樣 謝謝^^
→ xygod:固定五個數可以寫一排code爆破得出中間的數，跟n沒關係