Re: [問題] 在n個數字之中尋找第二大的數字需要做될…
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間16年前 (2008/10/13 07:22)推噓2(2推 0噓 2→)留言4則, 3人參與討論串1/3 (看更多)
※ 引述《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
推
10/13 10:18, , 1F
10/13 10:18, 1F
→
10/13 10:19, , 2F
10/13 10:19, 2F
推
10/13 11:38, , 3F
10/13 11:38, 3F
→
10/13 12:33, , 4F
10/13 12:33, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
