Web教材一覧>
アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)
計算量、オーダ、O、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次式、
anxn+an-1xn-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回になります。
ここで、乗算の回数を計算量の尺度にしたのは、加減算に比べて乗除算に要する時間は非常に大きいからです。すなわち、このほうが短い時間で計算されるので、優れたアルゴリズムだといえます。
このように、アルゴリズムでの主要な操作に着目して、解に達するまでに必要な操作回数のことを計算量(注)(オーダー)といい、O (nの式) で表現します。
(注)計算量には時間計算量と空間計算量があります。ここでの計算量は時間計算量のことです。空間計算量とは、アルゴリズムに必要となる変数領域の大きさです。
O (nの式) の表現では、次のように簡略化します。
・多項式になる場合、n→大としたとき最大になる項だけにする。
(Cの場合:(1/2)n2+(1/2)n を (1/2)n2 とする)
・係数を無視する。(Cの場合:(1/2)n2 を n2 とする)
すなわち、Cの計算量はO (n2) になります。
このようにする理由は、
・計算量が問題になるのは、nが大きいときに限られる。
・nの式による違いに対して、係数の違いは相対的に影響が小さい。
からです。主なnの式のグラフを右図に示します(両対数目盛)。
いくつかのアルゴリズムについて、計算量の尺度としてよく用いられる操作と、計算量を列挙します。
計算量がO (nm) になるアルゴリズムが存在する問題をP問題といいます。P問題は、数学者にとっては、効率的に解ける問題だとして取り扱われます(実務的には、n100 効率的だとはいえませんが)
ところが、一般的な解法が見つからない問題や、解法はあるのだが、O (nm) でにはならない問題(O (2n) や O (n!) が多くあります。それをNP問題といいます。
数学的な関心事としては、
P=NP(本当はP問題として解けるのに、未だ発見されていないだけだ)
P≠NP(本当にP問題にはならない問題があるのだ)
のどちらなのだろうかが、大きな課題になっています。
例えば、ある程度の大きさの数を「素因数分解」することは、現在は決定的な解法が知られておらず、考えられるすべての場合をしらみつぶしに調べなければなりません。それが公開鍵暗号方式の基盤になっています。「ナップザック問題」「巡回セールスマン問題」なども現在ではNP問題とされています。
なお、一般的にNP問題を解くのには長時間がかかりますが、nが小さいときには、実務的に解くことができるものもあります。
NP問題を、厳密解を得ることはやや犠牲にして、比較的計算量を減らして近似解を得ようとする方法が試みられています。