作者lionhome20 (林北大GG)
看板Prob_Solve
標題[問題] 用最少比較次數找最大、最小等值
時間Thu Mar 31 18:12:50 2016
各位神人好
想請問在int array[5000]裡
如何用最少的compare次數
找出最大 最小 次大 次小的值
有沒有小於下列5000*4次 compare的找法
(找每一個數都用暴力法)
for(i=0;i<5000;i++)
if(array[i] > Max)
Max = array[i]
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.122.2
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1459419175.A.56B.html
1F：推 LPH66: 概念: 一個數沒比過不會知道他是不是最大 03/31 20:38
感謝提醒 已修正題目 目前有想到用Heap sort
※ 編輯: lionhome20 (111.248.31.18), 03/31/2016 22:20:19
2F：推 springman: 同時找最大與最小，有 5000*3/2 次比較的方法。 04/01 03:59
3F：→ springman: 找最大與次大，有 n + log_2 n 次比較的方法。 04/01 03:59
4F：→ springman: 所以看來應該有 5000*3/2 + 2*log_2 5000 次比較的方法 04/01 09:57
5F：→ springman: 找到這四個資料，只是程式寫起來或許比較麻煩。 04/01 09:57
6F：推 DJWS: sorting network 這是超級困難的問題 04/01 10:38
7F：推 FRAXIS: sorting network 的限制應該太強了吧 04/01 18:46
8F：推 FRAXIS: 因為 sorting network 不能依照之前比較的結果來選擇下 04/01 18:52
9F：→ FRAXIS: 一次要比較的元素 04/01 18:52
10F：推 DJWS: 對耶 那麼 樓上說的這種情況 有沒有專有名詞？ 04/02 09:38
11F：推 FRAXIS: decision tree? 04/02 09:46
12F：推 janice001: 都n log n 了 幹嘛不直接quick sort? 04/16 11:20
13F：推 j2jx008447: 樓上的方法排序後，索引值頭尾不就是答案了嗎 05/02 03:36