Web教材一覧アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)

計算量(オーダー)

キーワード

計算量、オーダー、


アルゴリズムで重要なことは、少ない計算量(短い時間)で、解に達することです。
例えば、2x3+4x2+2x+5 を計算するのに、
   2×x×x×x+4×x×x+2×x+5   ・・・A
とすると、乗算の回数は6回になります。
 この式を変形して、
   (((2x+4)x+2)x)+5   ・・・B
とすれば、乗算の回数は3回になります。
 一般化して、n次式、
   ann+an-1n-1+・・・+a1x+a0
をAのように計算するならば、乗算回数は
   (n+1)+n+・・・+1+0=n(n+1) =(1/2)n2+(1/2)n   ・・・C
になります。また、Bの形式に変形して
   ((...(an×x+an-1)×x+an-1)×...)×x+a0
とすれば、乗算回数はn回になります。
 ここで、乗算の回数を計算量の尺度にしたのは、加減算に比べて乗除算に要する時間は非常に大きいからです。すなわち、このほうが短い時間で計算されるので、優れたアルゴリズムだといえます。

計算量 の表記

このように、アルゴリズムでの主要な操作に着目して、解に達するまでに必要な操作回数のことを計算量(注)(オーダー)といい、 (nの式) で表現します。

(注)計算量には時間計算量と空間計算量があります。ここでの計算量は時間計算量のことです。空間計算量とは、アルゴリズムに必要となる変数領域の大きさです。

(nの式) の表現では、次のように簡略化します。
   ・多項式になる場合、n→大としたとき最大になる項だけにする。
    (Cの場合:(1/2)n2+(1/2)n を (1/2)n2 とする)
   ・係数を無視する。(Cの場合:(1/2)n2 を n2 とする)
 すなわち、Cの計算量は (n2) になります。

このようにする理由は、
   ・計算量が問題になるのは、nが大きいときに限られる。
   ・nの式による違いに対して、係数の違いは相対的に影響が小さい。
からです。主なnの式のグラフを右図に示します(両対数目盛)。

アルゴリズムと計算量の例示

いくつかのアルゴリズムについて、計算量の尺度としてよく用いられる操作と、計算量を列挙します。

●サーチ
 n個の要素をもつ配列aのなかで、与えた値xと同じ値である要素 a[i] を検索することをサーチといいます。サーチでは、比較回数nを計算量の尺度にします。
 リニアサーチでは、xとa[1]、a[2]、a[3]と順に比較していくため、平均比較回数はn/2回の比較が必要になります。それで、 (n) となります。
 それに対して、バイナリサーチでは、探索範囲の中央の要素とxを比較することにより、求める要素がそれより前にあるか後にあるかを調べて検索範囲を絞ります。比較回数をmとすれば、2m=n、すなわち、m=log2n となり、 (log2n)になります。
→参照「サーチ」(al-search

●ソート
 配列aの要素を小さい(大きい)順に並べ替えることをソートといいます。ソートでの計算量尺度として、大小の比較回数と要素の入れ替え操作が考えられますが、一般的には比較回数が用いられます。
 選択整列法では、n個の要素のうち最小の要素を先頭におき、残りの要素のうち最小のものを2番目におくというような操作を繰り返します。比較の回数は、n(n-1)/2になるので、計算量(オーダ)は (n2)になります。
 クイックソートでは、バイナリサーチのように、ある要素よりも小さいグループと大きいグループにわける操作を繰り返すことにより、計算量を減らします。 (n log2n)になります。
→参照「ソート(その2)」(al-sort2

●連立方程式
 n元連立方程式を解くアルゴリズムにガウスの消去法があります。式kの変数xkに着目して、その係数 a[k][k] を1になるように変形し、他の式jの各要素 a[i][j] から、a[k][j]*a[i,j] を引く操作を繰り返すことにより、解に達します。その演算回数を尺度にすると、 (n3)になります。
→参照「連立方程式」(na-renritu-houteishiki

高度な計算量理論

計算量が (n) になるアルゴリズムが存在する問題をP問題といいます。P問題は、数学者にとっては、効率的に解ける問題だとして取り扱われます(実務的には、n100 効率的だとはいえませんが)
 ところが、一般的な解法が見つからない問題や、解法はあるのだが、 (n) でにはならない問題( (2n) や (n!) が多くあります。それをNP問題といいます。

 数学的な関心事としては、
   P=NP(本当はP問題として解けるのに、未だ発見されていないだけだ)
   P≠NP(本当にP問題にはならない問題があるのだ)
のどちらなのだろうかが、大きな課題になっています。

例えば、ある程度の大きさの数を「素因数分解」することは、現在は決定的な解法が知られておらず、考えられるすべての場合をしらみつぶしに調べなければなりません。それが公開鍵暗号方式の基盤になっています。「ナップザック問題」「巡回セールスマン問題」なども現在ではNP問題とされています。
 なお、一般的にNP問題を解くのには長時間がかかりますが、nが小さいときには、実務的に解くことができるものもあります。


アルゴリズムへ