[問題] 在n個數字之中尋找第二大的數字需要做幾次比較？

[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是怎麼產生的呢？

--
踽踽獨行 學分不足 人際破碎 老大不小 一事無成

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.115.189.20
推 netsphere:類似quick sort的方法
推 ferng1021:也是類似單淘汰賽產生冠亞軍的方法
推 march20:應該比較像奧運抬拳道銅牌的決定方法才對
推 march20:不過我覺得這個 "at least" 給的很怪. 真的要 show at
推 march20:least 是證明下界, 這拿來出 algo 的作業有點....
→ kao028kimo:n大可以更詳細的說明嗎
推 ckclark:就是quicksort 不過每次都有一邊不用繼續做下去