計算量

Computational Complexity

けいさんりょう

アルゴリズムの実行に必要な時間や空間の量をオーダー記号O(n)で表現したもの。時間計算量と領域計算量があり、入力サイズnに対する増加傾向でアルゴリズムの効率を評価する。O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(2^n)の順に計算量が大きい。

基礎理論 > 情報に関する理論

関連キーワードの用語

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

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

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

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

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

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