[問題] 請問取中間值所需的比較次數

看板Prob_Solve作者 (D)時間14年前 (2009/12/22 13:58), 編輯推噓3(3推 0噓 5→)
留言8則, 5人參與, 最新討論串1/1
請問有沒有人知道取中間值所需的最少比較次數是多少次？ 譬如 3個數字取中間值,最少需要三次 5個數字,最少需要六次 7個數字呢？ 有理論公式可推到2n+1個嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.96.112.162
→
12/22 16:38, , 1F
2n+1...請看一下http://0rz.tw/Fky2Z 吧!
12/22 16:38, 1F
→
12/22 16:45, , 2F
抱歉,我不知道這有什麼幫助,如果只是演算法,k-selection可以用
12/22 16:45, 2F
→
12/22 16:45, , 3F
但這不是我要問的問題
12/22 16:45, 3F
※ 編輯: JFD 來自: 140.96.112.162 (12/22 16:51) ※ JFD:轉錄至看板 puzzle 12/22 16:56
推
12/22 21:16, , 5F
12/22 21:16, 5F
推
12/22 21:19, , 6F
我幫你google了一下，都沒看到有公式，只有看到bound而已。
12/22 21:19, 6F
→
12/22 21:51, , 7F
very thanks
12/22 21:51, 7F
→
01/08 07:52, , 8F
(n-1)+(n-1)/2
01/08 07:52, 8F
‣ 更多 JFD 的文章
文章代碼(AID): #1BC5_rLA (Prob_Solve)