計算量

アルゴリズムが処理に要する時間や記憶領域が、入力データの量nに応じてどう増えるかを表す尺度。定数倍などを無視した増え方をO(n)やO(n log n)のようなオーダ記法で示す。処理時間を表す時間計算量と、必要な記憶量を表す領域計算量がある。

アルゴリズムが処理に要する時間（時間計算量）や記憶領域（領域計算量）が、入力の大きさnに対してどう増えるかを表したもの。定数倍や低い次数の項を省いて増え方だけを示すオーダ記法（O記法）で表し、O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2ⁿ)の順に増え方が大きい。データ量が増えたときの処理時間の見積もりや、アルゴリズムの選択に使う。

アルゴリズムの実行に必要な手間を、入力データの大きさnに対する増え方で表したもの。処理時間を表す時間計算量と、必要な記憶領域を表す領域計算量があり、O(n)、O(n log n)、O(n²)のように最も影響の大きい項だけを残したオーダ記法で表す。

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

有限個の状態と状態遷移規則からなる計算モデル。決定性（DFA）と非決定性（NFA）があり、正規言語を認識する能力を持つ。状態遷移図や状態遷移表で表現され、字句解析やパターンマッチングに応用される。

有限オートマトンにスタック（プッシュダウンスタック）を追加した計算モデル。文脈自由言語を認識する能力を持ち、プログラミング言語の構文解析（括弧の対応や再帰構造の処理）に対応する。

任意のプログラムと入力に対して、そのプログラムが有限時間内に停止するかどうかを判定するアルゴリズムは存在しないことを証明した問題。チューリングによる証明は計算可能性理論の基礎であり、決定不能問題の代表例。

NPクラスに属し、かつNPクラスの全問題から多項式時間で帰着可能な問題の総称。効率的な（多項式時間の）解法が見つかっておらず、一つでも多項式時間で解ければP=NPが証明される。巡回セールスマン問題やナップサック問題が代表例。

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