作者kao028kimo (羊羽)
看板Prob_Solve
标题[问题] 在n个数字之中寻找第二大的数字需要做几次比较？
时间Thu Oct 9 12:21:18 2008
已知现在有n个不相同的数
题目要求找出第二大的数 需要做几次的比较？
我的作法：
先找出最大的数
由数字之中挑选两数做比较 再由剩下来的n-2个数全部挑上来比较
所以需要花n-1次的比较
现在问题来了
题目(其实是演算法的回家作业)要求
Show that to find the second largest number requires at least n-2+logn
comparisons
也就是说
在n-1个数中挑最大的数至少要logn-1 comparisons
以上就是我最不解的部份
究竟那个log是怎麽产生的呢？
--
踽踽独行 学分不足 人际破碎 老大不小 一事无成
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.189.20
1F：推 netsphere:类似quick sort的方法 10/09 12:23
2F：推 ferng1021:也是类似单淘汰赛产生冠亚军的方法 10/09 13:27
3F：推 march20:应该比较像奥运抬拳道铜牌的决定方法才对 10/09 16:58
4F：推 march20:不过我觉得这个 "at least" 给的很怪. 真的要 show at 10/09 16:58
5F：推 march20:least 是证明下界, 这拿来出 algo 的作业有点.... 10/09 16:59
6F：→ kao028kimo:n大可以更详细的说明吗 10/10 23:37
7F：推 ckclark:就是quicksort 不过每次都有一边不用继续做下去 10/11 00:12