作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] 在n个数字之中寻找第二大的数字需要做될…
时间Mon Oct 13 07:22:24 2008
※ 引述《kao028kimo (羊羽)》之铭言：
: 已知现在有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是怎麽产生的呢？
这个, 用中文来说,
第二名只会输给第一名.
所以你只要把输给第一名的人找出来, 然後叫他们互比就行了.
在产生第一名的过程中的输家, 有 log(n) 个.
--
赵客缦胡缨，吾钩霜雪明。银鞍照白马，飒沓如流星。
十步杀一人，千里不留行。是了拂衣去，深藏身与名。
闲过信陵饮，脱剑膝前横。将炙啖朱亥，持觞劝侯赢。
三杯吐然诺，五岳倒为轻。眼花耳热後，意气素霓生。
就赵挥金锤，邯郸先震惊。千秋二壮士，烜赫大梁城。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 76.170.72.148
1F：推 flamerecca:这个是机率吧@@a 感觉他好像想问的是一个at least 10/13 10:18
2F：→ flamerecca:所以应该要试着提出证明s...吧XD 10/13 10:19
3F：推 a127a127:这是单淘汰赛的实际情况吧@@a 10/13 11:38
4F：→ final01:这是抠们书的范例吧 我记得看过.有证明 10/13 12:33