Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

計算量とBig-θ記法.

アルゴリズムの計算量を簡易的に把握するために、よくBig-Oを用いることがある。たとえば、O(n)やO(log n)といった具合になんとなくlog n < n < n^2というイメージを持っている人は多いと思う。このような記法は漸近的成長と呼ばれている。今回はその中でBig-θについてまとめる。

Big-θ(ビッグ・シータ)


{ \displaystyle
θ(g(n))
} とはg(n)と等しい速さで成長するという関数の集合を表している。
たとえば、 { \displaystyle
f(n)\inθ(g(n))
}のようにある関数f(n)がg(n)と成長率の等しい関数の集合に属する場合、 必要十分条件{ \displaystyle
c_1
}, { \displaystyle
c_2
}, { \displaystyle
n_0
} となり、 { \displaystyle
∀_n>n_0
}において、漸近的に成長して十分大きな極限になると { \displaystyle
0\leqq c_1g(n)\leqq f(n)\leqq c_2g(n)
}となる。
この不等式が成り立つ場合、 { \displaystyle
f(n)
}{ \displaystyle
θ(g(n))
}に属すると言うことができる。

では逆に { \displaystyle
g(n)\inθ(f(n))
}は成り立つかどうかを確かめる。先ほどの不等式に対して { \displaystyle
c_1
}で除算すると以下になる。
{ \displaystyle
0\leqq g(n)\leqq \frac{1}{c_1}f(n)\leqq \frac{c_2}{c_1}g(n)
} (1)

また、同様に { \displaystyle
c_2
}で除算すると以下になる。
{ \displaystyle
0\leqq \frac{c_1}{c_2}g(n)\leqq \frac{1}{c_2}f(n)\leqq g(n)
} (2)

{ \displaystyle
c_1
}{ \displaystyle
c_2
}で除算した上記二つの(1)及び(2)の不等式を組み合わせると以下とすることが出来る。
{ \displaystyle
0\leqq \frac{1}{c_2}f(n)\leqq g(n)\leqq \frac{1}{c_1}f(n)
} (3)

ここで、{ \displaystyle
1/c_1
}{ \displaystyle
1/c_2
}は定数であるため、(3)の不等式に対してそれぞれ { \displaystyle
c_2
}{ \displaystyle
c_1
}に置き換えることが可能である。
{ \displaystyle
0\leqq c_1f(n)\leqq g(n)\leqq c_2f(n)
} (4)

上記(4)の不等式より、g(n)はθ(f(n))に属するビッグ・シータの関係となることがわかる。

ビッグ・シータの例


たとえばビッグ・シータは以下の様に表すことができる。

  1. { \displaystyle
\frac{1}{2}n^2\inθ(n^2)
}

  2. { \displaystyle
8\sqrt{n}\inθ(\sqrt{n})
}

  3. { \displaystyle
2n-2\sqrt{n}\inθ(n)
}

  4. { \displaystyle
7n^4+2n^3-4n\log n+\sqrt{n}\inθ(n^4)
}

  5. { \displaystyle
In{n}\inθ(\log{2} n)
}

  6. { \displaystyle
\pi^2\inθ(1)
}



類似の漸近的表記法


  • { \displaystyle
f(n)\in o(g(n))\approx f(n)<g(n)
} : 漸近的に成長率は低くなる

  • { \displaystyle
f(n)\in O(g(n))\approx f(n)\leqq g(n)
} : 漸近的に成長率はほぼ同じか低くなる

  • { \displaystyle
f(n)\in θ(g(n))\approx f(n)=g(n)
} : 漸近的に成長率はほぼ同じとなり同様に成長する

  • { \displaystyle
f(n)\in Ω(g(n))\approx f(n)\geqq g(n)
} : 漸近的に成長率はほぼ同じか上界である

  • { \displaystyle
f(n)\in ω(g(n))\approx f(n)>g(n)
} : 漸近的に成長率は上界である


アルゴリズムの計算量を測る時は上記のような表記法が挙げられる。
どの表記法においても、係数が表すのは大きさになるため重要ではなく、成長率に注目してアルゴリズムを評価することになる。

CompleteGraphの計算量


完全グラフ(CompleteGraph)を形成する際の計算量をビッグ・シータで計算してみる。
CompleteGrapthとは全てのノード同士がエッジで結びついているグラフである。

f:id:fixxman:20151012023259p:plain

File:Complete graph K5.svg - Wikimedia Commons


ノードの数をnとし、エッジの数をmと置くと、CompleteGraphにおけるエッジの計算量は以下で表現できる。(上記の星の図に当てはめてみるとわかりやすい)
{ \displaystyle
m=\frac{n(n-1)}{2}\in θ(n^2)
}

実際にCompleteGraphを作成するコードをPythonで書いてみると以下になる。

#! /usr/bin/python

def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    (G[node1])[node2] = 1
    if node2 not in G:
        G[node2] = {}
    (G[node2])[node1] = 1
    return G

def clique(n):
    # Return the number of edges
    if(n%2==0):
        result = (n/2)*(n-1)
    else:
        result = (n/2)*(n-1) + (n-1)
    return result

def correct_clique(n):
    G = {}
    for i in range(n):
        for j in range(n):
            if i<j: make_link(G, i, j)
    return sum([len(G[node]) for node in G.keys()])/2

for n in range(1, 10):
    print n, correct_clique(n), n*(n-1)/2


出力は1列目にノードの数、2列目にエッジ生成処理の結果、3列目に上記で出した計算式の値を返すようになっている。
この出力から2列目と3列目が一致していることがわかる。

1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
7 21 21
8 28 28
9 36 36


このようにアルゴリズムは生成処理を行わなくとも解を得ることが可能であり、また計算量を出して漸近的な成長率を把握することができる。

現場からは以上です。

参考

Remove all ads