10.6 まとめ
1. 要点の振り返り
- 二分探索はデータの順序性に依存し、ループによって探索区間を半分ずつ縮小しながら探索を行う。入力データがソート済みであることを前提とし、配列または配列ベースで実装されたデータ構造にのみ適用できる。
- 総当たり探索はデータ構造を走査してデータを特定する。線形探索は配列と連結リストに適しており、幅優先探索と深さ優先探索はグラフと木に適している。この種のアルゴリズムは汎用性が高く、データの前処理を必要としないが、時間計算量 \(O(n)\) は高い。
- ハッシュ探索、木探索、二分探索は高効率な探索手法であり、特定のデータ構造内で目的の要素を高速に特定できる。この種のアルゴリズムは効率が高く、時間計算量は \(O(\log n)\) あるいは \(O(1)\) に達するが、通常は追加のデータ構造を必要とする。
- 実際には、データ規模、探索性能の要件、データの問い合わせ頻度や更新頻度などの要因を具体的に分析し、そのうえで適切な探索手法を選択する必要がある。
- 線形探索は小規模または頻繁に更新されるデータに適している。二分探索は大規模でソート済みのデータに適している。ハッシュ探索は問い合わせ効率への要求が高く、範囲検索を必要としないデータに適している。木探索は順序の維持と範囲検索のサポートが必要な大規模動的データに適している。
- ハッシュ探索で線形探索を置き換えることは、実行時間を最適化するための一般的な戦略であり、時間計算量を \(O(n)\) から \(O(1)\) へと下げられる。