コンピュータ上で、
データの格納先を探す方法はいくつかあります。
・線形探索法(逐次探索法)
・2分探索法
・ハッシュ探索法
◆線形探索法(逐次探索法)
先頭から順にデータを探していきます。
「何回目でデータは探せるか?」
⇒「平均でデータの数の半分の回数」です。
1番目から11番目までのデータがあれば、
「平均で6回目」です。
↓
●線形探索法(逐次探索法)
最少探索回数:1回
最大探索回数:N回
平均探索回数:(N+1)÷2回
※「N」というのはデータの数です。
※平均を計算するときに端数が生じることもあり
ますが、あくまでも平均のお話です。
●番兵法
線形探索法では「番兵法」と呼ばれる探索法があります。
単純に、データの最後に「番兵」を追加します。
※「番兵」とは、見張り番の兵士のことです。
「番兵」は探したいデータとイコールにしておきます。
つまり、「リンゴ」というデータを探したいときに、
最後のデータのさらに後ろに、「リンゴ」と番兵を置いておきます。
もし、最後の最後に検索したい値がヒットしたら、
それは番兵になります。
つまり、検索したい値は「無かった」と判断できます。
同じ「線形探索法」でも、
「番兵法」があるバージョンと、
「番兵法」がないバージョンがある
と理解してください。
具体的には、
番兵法を使うとアルゴリズムに、
「最後のデータまで検索したか?」
という質問を毎回しなくて済みます。
◆2分探索法
半分ずつ切り分けて検索していきます。
探したいデータが「1」~「100」のうち、
「20」だとします。
まず、「1+100÷2」をして、
真ん中の「50」(正確には50.5ですが)と
まず比較します。
「20」は「50」より値が小さいですから、
次は、その中央値を除いた「1~49」に
限定して調べます。2回目も中央値であ
る「1+49÷2=25」と比較します。
効率がいいですね。
※端数は除いてお考えください。
・端数を中央値ととる場合
・端数をカットする方法、
・あらかじめデータの母数に奇数なら「+1」をする・・
などといったやり方があります。
●2分探索法
平均探索回数:log2 N回
最大探索回数:log2(N+1)回
計算量:O(log2N)
※「log」という難しい言葉がでました。
数学用語ですが、
例えば、「log2 8」は3です。
↓
「2」を3乗すると、「8」になります。
つまり、8個のデータからある値を探す
ときの平均探索回数は3回ということです。
2等分しながら探索していく訳ですから、
逆に、探索回数が1回増える度に、その2倍を
検索できることになります。
※8個のデータを、平均3回で検索できるとしたら、
16個のデータから検索するには、
平均4回の検索回数です。
◆ハッシュ探索法
あらかじめデータの格納場所を
ある計算式の答えにしておきます。
例えば、データ「99」の格納場所(アドレス)は、
「13」だったとします。
↓
データ「99」を探そうと思ったときに、
「データの値÷5の余り+2」をします。
(答え:6)
この「÷5の余り+2」が”ある計算式”です。
計算はもっと複雑ですから、
一発でデータが格納されているアドレスに
辿り着くことができます。
ということで・・・
探索回数:1回
探索量:0(1)
です。
たまたま、計算結果が同じになることが
あります。
「99÷5の余り+2」と、
「104÷5の余り+2」の答えは
一緒ですよね。
この現象を「シノニム」といいます。
シノニムが発生した際は、
どちらかのアドレスを変更しなくてはいけません。。
どう変更するかは出題されませんのでご安心を!