二分探索法の平均探索回数について
佐藤道一
| これは，2004年12月10日の書き下ろしです． 関連ページ 二分探索木による探索の平均探索回数について クイックソートでの平均比較回数について 二分探索法で，n 件のデータから探索する場合， 最大探索回数：[log2n]＋1 平均探索回数：[log2n] （ここで [x] は x を超えない最大の整数）であるといったことが，情報処理技術者試験の参考書（但し，第三者が出しているものであって公式参考書はそもそも存在しない）にしばしば書いてある．しかし，この平均探索回数は近似に過ぎない．一般の固定した n に対する厳密な公式を書いてあるものが見当たらないので，以下で明らかにする．なお特別な n に対する厳密な公式の書いてある英語の文献は見つかったので末尾で述べる． k ＝ [log2n]＋1（最大探索回数）とおく．すなわち，k を 2k−1 ≦ n ≦ 2k −1 を満たす整数とすると， １回目に見つかる確率は 1/n ２回目に見つかる確率は 2/n ３回目に見つかる確率は 4/n ： ： j 回目に見つかる確率は 2j−1/n (j＝1, 2, …, k−1) ： ： k 回目に見つかる確率は 1−(1＋2＋…＋2k−2)/n ＝ 1−(2k−1−1)/n となるので，期待値μn は μn ＝ (Σ となる．ここで，総和部分をSkとおくと， 1Sk ＝ 1 ＋ 2・2 ＋ 4・3 ＋…＋ 2k−2(k−1) 2Sk ＝ 0 ＋ 2・1 ＋ 4・2 ＋…＋ 2k−2(k−2) ＋ 2k−1(k−1) となるので，上式から下式を引いて −Sk ＝ 1＋2＋4＋…＋2k−2 − 2k−1(k−1) −Sk ＝ 2k−1−1 −2k−1(k−1) ＋Sk ＝ 2k−1(k−2) ＋ 1 となる．よって μn ＝ {2k−1(k−2) ＋ 1}/n ＋ {1−(2k−1−1)/n}k μn ＝ k ＋ (−2k＋k＋1)/n となる．ここで 2k−1 ≦ n ≦ 2k −1 なので k − 2 ＋ (k＋1)/2k−1 ≦ μn ≦ k − 1 ＋ k/(2k−1) となり，近似式μn ≒ k − 1 の誤差の絶対値は１以下であることが分かる． 特に n ＝ 2k −1 の場合は μn ＝ k − 1 ＋ k/n となり，このことはこちら（英語の文献）に書かれている．但しそこにある log(n)は正しくは log(n＋1)である． |