[問題] 演算法..找第二小的元素(n+logn-2比較)

[mqazz1 (無法顯示)]

我想請教一題演算法..

Show that the second smallest of n elements

can be found in (n+logn-2) comparisons in the worst case.



找第二小的元素

在最差狀況下

可以使用 n + logn - 2 次比較找到



請問這題應該從哪個部份下手會比較方便呢?


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.24.185
→ gozule:從logn大概可以想到用tree，方法類似winner tree