作者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