コンピューター上で計算に要する手間を量的に計る尺度を計算の複雑さという。計算の複雑さには2種類ある。プログラムの実行に要する時間計算量と、プログラムの実行時に要する空間計算量（記憶容量）である。アルゴリズムを設計するときには、解くべき問題をなるべく少ない計算量で解くようなものを設計する必要がある。なるべく少ないといっても頑張ればいくらでも減らせるものではなく、問題が与えられれば一般にそれを解くのに最低必要な計算量が理論的に定まる。その計算量は問題の難しさを表す指標として用いることができる。人工知能（AI）の多くの応用は、まともに解こうとすれば入力の数に対して指数関数のオーダーの計算量が必要になるとされている（NP問題）。指数関数のオーダーがかかるときに計算量が爆発すると表現する。現実的に解こうとすれば、計算量が爆発しないように、適切なヒューリスティックスを適用する必要がある。

図「計算量爆発問題」