時間計算量と空間計算量
定義
与えられた問題を解く時の時間を時間複雑度time Complexity、メモリの要求を空間複雑度space Complexityと言う。
例
漸近記法はこれらを表現するのに非常に便利な手段になる。時間複雑度の例を見てみよう。
定数時間 $O(1)$
$n$ にかかわらず終わることができるアルゴリズムで、実質的に時間がかからないことだ。例えば、$\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ の三番目の要素を見つけるアルゴリズムは、$\mathbf{x}$ がどうなっているかに関心がなく、ただ $8$ を返せばいい。
線形時間 $O(n)$
$n$ に比例する時間がかかる。例えば、$\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ の最大値を見つけるアルゴリズムは、$8$ で見つけられるが、それが本当に最大値であることを保証するためには、他の要素もすべてチェックしなければならない。表現がこんな感じだと少し悪い気がするが、実際、線形時間くらいであればかなり速いアルゴリズムだと言われている。
二次時間 $O(n^2)$
$n^2$ に比例する時間がかかる。例えば、$\mathbf{x} = [4,3,8,-1,-9,0,5,7,2,6]$ を大きさ順に並べ替える場合は、最大値を一度見つけて最後に置き、その最大値を抜いた配列でまた最大値を見つけることを繰り返せばいい。最大値を見つけるたびに $n, n-1, \cdots , 1$ 時間がかかるので、その合計は 等差数列の和の公式により $\displaystyle \sum_{k=1}^{n} k = {{ n (n+1)} \over {2}} = O(n^2)$ になる。もっと賢い方法があると思うかもしれないが、これより愚かな方法は考える必要がない。
三次時間 $O(n^3)$
$n^3$ に比例する時間がかかる。例えば、$n=2^{k}$ 時に $n \times n$ 行列の乗算を考えてみると、$A, B \in \mathbb{R}^{n \times n}$ を掛けた$C = AB$ を計算することになるが、次の8つの ${{n} \over {2}} \times {{n} \over {2}}$ 行列の積を計算して解決できる。 $$ AB= \begin{bmatrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{bmatrix} \begin{bmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} \\ C_{3} & C_{4} \end{bmatrix} = C $$
$$ C_{1} = A_{1}B_{1} + A_{2} B_{3} $$
$$ C_{2} = A_{1}B_{2} + A_{2} B_{4} $$
$$ C_{3} = A_{3}B_{1} + A_{4} B_{3} $$
$$ C_{4} = A_{3}B_{2} + A_{4} B_{4} $$ この計算を続けていくわけだが、一回の計算にかかる時間が $T(n)$ で、繰り返し外の実行時間を $c$ とすると $\displaystyle T(n) = 8 T \left( {{n} \over {2}} \right) + c$ だからだ。 $$ \begin{align*} T(n) =& 8 T \left( {{n} \over {2}} \right) + c \\ =& 8 \left[ 8 T \left( {{n} \over {4}} \right) + c \right] + c \\ =& 8 \left[ 64 T \left( {{n} \over {8}} \right) + 8 c + c \right] + c \\ =& 8^3 T \left( {{n} \over {8}} \right) + (1+8+8^2)c \\ =& 8^3 T \left( {{n} \over {8}} \right) + {{8^3 - 1} \over {8 - 1}}c \\ & \vdots & \\ \approx& 8^{\log_{2} n} ( T(1) + c ) \\ =& n^{\log_{2} 8} ( T(1) + c ) \\ =& n^{3} ( T(1) + c ) \\ =& \Theta ( n^3 ) \end{align*} $$ 行列の乗算は、数学が入った応用分野でほとんど例外なく、それもかなり多く行う。しかし、$n^3$ は少し大きい。$n=100$ だけになると、なんと $n^3 = 10^6$ になる。ここでさらに計算を減らすことはできるだろうか？もともと不要な計算をしていないので、これ以上どう減らせるかは見当たらない。しかし、シュトラッセンアルゴリズムという驚くべき方法を使えば、これをさらに減らすことができる。これがアルゴリズムの醍醐味だ。
対数時間 $O \left( \log (n) \right)$
非常に速いという意味だ。例えば、ソートされた配列 $\text{sort} (\mathbf{x}) = [-9,-1,0,2,3,4,5,6,7,8]$ で $0$ の位置を見つける問題があるとしよう。直感的に考えられる方法は、真ん中の要素を一つ選んで $0$ より大きいか小さいかを確認し、$0$ より大きければ右側を捨て、小さい場合は左側を捨てて配列を縮めながら探すことだ。これを二分探索binary searchと言う。一回の計算にかかる時間が $T(n)$ で、比較にかかる時間を $c$ とすると、 $$ \begin{align*} T(n) =& T \left( {{n} \over {2}} \right) + c \\ =& \left[ T \left( {{n} \over {4}} \right) + c \right] + c \\ =& T \left( {{n} \over {4}} \right) + 2 c \\ =& T \left( {{n} \over {8}} \right) + 3 c \\ & \vdots & \\ \approx& T \left( 1 \right) + c \log_{2} n \\ =& O \left( \log_{2} (n) \right) \end{align*} $$ それだからだ。対数の底の変換公式によれば $O( \log (n)))$ になってもいいが、元々コンピュータ科学では、特に対数の底に言及がなければ、通常は $e = 2.7182…$ ではなく$2$ だから、表現に気を使う必要はない。
指数時間 $O(2^n)$
非常に長い時間がかかるという意味だ。再帰函数を使ってフィボナッチ数列を計算する場合、非常に非効率的で、一度の計算が $n$ 番目のフィボナッチ数 $a_{n}$ を求めるためにかかる時間が $T(n)$ で、前の二項を足すのにかかる時間を $c$ とすると、黄金比 $\phi = 1.618…$ に対して、 $$ \begin{align*} T(n) =& T(n-1) + T(n-2) + c \\ =& [ T(n-2) + T(n-3) + c ] + T(n-2) + c \\ =& 2 T(n-2) + T(n-3) + (1+1) c \\ =& 3 T(n-3) + 2 T(n-4) + (1+1+2) c \\ =& 5 T(n-4) + 3 T(n-5) + (1+1+2 + 3) c \\ =& 8 T(n-6) + 5 T(n-4) + (1+1+2+3+5) c \\ & \vdots & \\ =& c \sum_{k=1}^{n} a_{n} \\ \approx& {{\phi^{n-1}-1} \over {\phi-1}} c \\ =& \Omega ( \phi^n ) \end{align*} $$ こうなる理由だ。最後の部分は、$\displaystyle \phi \approx {{a_{n}} \over {a_{n-1}}}$ であるため、等比数列の和の公式を使って近似したものだ。こんなアルゴリズムは現実的には使うことができず、動的プログラミングのような解決法を探すか、または、このような時間複雑度を持つことを利用して、暗号に応用することもできる。