問題の計算の難しさやアルゴリズムの作業量を、アルゴリズムが入力から解を導き出すのに必要とする 時間や記憶領域の量で評価したもの。

時間として総命令ステップ数を、記憶領域としてアクセスしたメモリのアドレスの最大幅（最高位－最低位）を評価に使い、また一般に大きな入力ほど計算は難しくなるので入力のサイズ（長さ、大きさ）に関して評価する。

比較や議論を簡単にするため、一般にオーダー O( ) 表記を使って定数や低次の項を省略する。

計算複雑性（computational complexity）

ランダウの漸近記法（asymptotic notation）、O記法

対数（logarithm）

計算量クラス、複雑性クラス（Complexity class、computational complexity class）

時間計算量（time complexity）

空間計算量（space complexity）

平均計算量（average-case complexity）

最大計算量、最悪計算量（worst-case complexity）

整列、ソート（sort）