PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 在n個數字之中尋找第二大的數字需要做될…

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間16年前 (2008/10/19 02:53)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/3 (看更多)

※ 引述《Lucemia (生の直感、死の予感)》之銘言： : ※ 引述《Leon (Achilles)》之銘言： : : 這個, 用中文來說, : : 第二名只會輸給第一名. : : 所以你只要把輸給第一名的人找出來, 然後叫他們互比就行了. : : 在產生第一名的過程中的輸家, 有 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次) 有人問, exist ~= at least, 我想了一下, 這的確不太好證明, 不過, exist 就代表了 at most. Say, if there exist a algorithm, smaller than n + log n - 2. Assume we only have {a,b} two elements.. than.. need 0 comparision! 如果你要比較分析的証明, 你可以畫一 tree, 代表 parial relation. 假設 {a,b,c,d} 四個 element, 在三次比較後, we have a > b, c > d, a > c. then it will like a b c d 而我們最後希望建構 relation tree a b c d 你必須去比較 a 的 child. 我已經忘記這個 operation 的名詞了, btw, 這邊你就可以看到, 為何第一步需要採用淘汰賽的形式. -- 趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。十步殺一人，千里不留行。是了拂衣去，深藏身與名。閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 76.170.72.148