PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 用最少比較次數找最大、最小等值

看板Prob_Solve (計算數學 Problem Solving)作者 (林北大GG)時間8年前 (2016/03/31 18:12), 8年前編輯推噓9(9推 0噓 4→)
留言13則, 6人參與, 最新討論串1/3 (看更多)
各位神人好 想請問在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://www.ptt.cc/bbs/Prob_Solve/M.1459419175.A.56B.html
推
03/31 20:38, , 1F
概念: 一個數沒比過不會知道他是不是最大
03/31 20:38, 1F
感謝提醒 已修正題目 目前有想到用Heap sort ※ 編輯: lionhome20 (111.248.31.18), 03/31/2016 22:20:19
推
04/01 03:59, , 2F
同時找最大與最小，有 5000*3/2 次比較的方法。
04/01 03:59, 2F
→
04/01 03:59, , 3F
找最大與次大，有 n + log_2 n 次比較的方法。
04/01 03:59, 3F
→
04/01 09:57, , 4F
所以看來應該有 5000*3/2 + 2*log_2 5000 次比較的方法
04/01 09:57, 4F
→
04/01 09:57, , 5F
找到這四個資料，只是程式寫起來或許比較麻煩。
04/01 09:57, 5F
推
04/01 10:38, , 6F
sorting network 這是超級困難的問題
04/01 10:38, 6F
推
04/01 18:46, , 7F
sorting network 的限制應該太強了吧
04/01 18:46, 7F
推
04/01 18:52, , 8F
因為 sorting network 不能依照之前比較的結果來選擇下
04/01 18:52, 8F
→
04/01 18:52, , 9F
一次要比較的元素
04/01 18:52, 9F
推
04/02 09:38, , 10F
對耶 那麼 樓上說的這種情況 有沒有專有名詞？
04/02 09:38, 10F
推
04/02 09:46, , 11F
decision tree?
04/02 09:46, 11F
推
04/16 11:20, , 12F
都n log n 了 幹嘛不直接quick sort?
04/16 11:20, 12F
推
05/02 03:36, , 13F
樓上的方法排序後，索引值頭尾不就是答案了嗎
05/02 03:36, 13F
‣ 更多 lionhome20 的文章
文章代碼(AID): #1M_FWdLh (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 lionhome20 的文章
文章代碼(AID): #1M_FWdLh (Prob_Solve)