計算量とは?

アルゴリズムとは, 問題を解くための計算の手続きのことです. 同じ問題を解くにも様々なアルゴリズムが考えられますが, その中で最も効率的なものが望ましいです. そこでアルゴリズムの効率性を定量的に測る尺度として計算量 (computational complexity) が定義されます. 計算量にも様々なものがあり, 例えば時間計算量や空間計算量などがあります.

• 時間計算量 (time complexity) : サイズ$n$の任意の入力に対し, 計算が終わるまでにかかるステップ数.
• 空間計算量 (space complexity) : サイズ$n$の任意の入力に対し, 計算が終わるまでに使用したメモリのサイズ

考える問題によって入力のサイズは変わってきます. 例えば文字列を扱う問題は与えられる文字列の長さを$n$とすることが多く, 行列を扱う問題は, 例えば$n\times n$ 行列を扱うときは入力長は $n^2$ だが入力のサイズを$n$と定義するもある.

本講義では特に断りのない限り, 計算量と言えば時間計算量を指すものとし, 基本的な演算(加算や掛け算など)の回数によって測ります.

例: 1からnまでの総和を求める関数sum_to_n()

def sum_to_n(n):
	S=0
	for i in range(1,n+1):
		S=S+i
	return S

この関数はS=0とS=S+iのそれぞれで変数Sの値を更新しています. 計算回数はS=0の箇所では1回, S=S+iは$n$回実行されるので, この関数の計算量は$n+1$となります.

例2. 1からnまでの総和を求める別の関数sum_to_n()

def sum_to_n(n):
	return n*(n+1)//2

この関数は等差数列の和の公式を使って1からnまでの和を計算する関数になっています. n*(n+1)//2では, まず最初に $n\cdot (n-1)$ を計算し, その次に2で割っているので, 計算回数は2となります. 例1と同じ値を計算していますが, $n$ が大きくなった時はこちらの方が計算回数が少ないので高速です. つまり, 例2のアルゴリズムの方が効率的であるとみなします.

実際のプログラムの実行時間は同じアルゴリズムであっても実装したときのプログラミング言語や実行環境によって変動しうるので, 「アルゴリズムの効率性」を議論する場合はこれらの要因を排除して行うのが基本です. 例えば実行環境によっては同じアルゴリズムを２回走らせるということもあるかもしれません. 従って, 計算量の議論をする際は定数倍を無視するという慣習があります. 詳しくはオーダー記法を参照してください.