※ 引述《mqazz1 (無法顯示)》之銘言：
: 我想請教一題演算法..
: Show that the second smallest of n elements
: can be found in (n+logn-2) comparisons in the worst case.
: 找第二小的元素
: 在最差狀況下
: 可以使用 n + logn - 2 次比較找到
: 請問這題應該從哪個部份下手會比較方便呢?
我看過的做法如下:
先把 n 個元素每兩個放在一組, 每一組做一次比較取出較小的元素
o o <= 底層每兩個元素比較, 較小者勝出
/ \ / \
o o o o <= 原本有 n 個元素, 放在底層
然後把每一組取出的較小元素繼續兩兩一組, 每一組做一次比較取出較小的元素
o
/ \
/ \
o o
/ \ / \
o o o o
這樣直到取得最小元素, 共做了 n-1 次比較 --- 因為每次比較恰好淘汰一個元素.
接著, 第二小元素一定有與最小元素比較過 --- 因為第二小元素在上面那個 tree 裡面,
最終沒有勝出 (i.e., 被放到頂上), 這一定是被最小元素打敗的.
而與最小元素做過比較的元素頂多 lg n 個, 在這 lg n 個裡面取最小的元素只要
lg n-1 次比較, 這也就是全部 n 個數裡面的第二小數!
總共比較次數為 n-1 + lg n - 1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.99.236