[問題] 在n個數字之中尋找第二大的數字需要做幾次比較？
看板Prob_Solve (計算數學 Problem Solving)作者kao028kimo (羊羽)時間16年前 (2008/10/09 12:21)推噓6(6推 0噓 1→)留言7則, 5人參與討論串1/1
已知現在有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
推
10/09 12:23, , 1F
10/09 12:23, 1F
推
10/09 13:27, , 2F
10/09 13:27, 2F
推
10/09 16:58, , 3F
10/09 16:58, 3F
推
10/09 16:58, , 4F
10/09 16:58, 4F
推
10/09 16:59, , 5F
10/09 16:59, 5F
→
10/10 23:37, , 6F
10/10 23:37, 6F
推
10/11 00:12, , 7F
10/11 00:12, 7F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
