Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。
WebブラウザにはSafari/Chrome/Firefoxを使って下さい（IEでは表示できないようです。）
計算量の評価
big O 記法
$f(n)$ と $g(n)$ が $\mathbb{R}$ 上の関数であるとき、 \[ f(n)= \mathcal{O}(g(n)) \qquad \text{as $n\rightarrow \infty$} \] であるとは、正の実数 $c_1, c_2$ および $n_0$ が存在して、$n_0\leqq n$ なる $n$ に対して \[ c_1\lvert g(n) \rvert \leqq \lvert f(n) \rvert \leqq c_2\lvert g(n) \rvert \qquad \text{for $n_0\leqq n$} \] であるときをいう。 このとき、$f(n)$ は $g(n)$ のオーダー（order）であるといい、big $\mathcal{O}$ を使って、$f(n)= \mathcal{O}(g(n))$ あるいは $f(n) \sim \mathcal{O}(g(n))$ などと書く。 この 記法は $n$ が十分大きくなったときの関数 $f(n)$ の挙動を表していることに注意する。
$f_1(n)= \mathcal{O}(g_1(n))$ および $f_2(n)= \mathcal{O}(g_2(n))$ が正値関数であるとき、定義から次が成立する。 \begin{align*} & f_1(n)f_2(n)= \mathcal{O}(g_1(n)g_2(n))\\ & f_1(n) + f_2(n)= \mathcal{O}(g_1(n) + g_2(n)). \end{align*}
たとえば、次の多項式 $p(n)$ を考えてみる。 \[ p(n)= a_k n^k + a_{k-1} n^{k-1}+\dots +a_2 n^2 + a_1 n + a_0 \] $n>1$の時には、自明な関係 \[ 1\leqq n\leqq n^2 \leqq \dots \leqq n^{k-1}\leqq n^k \] から直ちに得られる関係 \begin{align*} a_k n^k \leqq p(n) & \leqq a_k n^k + a_{k-1} n^k + \dots + a_2 n^k + a_1 n^k + a_0 n^k\\ & \leqq n^k (a_k + a_{k-1} + \dots + a_1 + a_0) \end{align*} は、$p(n)=\mathcal{O}(n^k)$ であることを示している。
これより、多項式については $n$ の最大次数に着目して \begin{align*} p_0(n) & 5000000000=\mathcal{O}(1) p_1(n) &= 20000 n + 3000000=\mathcal{O}(n)\\ p_2(n) &= 0.000001 n^2 -31412 n - 2600 = \mathcal{O}(n^2)\\ p_3(n) &= 300 n^2 + 600 n + 2500 = \mathcal{O}(n^2) \end{align*} となり、$p_2(n)$ と $p_3(n)$ は同じ $n^2$ のオーダーで $n$ が十分に大きくなると同じ程度に増加し、$n$のオーダーの $p_1(n)$ を圧倒し、$p_1(n)$ は $p_0(n)$ を圧倒することがわかる（この場合、関数の$\log$-$\log$グラフを書いてみるとこの事実は分かりやすい）。
アルゴリズムの計算量オーダーを低くすることは、大きなデータサイス $n$ に対しては劇的な効果があることになる。 あるいは、指数的オーダーを持つ計算量アルゴリムは大きなデータサイス $n$ に対して手に負えない（intractable）ことになる。
| order | 名前 |
|---|---|
| $\mathcal{O}(1)$ | 定数 |
| $\mathcal{O}(\log n)$ | 対数的 |
| $\mathcal{O}(n)$ | 線形的 |
| $\mathcal{O}(n\log n)$ | 対数線形的 |
| $\mathcal{O}(n^2)$ | 2乗的 |
| $\mathcal{O}(n^3)$ | 3乗的 |
| $\mathcal{O}(2^n)$ | 指数的 |
| $\mathcal{O}(n!)$ | 階乗的 |
階乗的オーダーが指数的オーダーよりも大きいのは Stirling's の近似公式からわかる。 \[ n! \sim \sqrt{2\pi n} n^n \mathrm{e}^{-n} \] 比 $n! /2^n$ の対数をとると \[ \log \left(\frac{n!}{2^n} \right) \sim \left( n+\frac12\right) n -(1+\log 2)n +\text{定数} \] から、$n\rightarrow \infty$につれて比はいくらでも大きくなるからである。
代表的なアルゴリズムの計算量
ベクトルの内積
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# inner product of two vectors given by numeric lists
import random
import time
def innner_product(v, w):
n = len(v)
ip = 0
for i in range(size):
ip += v[i] * w[i]
return ip
n = int(raw_input("Length of each random vectors: "))
# preparing two random vectors which element is in [0,1)
v = [random.random() for i in range(n)]
w = [random.random() for i in range(n)]
start = time.time()
result = innner_product(v, w)
end = time.time()
print "used time: ", end - start
print "innver product = ", result
問題のサイズはベクトルの長さ n = len(v) である。
時間計算量を見積もろう。 9行目でベクトルの長さを知る時間 $T_{09}$、変数 ip をゼロにセットするための時間 $T_{10}$とで、$T_{09}+T_{10}$ 時間。
11行目のfor文では、カウンタ変数 i を1つずつ増分し手、最後に i の添字範囲をチェックする時間として (n + 1)$T_{11}$ 時間。 11行で、掛け算と足し算の時間 $T_{12}$ を n回する n$T_{12}$時間。 したがって、合計の計算時間 \[ T_{total} = T_{09} + T_{10} + (n + 1) T_{11} + nT_{12}=n(T_{11}+T_{12}) + T_{09}+T_{10}+T_{11} \] よって、$n$ が十分大きいと $T_{total}\approx n(T_{11}+T_{12})=\mathcal{O}(n)$ である。
一方、計算に要するメモリ使用量は、変数 n, i と ip にスカラー値格納のために $M_s$ + å$M_s$ + $M_s$、ベクトル v と w にn 個のスカラー値を格納するために n$M_s$ + n$M_s$、したがって合計 \[ M_{total}= nM_s + n M_s + M_s + M_s=(2n+2)M_s \] よって、$n$ が十分大きいと $M_{total}\approx 2nM_s=\mathcal{O}(n)$ である。
行列とベクトルの積
$m$ 行 $n$ 列の $m\times n$ 行列 $M$ と $n$次元ベクトル $v$ の積 $Mv$ は $m$ 次元ベクトルを返す。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# product of (m x n) matrix by n-vectors
import random
import time
def mat_vec_product(M, v):
row = len(M)
col = len(M[0])
w = [0 for i in range(row)]
for i in range(row):
sum = 0
for k in range(col):
sum += M[i][k] * v[k]
w[i] = sum
return w
row = int(raw_input("Row size of random Matrix: "))
col = int(raw_input("Column size of random Matrix: "))
# preparing a random matrix and a random vectors with integer elements
M = [[random.randint(0, 3 * row) for i in range(col)] for k in range(row)]
v = [random.randint(0, 5 * col) for i in range(col)]
print M
print v
start = time.time()
result = mat_vec_product(M, v)
end = time.time()
print "used time: ", end - start
print "innver product = ", result
問題のサイズを決めるパラメータは行列の行数 m と 列数 n である。
行列の行数 m の取得（9行目）に$T_{09}$時間、列数 n の取得（10行目）に$T_{10}$時間、 m 次元空ベクトルの生成（11行目）に m に比例した m$T_{11} 時間かかる。
12行目の for文では、カウンタ変数 i の添字範囲のチェックを入れて (m+1)$T_{12}$時間、 13行目と16行目で m$T_{13}$ + m$T_{16}$ 時間。 14行目のfor文では、外側のfor文の各 i について (n + 1) $T_{14}$ 時間かかり、その内側(15行目)で n 回の繰り返す n$T_{15}$時間を、外側のfor文で m 回繰り返す。 したがって、合計時間は \begin{align*} T_{total} &=\big(T_{09}+T_{10}+ mT_{11}\big)+\big((m+1)T_{12} +mT_{13}+mT_{16}\big) +m\big((n+1)T_{14}+ nT_{15}\big)\\ &= mn(T_{14}+T_{15}) + m(T_{11}+T_{12}+T_{13}+T_{16}+T_{14}+T_{15}) +T_{09}+T_{10}+T_{12} \end{align*} したがって、$T_{total}\approx mn(T_{14}+T_{15})=\mathcal{O}(mn)$ となる。 正方行列の場合には $T_{total}=\mathcal{O}(n^2)$ である。
メモリ使用量は、スカラー値を格納する$M_s$ が行列で mn$M_s$、掛けるベクトルにn$M_s$、仮ベクトルに m$M_s$、i, sum, k に 3$M_s$、よって \[ M_{total}=mn M_s+ nM_s + mM_s + 3M_s=(mn+n+m+3)M_s. \] したがって、$M_{total}\approx mnM_s=\mathcal{O}(mn)$ となる。 正方行列の場合には $M_{total}=\mathcal{O}(n^2)$ である。
行列と行列の積
$m \times r$ 行列 $A$と $r\times n$ 行列 $B$ の行列積 $C=AB$ は $m\times n$ 行列で次のように計算される。 \[ C_{ij}=\sum_{k=1}^r A_{ik} B_{kj},\qquad 1\leqq i \leqq n, 1\leqq j\leqq m \]
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# product of (m x k) matrix by (k x n)-matrix
import random
import time
def mat_mat_malti(A, B):
row = len(A)
rect = len(A[0])
col = len(B[0])
C = [[0 for i in range(col)] for j in range(row)]
for i in range(row):
for j in range(col):
sum = 0
for k in range(rect):
sum += A[i][k] * B[k][j]
C[i][j] = sum
return C
row = int(raw_input("Row size of random Matrix A: "))
rect = int(raw_input("Column size of random Matrix A: "))
col = int(raw_input("Column size of random Matrix B: "))
# preparing a random matrices with integer elements
A = [[random.randint(0, 2 * row) for i in range(rect)] for k in range(row)]
B = [[random.randint(0, 3 * rect) for i in range(col)] for k in range(rect)]
print A
print B
start = time.time()
result = mat_mat_malti(A, B)
end = time.time()
print "used time: ", end - start
print "Matrix Matrix Multiplication = ", result
ベクトルの1-ノルム
$n$個の成分を持つベクトル $v=(v_0, v_1, \dots, v_{n-1})$の$L_1$ノルム $\Vert v\Vert_1$ は次のようである。
\[ \lVert v\rVert_1 =|v_0| + |v_1| +\dots + |v_{n-1}|. \]
以下は、再帰再訪--計算時間の「ベクトルの$L1$ノルム」のスクリプトを含んでいる。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# L1 norm of vector(list)
import math
import random
import time
def one_norm_recur(num_list):
if len(num_list) == 1:
onenorm = math.fabs(num_list[0])
else:
left_norm = one_norm_recur(num_list[: int(math.floor(len(num_list) / 2))])
right_norm = one_norm_recur(num_list[int(math.floor(len(num_list) / 2)): ])
onenorm left_norm + right_norm
return onenorm
def one_norm_for(num_list):
onenorm = 0
for elemnt in num_list:
onenorm += element
return onenorm
n = int(raw_input("Length of random vector: "))
nlist = [random.random() for k in range(i)]
start_for = time.time()
result_for = one_norm_for(num_list)
end_for = time.time()
used_for = end_for - start_for
start_recur = time.time()
result_recur = one_norm_recur(num_list)
end_recur = time.time()
used_recur = end_recur - start_recur
print "1-norm = ", result_for
print "used time:"
print "\tby for", used_for
print "\tby recursion", used_recur
$L_1$ノルムの問題サイズはベクトルの長さ $n$ である。
$L_1$ノルム計算の再帰版 one_norm_recur の時間計算量を評価する。 簡単のためにベクトルの長さ $n$ を $n=2^k$ と仮定しても一般性を失わない（$k=\log n$）。 10行目の判断で時間 $T_{10}$と15行目の足し算計算に時間 $T_{14}$を費やすのであるが、13行目と14行目で半分の長さの$L_1$ノルム計算をしていることを考慮すると \[ T_{total}(2^k) = T_{10} + T_{14} + 2T_{total}(2^{k-1}) \] の関係、つまり $c= T_{10} + T_{14}$ を定数とすると \[ T_{total}(n)= c + 2T_{total}(n/2) \] が成立する。 このことから、次のように書くことができる。 \begin{align*} T_{total}(n) &= c + 2T_{total}(n/2)\\ &= c + 2(c + 2 T_{total}(n/2^2))= c + 2c + 2^2 T_{total}(n/2^2)\\ &= c + 2c + 2^2(c + 2T_{total}(n/2^3))=c + 2c + 2^2c + 2^3T_{total}(n/2^3)\\ & \vdots\\ &= c + 2c + 2^2 c+ 2^3 c+ \dots + 2^{k-2}c + 2^{k-1}T_{total}(2)\\ &= c\sum_{i=0}^{k-1} 2^i + n(T_{10} + T_{14})\\ &= \frac{1-2^k}{1-2}c + dn \qquad d = T_{10} + T_{14}\\ &=(c+d)n -c=\mathcal{O}(n) \end{align*}
メモリ計算量を考えよう。 $L_1$ノルムを計算するために長さ $n$ のベクトルを保持するための入力メモリ量 $M_{input}(n)$ とは区別して、関数内で再帰呼び出しするために必要なメモリを考える必要がある。 サイズ $n$ の計算に再帰呼び出しで必要なメモリ$M_{recur}(n)$は \[ M_{recur}(n) = c + M_{recur}(n/2) \] である。$c$ には left_norm や right_norm （など）に必要な固定領域である。 この漸化式は上の時間計算量と同様に評価でき、$M_{recur}(n)=\mathcal{O}(n)$ である。
入力メモリ量 $M_{input}(n)$ は明らかに $=\mathcal{O}(n)$ であることから、関数 one_norm_recur のメモリ計算量 $M_{total}(n)$ は次のようになる。 \[ M_{total}(n) = M_{input}(n) + M_{recur}(n) = \mathcal{O}(n) + \mathcal{O}(n) = \mathcal{O}(n). \]
先の関数 one_norm_recur は、リスト分割して再帰呼び出ししている様子の1行の表現が長くなって見づらい。 そこで次のように、リストを左右に分割してそれぞれを left_list と right_list に代入してコードを分かりやすくした関数を one_norm_recur2 としてみた。 しかしながら、以下の計算から明らかになるように、オーダーが上がったメモリ計算量を必要とするようになる。結果、$n$が大きくなると無視できない影響を及ぼしてしまう。
def one_norm_recur2(num_list):
if len(num_list) == 1:
onenorm = math.fabs(num_list[0])
else:
left_list = num_list[: int(math.floor(len(num_list) / 2))]
right_list = num_list[int(math.floor(len(num_list) / 2)): ]
left_norm = one_norm_recur(left_list)
right_norm = one_norm_recur(right_list)
onenorm left_norm + right_norm
return onenorm
この場合、5行目と6行目のリスト（長さは約半分の $n/2$） left_list と right_list のために必要なメモリが発生するため $M_{recur}(n)$ は次のようになる。 \[ M_{recur}(n) = c + d n + 2M_{recur}(n/2) \]
したがって、 \begin{align*} M_{recur}(n) &= c + dn+ 2M_{recur}(n/2)\\ &= c + dn + 2(c + dn/2 + 2M_{recur}(n/2^2))= c + 2c + 2dn + 2^2M_{recur}(n/2^2)\\ & \vdots\\ &= c + 2c + 2^2 c+ 2^3 c+ \dots + \frac{n}{2}c + dkn + nM_{recur}(1)\\ &= c\sum_{i=0}^{k-1} 2^i +d (n\log n) + en\\ &= cn - c +d(n\log n) + en\\ &=\mathcal{O}(n\log n) \end{align*} つまり、関数 one_norm_recur2 のメモリ計算量 $M_{total}(n)$ は次のようになる。 \[ M_{total}(n) = M_{input}(n) + M_{recur}(n) = \mathcal{O}(n) + \mathcal{O}(n\log n) = \mathcal{O}(n\log n). \] 同じアルゴリズムでありながら、再帰計算の場合にはメモリ計算量のオーダーが $\mathcal{O}(n)$ から $\mathcal{O}(n\log n)$ へと上がってしまうことがわかった。
Fibonacci数の計算
Fibonacci数の計算は、再帰再訪--計算時間の「Fibonacci数列」で紹介した。
再帰呼び出すしを使ってn番目のFibonacci数を返す杉の関数 fibonacci_recur の計算量評価を考える。
def fibonacci_recur(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)
二項係数
二項係数 $\binom{n}{k}$ は \[ \binom{n}{k} = \frac{n!}{(n-k)! \times k!} \] で定義される。 次の二項係数を計算するスクリプトは、明らかに推奨できない。
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
def binomial_0(n, k):
return fact(n) / fact(n - k) / fact(k)
n = int(raw_input("Binomial coefficent n > k : n = "))
k = int(raw_input("\t k = "))
start_time = time.time()
bino_0 = binomial_0(n, k)
end_time = time.time()
print "Primitive + for version: used time = :", end_time - start_time, "[sec]"
print "\tBinomial coefficent = ", bino_0
二項係数$\binom{n}{k}$の計算で $n$ が大きくなると階乗 $n!$ を求めること自体が以下の2つんぴみで困難になるからだ。 その困難の1つは階乗計算に再帰的定義を使っていることにある。 この方法では再帰の深さ $n$ に応じて計算量が増大することによる。 再帰の深さががシステム設定を越えてしまうと、再帰呼び出しに呼び出しにも失敗する。
上の二項係数のスクリプトでは $\binom{400}{1}, \binom{400}{399}$が 400 であることは直ぐにわかるにも関わらず巨大整数 400! を計算しなくてはならない。 システムごとに異なった、階乗の場合では許容可能な整数桁を簡単に上回って正しい計算ができないことを計算の不安定性ということがある。
計算スピードを上げるために、階乗計算を次のように for文で書いてみよう。
def fact2(n):
if n == 0:
return 1
else:
fa = 1
for i in range(1, n + 1):
fa *= i
return fa
では、次のように二項係数で成立する漸化式 \[ \binom{n}{k} = \binom{n - 1}{k- 1} + \binom{n - 1}{k} \] を使って再帰的によって計算するのはどうだろうか。 この場合、$k\approx n/2$ 程度で再帰呼び出しの深さが最大になることに注意しよう。
def binomial_1(n, k):
if k == 0:
return 1
elif n == k:
return 1
else:
return binomial_1(n - 1, k- 1) + binomial_1(n - 1, k)
さらに、二項係数の次の関係式に注目しよう。 \begin{align*} \binom{n}{k} &= \frac{n\times (n-1)\times (n-2)\times \dots \times (n-k+1)} {k\times (k-1)\times\dots\times 1} &= \frac{n}{k}\binom{n-1}{k-1} \end{align*}
この関係を使うと次の二項係数の再帰的定義を書くことができる。 ただし、n と k の掛け算の位置には配慮が必要である。
def binomial_2(n, k):
if k == 0:
return 1
else:
return binomial_2(n - 1, k- 1) * n / k
