アルゴリズム

問題を解決するための手順や計算方法を明確に定義したもの。有限回の操作で必ず終了し、正しい結果を得られることが求められる。

問題を解くための手順を、有限個の明確な操作の組合せとして定めたもの。同じ問題でも手順によって処理時間や必要な記憶領域が異なるため、計算量（オーダー記法）で効率を比べる。整列や探索などの代表的なアルゴリズムがあり、流れ図や擬似言語で表す。なお、アルゴリズム（解法）そのものは著作権法の保護の対象にならない。

整列済みのデータで、探索範囲の中央の値と目的の値を比較し、目的の値がある側の半分に範囲を絞ることを繰り返す探索の方法。1回の比較で範囲が半分になるので、データ数nに対する最大の比較回数は約log₂n回で、計算量はO(log n)である。データが整列している必要があり、追加・削除が多いデータでは整列を保つ費用がかかる。

ピボット要素を選び、それより小さい要素と大きい要素に分割して再帰的に整列するアルゴリズム。平均計算量はO(n log n)だが最悪はO(n^2)。実用的には最速のソートアルゴリズムの一つで、多くの言語の標準ライブラリで採用。

データを半分に分割して再帰的に整列し、整列済みの部分列を統合（マージ）するアルゴリズム。計算量は常にO(n log n)で安定しており、安定ソート（同値要素の順序を保持）。外部ソートにも適用可能だが、O(n)の追加メモリが必要。

ヒープ構造を利用したソートアルゴリズム。データからヒープを構築し、最大（最小）要素を繰り返し取り出して整列する。計算量は常にO(n log n)で追加メモリがO(1)だが、キャッシュ効率がクイックソートより劣る。

キーからハッシュ関数でアドレスを算出し、データを直接参照する探索法。平均O(1)で探索可能だが、衝突（異なるキーが同一アドレスに対応）が発生した場合の処理が性能に影響する。シノニム対策が重要。

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