Re: [理工] [algo]-找第二小的數
※ 引述《yesa315 (XD)》之銘言：
: cormen的習題有一題 如何在 n + [log n] - 2 找出第二小的數
: 看解答看好久不太了解他的意思 為什麼已經偷偷建了tree?
: 感謝
演算法:
STEP1 兩兩比找最小，贏的人再兩兩比找最小
STEP2 最後比那些和最小的人交過手的
範例:
3 8 6 4 1 5 2 9
3 4 1 2
3 1
1
此時對 3 2 5 找最小即可，也就是 2
分析:
STEP 1 總共用了 n-1 個比較
STEP 2 其實我們就在建一個 winner tree 此 tree height 不超過 logn
但是 winner 在 step 2 不用和自己比，所以 STEP 2 共用了 logn - 1 個比較
STEP 1 + STEP 2 = n + logn - 2
註:
不過這個方法你需要準備額外 logN 的空間去紀錄誰和最小的比過
標準的用空間換時間的做法
※ 編輯: Am7 來自: 203.70.75.96 (03/03 01:34)
討論串 (同標題文章)