ハッシュ表探索法

ハッシュ関数を用いてキーからデータの格納位置を直接計算して探索するアルゴリズム。平均計算量はO(1)で非常に高速。衝突が多発すると性能が低下する。

ハッシュ関数を用いてキーから直接データの格納位置を計算し、データにアクセスする探索手法。等値検索がO(1)で非常に高速だが、範囲検索には使用できない。

整列済みデータの中央要素と目標値を比較し、探索範囲を半分に絞り込む操作を繰り返す探索アルゴリズム。計算量はO(log n)。データが整列されている前提が必要で、配列に対して適用される。

データの先頭から順に1つずつ目的の値と比較して探索するアルゴリズム。実装が簡単だが、データ量に比例して探索時間が増加するため、大量のデータには不向きである。

整列済みデータの中央値と目的の値を比較し、探索範囲を半分に絞り込みながら探索するアルゴリズム。データ量が多い場合でも高速に探索できるが、データが事前にソートされている必要がある。

データを先頭から順に目的の値と比較していく探索アルゴリズム。計算量はO(n)。データが整列されていなくても使用できるが、データ数が多い場合は非効率。逐次探索とも呼ばれる。

整列済みデータの中央値と目的の値を比較し、探索範囲を半分に絞り込む操作を繰り返す探索アルゴリズム。計算量はO(log n)で効率的。データが事前に整列されている必要がある。

最適化問題を部分問題に分割し、各部分問題の最適解を記憶して再利用することで全体の最適解を効率的に求める手法。ナップサック問題や最短経路問題などに適用され、メモ化再帰やボトムアップ方式で実装される。