※ 引述《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