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