- 304 名前：デフォルトの名無しさん mailto:sage [2006/02/12(日) 03:01:20 ]
- >>296
完全二分木でトーナメントを考えよう。
一番小さい要素を見つけるのにn-1回の比較が必要。
二番目に小さい要素は一番小さい要素の対戦相手のどれか。
木の高さはceil(log n)で木の一番上には対戦相手はいないから、
二番目に小さい要素の候補たりえるものはceil(log n)-1個
この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。
したがって比較回数は、
(n-1)+ceil(log n)-2<n+logn-2
ただし、ceil(x)はxの小数点以下切り上げの関数
