【アルゴリズム】アルゴリズムの性能評価

アルゴリズムとは？

簡単に言うとある値または値の集合を入力として受け取り値または値の集合を出力として生成する、明確に定義された計算手続きのことです。つまり、コンピュータが問題を解く時に必ず必要になってきます。

アルゴリズムの性能とは？

問題を解く時にアルゴリズムの効率や性能を知りたい場合は、どのように図るのでしょうか。それは、アルゴリズムが問題を解くのにどれだけの時間がかかるのかとどれだけのメモリ空間を必要とするかと言うことです。アルゴリズムの計算時間は、アルゴリズムの計算ステップ数と使用する時間に依存します。

アルゴリズムの性能の尺度（オーダー）

アルゴリズムは入力を受け取り出力するものだと言いました。当然入力が増えれば実行時間やメモリの消費量も増えます。入力データの大きさは整数nで表します。並べ替え問題の場合は、並べ替えるデータ数です。グラフ問題の場合は、頂点や辺の数などです。

配列Aを挿入ソートでソートする　　　　　　　　　　　　コスト　　実行回数
for j = 2 to A.length                       c_1       n
    key = A[j]                              c_2       n-1
    //ソート済み列A[1..j-1]にA[j]を挿入する     0         n-1
    i = j -1                                c_4       n-1
    while i > 0 かつ A[i] > key　            c_5     　①
        A[i+1] = A[i]                       c_6     　②
        i=i-1                               c_7     　③
A[i+1] = key                                c_8       n-1

\(①：\sum_{j=2}^{n}t_j\) \(②：\sum_{j=2}^{n}(t_j-1)\)\(③：\sum_{j=2}^{n}(t_j-1)\)

挿入ソートの最悪の場合の実行時間は、
\(T(n)=\)\(c_1n+c_2(n-1)+\)\(c_4(n-1)\)\(+c_5(\sum_{j=2}^{n}j)\)\(+c_6(\sum_{j=2}^{n}(j-1))\)\(+c_7(\sum_{j=2}^{n}(j-1))\)\(+c_8(n-1)\)

\(=c_1n+c_2(n-1)\)\(+c_4(n-1)\)\(+c_5(\frac{2}{n(n+1)-1})\)\(+c_6(\frac{2}{n(n-1)})\)\(+c_7(\frac{2}{n(n-1)})\)\(+c_8(n-1)\)

\(=(\frac{2}{c_5}+\)\(\frac{2}{c_6}\)\(+\frac{2}{c_7})n^2+\)\((c_1+c_2+c_4+\frac{2}{c_5}-\frac{2}{c_6}-\frac{2}{c_7}+c_8)n\)\(-(c_2+c_4+c_5+c_8)\)

\(T(n)を定数a,b,cを用いるとan^2+bn+c\)\(と表せます。\)さらに手続きを解析を容易にするために単純化行うために、\(c_i\)を無視する。

オーダーの表現法

\(O記法（Upper bound）\)

\(ある与えらた関数g(n)に対して、\)\(O(g(n))を関数の集合\)
\(O(g(n))\)\(=\{f(n):ある正の定数c,n_0が存在して、\)\(全てのn\ge n_0に対して\)\(0\le f(n)\le cg(n)を満たす。\}\)\(と定義します。\)
つまり、、
\(O記法\)は、関数に対して定数倍の範囲内での上界を与える。ある正定数\(n_0,c\)が存在して、\(n_0\)以上の\(n\)において\(f(n)\)の値が常に\(cg(n)\)の下にある（等しい場合を含む）時\(f(n)=O(g(n))とかく\)

\(\Omega記法（Lower bound）\)

\(ある与えらた関数g(n)に対して、\)\(\Omega(g(n))を関数の集合\)
\(\Omega(g(n))\)\(=\{f(n):ある正の定数c,n_0が存在して、\)\(全てのn\ge n_0に対して\)\(0\le cg(n)\le f(n)を満たす。\}\)\(と定義します。\)
つまり、、
\(\Omega記法\)は、関数に対して定数倍の範囲内での下界を与える。ある正定数\(n_0,c\)が存在して、\(n_0\)以上の\(n\)において\(f(n)\)の値が常に\(cg(n)\)の上にある（等しい場合を含む）時\(f(n)=\Omega(g(n))とかく\)

\(\Theta記法(Tight bound)\)

\(ある与えらた関数g(n)に対して、\)\(\Theta(g(n))を関数の集合\)
\(\Theta(g(n))\)\(=\{f(n):ある正の定数c_1,c_2,n_0が存在して、\)\(全てのn\ge n_0に対して\)\(0\le c_1g(n)\le f(n)\le c_2g(n)を満たす。\}\)\(と定義します。\)
つまり、、
\(\Theta記法\)は、関数を定数倍の範囲に限定する。ある正定数\(n_0,c_1,c_2\)が存在して、\(n_0\)以上の\(n\)において\(f(n)\)の値が常に\(c_1g(n)とc_2g(n)\)の間にある（等しい場合を含む）時\(f(n)=\Theta(g(n))とかく\)

引用：https://www.dotnetlovers.com/article/129/explanation-on-asymptotic-notations

オーダーの求め方

for/whileループ

Sの計算量が\(1\lt i \le m\)までで全て\(t(n)\)なら\(T(n)=mt(n)\)になります。

for i = 1 to m:
    S

if/else文

S_1,S_2の計算量がそれぞれ\(t_1,t_2\)なら\(max\{t_1(n),t_2(n)\}\)になります。

if(条件文):
    S_1
else:
    S_2

連続した文

S_1,S_2の計算量がそれぞれ\(t_1,t_2\)なら\(t_1(n)+t_2(n)\)になります。

...
S_1
S_2
...

組み合わせ

関数\(g_1(n)\)のオーダーが\(O(f_1((n))),\)\(g_2(n)\)のオーダーが\(O(f_2((n)))\)の時、
\(・g_1(n)+\)\(g_2(n)は、\)\(O(max(f_1(n),f_2(n)))\)
\(・g_1(n)\)\(g_2(n)は、\)\(O(f_1(n)f_2(n))\)
\(・ag_1(n)\)\(は、\)\(O(f_1(n))\)\(どんな定数aでもおk\)

実際の例

\(Linear Time: O(n)\)

配列Aの最大の要素を求める

max = a[1]
for i = 2 to n {
    if (a[i] > max) max = a[i]
}

\(Quadratic Time: O(n^2)\)

\((x_1,y_1),…,(x_n, y_n)\)の座標があり、その中で最も近い座標の距離を求める。

min = (x[i] - x[2])^2 + (y[1] - y[2])^2
for i = 1 to n {
    for i = 1 to n {
       d = (x[i] - x[j])^2 + (y[i] - y[j])^2
       if (d < min) min = d
    }
}

\(Polynomial Time: O(n^k)\)

グラフが与えられ、、サイズがkの独立集合（＝1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 Vで、V の任意の2つの頂点をつなぐ辺が存在しない場合）があり、２つのノードが辺で結ばれていないようなk個のノードがあるかを求める。

for each subset S of k nodes{
    check whether S in an independent set
    if (S is an independent set) {
        report S is an independent set
    }
}

\(Exponential Time: O(n^22^n)\)

グラフが与えられて、最大の独立集合を求める

S* = φ
for each subset S of node {
    check whether S in an independent set
    if (S is largest independent set seen so far){
        update S* = S
    }
}

オーダーの名前

実行時間の例