二分探索木による探索の平均探索回数について

佐藤道一

トップページへ

これは，2005年4月7日の書き下ろしです． 関連ページ 二分探索法の平均探索回数について クイックソートでの平均比較回数について 　二分探索木による探索で，n 件のデータから探索する場合， 　　平均探索回数は O(log n)　　(最悪はO(n)) といったことが，情報処理技術者試験の参考書（但し，第三者が出しているものであって公式参考書はそもそも存在しない）に厳密な証明なしにしばしば書いてある．この点を厳密に述べる． 　詳しくは，平均探索回数をμn で表すと， (1)　　μn ≦ 2 ln n ＋ 1 (2)　　上式の係数２と定数項１は改良できない． (3)　　μn 〜 2 ln n　（すなわち，左右の比の極限は１） が成り立つ． （証明）（第１段）n ≧ 2 を固定する．二分探索木の根 j を固定した場合の探索回数を考える． 　　探索対象が根の場合は１回で，これは確率 1/n で起きる． 　　探索対象が根の左の場合は左に j − 1 個あるので平均 1 ＋μj−1 回で，これは確率 (j − 1)/n で起きる． 　　探索対象が根の左の場合は右に n − j 個あるので平均 1 ＋μn−j 回で，これは確率 (n − j)/n で起きる． これらの平均は 　　　 1/n ＋ (1 ＋μj−1)(j − 1)/n ＋ (1 ＋μn−j)(n − j)/n 　　＝ 1 ＋ {(j − 1)/n}μj−1＋{(n − j)/n}μn−j 　　　　（便宜上μ0 ＝ 0 とする） となり，更に j について平均をとると， 　　μn ＝ (1/n)Σj＝1 n　 [1 ＋ {(j − 1)/n}μj−1 ＋ {(n − j)/n}μn−j] 　　μn ＝ 1 ＋ (1/n2){Σj＝1 n　 (j − 1)μj−1 ＋ Σj＝1 n　 (n − j)μn−j} 　　μn ＝ 1 ＋ (2/n2)Σj＝1 n−1 jμj となる． （第２段）(1) を帰納法で示す．n = 1 のときはμ1 ＝ 1 だから等号で成り立つ．n ≧ 2 を固定し， 　　μj ≦ 2 ln j ＋ 1　(j ＝ 1, 2, …, n − 1) が成り立つと仮定する．すると， 　　μn ＝ 1 ＋ (2/n2)Σj＝1 n−1 jμj 　　μn ≦ 1 ＋ (2/n2)Σj＝1 n−1 j(2 ln j ＋ 1) 　　μn ＝ 1 ＋ (4/n2)Σj＝1 n−1 j ln j ＋ (2/n2)Σj＝1 n−1 j となり，ここで 　　(2/n2)Σj＝1 n−1 j ＝ (2/n2){n(n − 1)/2} ≦ 1 なので， 　　μn ≦ (4/n2)Σj＝1 n−1 j ln j ＋ 2 となり，y ＝ x ln x のグラフを考えると， 　　μn ≦ (4/n2)∫2 n x ln x dx ＋ 2 　　μn ＝ (4/n2)(1/4)[x2(2 ln x − 1)]2 n ＋ 2 　　μn ＝ (1/n2){n2(2 ln n − 1) − 4(2 ln 2 − 1)} ＋ 2 　　μn ＝ 2 ln n − 1 − (4/n2)(2 ln 2 − 1) ＋ 2 となり，2 ln 2 − 1 ＝ 0.386… ＞ 0 なので， 　　μn ≦ 2 ln n ＋ 1 が得られる．よって，(1) は示された． （第３段）(2) については，定数項は n ＝ 1 のときを考えれば得られる．係数については (3) が得られればよい．よって，後は (3) を示せばよい． （第４段）0 ＜ a ＜ 2 を任意に固定する．このとき，c ＞ 0 を十分大きくとると，すべての n に対して， 　　μn ≧ a ln n − c　　(＊) が成り立つことを示そう．a は固定したままで，まず，N を十分大きくとると，すべての n ≧ N に対して 　　a (−2/n ＋ 1/n2) ln(n − 1) ＋ (1 − a/2)/2 ≧ 0　　(＊＊) 　　a ln(1 − 1/n) ＋ (1 − a/2)/2 ≧ 0　　(＊＊＊) が成り立つことが，n についての極限を考えれば分かる．この N を固定する．c ＞ 0 を十分大きくとると，n = 1, 2, …, N に対して (＊) が成り立つ．後は，n ≧ N を固定して， 　　μj ≧ a ln j − c　(j ＝ 1, 2, …, n − 1)　 が成り立つことを仮定し，今固定した n に対して (＊) が成り立つことを示せばよい． 　　μn ＝ 1 ＋ (2/n2)Σj＝1 n−1 jμj［第１段より］ 　　μn ≧ 1 ＋ (2/n2)Σj＝1 n−1 j(a ln j − c)［帰納法の仮定より］ 　　μn ≧ 1 ＋ (2a/n2)∫1−0 n−1 x ln x dx − c［第１段と同様，但し積分範囲をずらして下から評価］ 　　μn ＝ (a/2n2)[x2(2 ln x − 1)]1−0 n−1 ＋ 1 − c 　　μn ＝ (a/2n2)[(n − 1)2{2 ln(n − 1) − 1} ＋ 1] ＋ 1 − c 　　μn ＝ a (1 − 1/n)2 ln(n − 1) − (a/2)(1 − 1/n)2 ＋ (a/2n2) ＋ 1 − c 　　μn ≧ a (1 − 1/n)2 ln(n − 1) − a/2 ＋ 0 ＋ 1 − c 　　μn ＝ a (1 − 1/n)2 ln(n − 1) ＋ (1 − a/2) − c 　　μn ≧ a ln(n − 1) ＋ (1 − a/2)/2 − c［(＊＊) より］ 　　μn ≧ a ln n − c［(＊＊＊) より］ なので示された． （第５段）第４段と (1) により 　　a ln n − c ≦ μn ≦ 2 ln n ＋ 1 なので，辺々を ln n で割り， 　　a − c / ln n ≦ μn / ln n ≦ 2 ＋ 1 / ln n となるので，n について極限をとり， 　　a ≦ liminf (μn / ln n) ≦ limsup (μn / ln n) ≦ 2 となる．これが任意の 0 ＜ a ＜ 2 に対して成り立つので， 　　2 ≦ liminf (μn / ln n) ≦ limsup (μn / ln n) ≦ 2 となる．よって， 　　lim (μn / ln n) ＝ 2 従って， 　　lim (μn / 2 ln n) ＝ 1 となり，(3) は示された．　□

トップページへ