計算複雑性理論 (Computational Complexity Theory)

計算複雑性理論は、問題を解くために必要な時間・空間などの資源を入力サイズの関数として分類する。P、NP、NP困難などの区分は、アルゴリズム選択や問題の近似可能性を考えるための共通語彙になる。

入力サイズと計算モデルを固定し、最悪計算量・平均的挙動・近似比・メモリ使用量を分けて評価する。多項式時間でも定数やデータ構造が実用性を左右するため、理論結果を実測で補う。

クラス名だけで特定の実装の遅さや速さは決まらない。制約が小さい、入力が偏る、前処理が可能、といった条件で実用解が成立することもある。