看板 [ Prob_Solve ]
討論串[問題] 在n個數字之中尋找第二大的數字需要做될…
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
Re: [問題] 在n個數字之中尋找第二大的數字需要做될…
推噓2(2推 0噓 2→)留言4則，0人參與, 最新作者Leon (Achilles)時間16年前 (2008/10/13 07:22), 編輯資訊
1
0
0
內容預覽:
這個, 用中文來說,. 第二名只會輸給第一名.. 所以你只要把輸給第一名的人找出來, 然後叫他們互比就行了.. 在產生第一名的過程中的輸家, 有 log(n) 個.. --. 趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。. 十步殺一人，千里不留行。是了拂衣去，深藏身與名。. 閑過信陵飲，脫劍膝前
#2
Re: [問題] 在n個數字之中尋找第二大的數字需要做될…
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者Lucemia (生の直感、死の予感)時間16年前 (2008/10/13 21:41), 編輯資訊
1
0
0
內容預覽:
把淘汰樹畫出來就很清楚了:. O. / \. O 3. / \ / \. O 2 ..... / \/ \. O 1 ...... 假設 O是最後的勝利者，也就是最大的數 (需要比較 n-1 次). 因為第二大的數只比最大的數小，所以一定是被O淘汰掉的. 以這個圖來說, N=8時 就是1, 2, 3
#3
Re: [問題] 在n個數字之中尋找第二大的數字需要做될…
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者Leon (Achilles)時間16年前 (2008/10/19 02:53), 編輯資訊
0
0
0
內容預覽:
有人問, exist ~= at least,. 我想了一下, 這的確不太好證明, 不過, exist 就代表了 at most.. Say, if there exist a algorithm, smaller than n + log n - 2.. Assume we only have {
(還有333個字)
首頁
上一頁
1
下一頁
尾頁