計算量のオーダー記法
関数の漸近的な振る舞いを評価する便利な方法としてオーダー記法というものがよく用いられます.
大雑把に説明すると, 関数の支配項(最も大きい部分)を抜き出し, その係数を無視したものをその関数のオーダーと呼びます. 例えば, $3n^2+5n+2$ の支配項は $3n^2$ であり, 係数を無視すると $n^2$ になります. よって$3n^2+5n+2$ は $n^2$ のオーダーであるといい, $3n^2+5n+2=O(n^2)$と書きます.
この説明だと多項式でないものに対してオーダーが定義できないので, 以下に厳密な定義を与えます.
二つの関数$f,g\colon \mathbb{N} \to \mathbb{R}_{>0}$を考える. ある定数$c>0$が存在して, 十分大きな全ての$n\in \mathbb{N}$に対して$f(n) \le c\cdot g(n)$が成り立つとき, $f(n)=O(g(n))$と表す.
例. 1からnまでの和を求める関数sum_to_n
def sum_to_n(n):
S=0
for i in range(n):
S=S+i
return S
計算量の例で扱った関数sum_to_nを再掲しています. この関数の計算時間は$n+1$なので, オーダー表記をすると$O(n)$となります.
例2. 1からnまでの和を計算する関数sum_to_n2
def sum_to_n2(n):
return n*(n+1)/2
二つ目の例で扱った関数sum_to_n2を再掲しています. この関数の計算量は2なので, オーダー表記をすると$O(1)$となります.
例3. 1からnまでの和を計算する関数sum_to_n3
def sum_to_n3(n):
S=0
for i in range(n):
a = i
S = S+a
return S
例1の関数sum_to_n()と本質的に同じ処理をしています. 計算時間はa=iという操作をしているので, $2n+1$になり, 例1よりも遅くなっていますが, オーダーは$O(n)$となります. このように, 細かく見ると違う処理をしているが本質的に同じ処理をしている関数は多くの場合, 計算時間をオーダーで評価すると同じになります. このように, オーダー表記はアルゴリズムの(細かい処理を無視した)本質的な計算時間を評価するのに便利です.
例4. 文字列が回文かどうかを判定する関数is_palindrome
def is_palindrome(s):
n = len(s)
for i in range(n):
if s[i] != s[n-i-1]:
return False
return True
途中に
returnが実行されるとその時点で関数の処理は終了します. なので, 例えば上記コードの5行目のように, for文の中で条件に合致するものを見つけたときにreturnすることによってその有無を判定することができます.
関数is_palindromeはfor文の中で1回だけ文字列の比較を行なっているので, ステップ数は高々$n$. よって計算量は$O(n)$.
例5. 二つのリストの結合
def list_concatenate(a,b):
c=a+b
return c
一見するとlist_concatenateのステップ数は1, 即ち計算量は$O(1)$に見えるのですが, 実際にはPythonのリストでa+bを計算しているときはaの後ろにbの要素を順番に一つずつ追加しているので, 要するステップ数は$n$. つまり計算量は$O(n)$となります.
オーダー記法の考え方自体はアルゴリズムの計算量に限らず, テイラー展開など関数の漸近的な振る舞いを知りたい場合によく使われる概念です.
色んなオーダー記法
より一般に, $O(\cdot)$の不等号の向きを逆にしたものなど, 様々なオーダーの概念があります.
二つの関数$f,g\colon \mathbb{N} \to \mathbb{R}_{>0}$を考える.
- ある定数$c>0$が存在して, 十分大きな全ての$n\in \mathbb{N}$に対して$f(g) \ge c\cdot g(n)$が成り立つとき, $f(n)=\Omega(g(n))$ と表す.
- $f(n)=O(g(n))$ かつ $g(n)=O(f(n))$ であるとき, $f(n)=\Theta(g(n))$と表す.
- 任意の定数$c>0$に対してある$n_0\in \mathbb{N}$が存在して, 全ての$n\ge n_0$に対して$f(n)\ge c\cdot g(n)$ 成り立つとき, $f(n)=\omega(g(n))$ と表す. 不等号が逆, すなわち $f(n)\le c\cdot g(n)$ が成り立つとき, $f(n) = o(g(n))$ と表す.
Exercise
以下の問いに答えよ.
- $f(n)=O(g(n))$ でも $g(n)=O(f(n))$ でもないような$f,g$を例示せよ.
- 任意の$c>0$に対して$f(n)=O(n^c)$を満たすような$f$を一つ例示せよ.
- 任意の$c>0$に対して$f(n)=\Omega(n^c)$を満たすような$f$を一つ例示せよ.
- $f(n)=n!$と$g(n)=2^{3n}$に対し, $f(n)=\omega(g(n))$が成り立つことを証明せよ.