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

計算量(オーダー)

キーワード

計算量、オーダ、、NP問題


計算量のイメージ

アルゴリズムで重要なことは、少ない計算量(短い時間)で、解に達することです。
例えば、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

NP問題

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

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

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

NP問題の近似解法

NP問題を、厳密解を得ることはやや犠牲にして、比較的計算量を減らして近似解を得ようとする方法が試みられています。

局所探索法
最初から全範囲を対象にするのではなく、ある値とその近傍での暫定最適値を求めます。多様な局所で試みて全体の最適解を求めます。
分枝限定法
起こり得る全てのデータを組み合わせ、一部の変数を固定したときの解合を調べ、データの組合せのうち無駄なものを除き、実際に調べる組合せ数を減らす方法です。
分割統治法
問題を幾つかの部分問題に分解して,それぞれの部分問題を再帰的に解いた後,部分問題の解ををつなぎ合わせて、最終的に元の問題を解決する方法です。
貪欲法(グリーディー法)
最適解が局所的に最適な解を繰り返し選ぶことで得られ最適解が部分問題に対する最適解を含むという性質 がある場合、問題全体のことは考えずに、問題をある尺度に沿って分解し、各時点で最良の解を選択し、これを繰り返すことによって、全体の最適解を得る方法です。