線形探索法

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

データの先頭から順に1つずつ目的の値と比較していく探索の方法で、逐次探索ともいう。データが整列していなくても使え、データ数nに対して平均の比較回数はn/2、計算量はO(n)である。末尾に探す値を置いて終了判定を省く番兵法で処理を速くできる。

データの列を先頭から順に1つずつ調べて、目的のデータを探す方法。データが整列されていなくても使えるが、比較の回数は平均でn/2回、計算量はO(n)で、データが多いと時間がかかる。

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

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

最適化問題を部分問題に分割し、各部分問題の解を記憶しながら全体の最適解を求めるアルゴリズム設計手法。重複する部分問題を再計算せずに済むため効率的。ナップサック問題や最短経路問題に応用される。

直前の2項を足した値が次の項になる数列。1,1,2,3,5,8,13…と続く。再帰処理の例題として頻出で、素直に再帰で書くと同じ計算を何度も繰り返すため、途中結果を保存する動的計画法で高速化できる。

アルゴリズムの実行に必要な計算ステップ数を入力サイズの関数として表したもの。オーダー記法O(n)で表現され、O(1)、O(log n)、O(n)、O(n log n)、O(n²)などがある。アルゴリズムの効率を評価する基本指標。

隣接する要素を比較して交換を繰り返すことでデータを整列するアルゴリズム。平均・最悪計算量ともにO(n²)で効率は良くないが、アルゴリズムが単純で理解しやすい。安定ソート。