作者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/cn.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