計算複雑度

計算機の能力が向上することにより現実的な時間で解けるようになった問題は多いが，計算能力の向上だけでは対処できない問題も存在する．こうした問題では計算対象の大きさが少し増えるだけで計算の手間が大きく増大し，これはその問題が本質的に難しいことを意味している．この計算時間に関する問題の難しさを計る指標が計算複雑度である．計算対象の大きさを変数として，その大きさに対して線形（一次式），多項式，指数関数というように表現する．同様に，計算に必要とされる空間量の指標を空間複雑度という．