探索アルゴリズムの比較

単純前方探索の平均比較回数

単語数の多い英和辞典で、単純前方探索と二分法探索の2つのアルゴリズムで探しました。どちらも意味を調べることができましたが見つけるまでの手間や時間を比較してみます。

yet という単語を探した時、単純前方探索では 1996回比較して見つけました。yet という単語が1996番目に登録されていたからてす。もし、a という単語ならば 1番目に登録されているので、1回の比較で見つかります。

こう考えていくと、単純前方探索で約2000件のデータから探索する場合は、平均で1000回程度の比較で見つけられることになります。

二分法探索の平均比較回数

一方、二分法探索で yet という単語を探した時は、10回程度の比較で見つかりました。

二分法探索の比較回数は最大で全体数を2で割りつづけて、1になる程度と言えます。ちょうど1/2のところにあったという幸運がであればもっと少なくなります。2000ならば大体 1000,500,250,125,64,32,16,8,4,2,1 ですから11回程度で見つかります。

ただし、単純前方探索の比較は等しいかどうかだけですが、二分法探索の比較はどちらが大きいか(ABC順で先か後か)も調べているので単純に回数だけで比べるわけには行きませんが、この比較回数の差は圧倒的に大きなものです。

単純前方探索と二分法探索の平均比較回数の比較

1000と11と横に比べるだけでなく、データの数が多くなったときにどのように比較回数が増えるかが重要です。データ数(ここでは単語数)が2000⇨20000⇨200000と10倍になっていくとき、単純前方探索は比較回数も同様に10倍ずつ増えていきます。二分法探索は2倍にもなりません。データ数が多くなるほど単純前方と二分法の手間の差はますます広がります。

これだけから考えると、二分法探索が優れているようですが、ちょっと待ってください。二分法探索はデータが大きさの順に並んでいる必要があります。並んでいない場合は並べかえる手間も考慮に入れる必要があります。

また、複数のデータが合致する場合には二分法探索では対処が難しくなります。