探索アルゴリズム再考¶

探索アルゴリズム（searching algorithm）は、データ構造（配列、連結リスト、木、グラフなど）の中から、特定の条件を満たす 1 つまたは複数の要素を探索するために用いられます。

探索アルゴリズムは、実装の考え方に応じて次の 2 種類に分けられます。

これらのトピックはすでに前の章で扱っているため、探索アルゴリズムは私たちにとって見慣れたものです。本節では、より体系的な視点から探索アルゴリズムをあらためて見直します。

総当たり探索¶

総当たり探索は、データ構造の各要素を順に調べて目標要素を特定します。

“線形探索”は配列や連結リストなどの線形データ構造に適しています。データ構造の一端から始めて、要素を 1 つずつ調べ、目標要素が見つかるか、もう一方の端に達しても見つからないまで続けます。
“幅優先探索”と“深さ優先探索”は、グラフと木における 2 つの走査戦略です。幅優先探索は初期ノードから始めて層ごとに探索し、近いところから遠いところへ各ノードを訪れます。深さ優先探索は初期ノードから始めて 1 本の経路を最後までたどり、その後でバックトラックしてほかの経路を試し、データ構造全体を走査し終えるまで続けます。

総当たり探索の利点は、単純で汎用性が高く、**データの前処理や追加のデータ構造を必要としない**ことです。

しかし、この種のアルゴリズムの時間計算量は \(O(n)\) です。ここで \(n\) は要素数であり、そのためデータ量が大きい場合は性能が低くなります。

適応的な探索は、データが持つ固有の性質（整列性など）を利用して探索過程を最適化し、目標要素をより効率よく特定します。

この種のアルゴリズムの利点は効率が高く、**時間計算量が \(O(\log n)\) あるいは \(O(1)\) に達する**ことです。

しかし、これらのアルゴリズムを使うには、たいていデータの前処理が必要です。たとえば、二分探索では事前に配列をソートする必要があり、ハッシュ探索と木探索では追加のデータ構造が必要です。これらのデータ構造を維持するにも、追加の時間と空間のコストがかかります。

Tip

適応的な探索アルゴリズムは、しばしば検索アルゴリズムとも呼ばれ、主に特定のデータ構造の中で目標要素を高速に取得するために用いられます。

大きさ \(n\) のデータ集合が与えられたとき、線形探索、二分探索、木探索、ハッシュ探索など、さまざまな方法で目標要素を探索できます。各手法の動作原理を下図に示します。

上記のいくつかの手法について、操作効率と特性を次の表に示します。

表探索アルゴリズムの効率比較

	線形探索	二分探索	木探索	ハッシュ探索
要素探索	\(O(n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)
要素挿入	\(O(1)\)	\(O(n)\)	\(O(\log n)\)	\(O(1)\)
要素削除	\(O(n)\)	\(O(n)\)	\(O(\log n)\)	\(O(1)\)
追加領域	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)
データ前処理	/	ソート \(O(n \log n)\)	木構築 \(O(n \log n)\)	ハッシュ表構築 \(O(n)\)
データの順序性	なし	あり	あり	なし

探索アルゴリズムの選択は、規模、探索性能の要求、データの問い合わせ頻度や更新頻度などにも左右されます。

線形探索

汎用性が高く、データの前処理をまったく必要としません。データを 1 回だけ問い合わせればよい場合、ほか 3 つの手法では前処理にかかる時間のほうが、線形探索そのものより長くなることがあります。
規模の小さいデータに適しています。この場合、時間計算量が効率に与える影響は比較的小さいです。
データ更新頻度が高い場面に適しています。この手法では、データに対する追加の保守が不要だからです。

二分探索

ハッシュ探索

木探索