Re: [問題] 在n個數字之中尋找第二大的數字需要做될…
※ 引述《Leon (Achilles)》之銘言：
: ※ 引述《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) 個.
把淘汰樹畫出來就很清楚了:
O
/ \
O 3
/ \ / \
O 2 ....
/ \/ \
O 1 .....
假設 O是最後的勝利者，也就是最大的數 (需要比較 n-1 次)
因為第二大的數只比最大的數小，所以一定是被O淘汰掉的
以這個圖來說, N=8時 就是1, 2, 3 下的數字其中之一 (共 log(n)個)
因此只要求在1,2,3中的最大數, 就是所要的
全部中第二大的數 (需要 比較log(n) -1次)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.182.149
推
10/15 10:22, , 1F
10/15 10:22, 1F
→
10/16 22:23, , 2F
10/16 22:23, 2F
討論串 (同標題文章)