指数関数的と多項式的

質問

アルゴリズムの計算量を考えるときに，そのステップ数が指数関数的に増えるか多項式的に増えるかで，アルゴリズムが有用かどうかの分かれ目になると思うのですが，具体的にはどういう違いなのでしょうか？計算量がステップ数の多項式で表されるとき，その次数がいくらであっても，指数関数的でなければ有用なのでしょうか？

回答No.2

noname#221368 · ベストアンサー

具体的に、という事なので、具体的にやってみます。

　まずステップ数とは、演算量という事で良いでしょうか？。そうであれば、数値計算プログラム（数値計算プログラムだけですよ）の計算時間は、演算量に比例すると思って、実用的には問題ありません。比例係数は、問題の種類とマシンの性能で決まります。特に演算が四則演算のみなら、ほぼマシンの性能で、比例係数は決まります。四則演算の１回は、CPUの１クロック（１動作）に正確に対応する、と思ってかまわないからです。

　四則演算のみの問題として、ｎ×ｎの係数行列を持つ、連立１次方程式を考えます。未知数の数はｎなので、ｎが問題の規模です。ガウスの掃き出し法を使うとすると、演算量はｎ^3に比例します（計算手順を思い出せば、すぐわかります）。

　具体的な話では、演算量から、適正な問題規模を考える方が、たぶん正解です。

　こんな時代がありました。CPUは8bitで速度はMHzにすらとどかず、メモリは64KBで、20MBのHDが200万もした・・・。こんな時代に、100×100のガウスの掃き出し法をやらせたら、30分くらいかかりました。1000×1000なら30000分＝約20日。10000×10000なら57年。つまりこの時代、掃き出し法に対する適正規模は、100×100程度だった訳です。理由は、仕事の一部の計算作業と考えても、許容できる時間だからです。

　ところが問題規模というのは、時代の要請でもあります。この時代でも数1000元の問題規模が要求されました。例えば3000元なら、1.5年です。ガウスの掃き出し法は当時、有用でありませんでした。メモリの問題もありました。その結果、スカイライン法や共役勾配法が考えだされ、演算量はn^2程度にまで抑えられます。これなら約６日です。スカイライン法や共役勾配法は、有用な方法でした。他にやりようがなかったし、６日待つ事は不可能ではないからです。

　次にフーリエ変換を考えます。フーリエ変換を定義通りに計算すると、波数ｎまでとるとして、ｎ^2の演算量です。ふつうはｎを100もとれば十分ですから、さっきの例でいくと、10分程度です。ところがフーリエ変換は四則演算だけではありません。sin，cosの計算があります。sin，cosは、内部で本質的にはテーラー展開に従い、四則演算で処理されます。この時間が余計にかかります。計算時間は、四則演算だけのケースの３倍くらいには、すぐなります。するとやはり30分です。フーリエ変換は、問題の種類が違います。

　ふつうはｎ＝100くらいが適正規模で、30分は人間の許容範囲だからOKでは？・・・、とはなりません。問題の種類には、その計算の使われ方も入ってきます。フーリエ変換は、多数の波形データの周波数特性を比較するために、よく使用されます。波の数は、実際問題として、100や200にはすぐなります。20日や40日に、すぐなってしまう訳です。

　そこで高速フーリエ変換が出てきます。高速フーリエ変換は、演算量をlog2(ｎ^2)＝2×log2(ｎ)程度に抑えます。そうすると単純計算すれば、１波形あたり、1/2000秒という驚くべき結果になり、100や200の波形処理は、１秒以内にできる事になります。

　1/2000秒は単純にしすぎで、実際の時間はもっとかかりりますが、100倍だとしてもたかが知れてます。オーダー比較としてはこんなものです。高速フーリエ変換は、とにかく「桁違いに」速いです。その理由はlogの性質です。logの発散って、数値で追跡すると発散するように見えませんよね？。logの収束が、これが収束か？と言いたくなるように。

　そういう訳で、演算量がlog(ｎ)の計算方法は、コンピューターが信じられないほど速くなった現在でも、非常に有用です。

　最後に指数関数的、2＾ｎのような場合。指数関数がlogの逆関数である事を思えば、ちょっとした問題規模に対してさえ、ほぼ望みがなく有用でないのは、明らかと思います（今でも）。しかし他に方法がなければ使います。有用と言わざる得ないが、ひどいもんだ・・・、とボヤキながら(^^)。

　今から20年くらい前の大型汎用機（ビルの１フロアを占領するような奴）やスパコンは、CPU10MHz程度，メモリ64MB，HDだけは沢山あった、という状態でした。今ではPCでさえ、CPU3GHz×クワッドコア×64bit，メモリ4GB，HD500GBなど当たり前になって来てます。

　計算時間など体感する事はないのかも知れませんが、昔はこんな状況でした(^^)。

お礼

ありがとうございます．

回答No.1

Tacosan

「問題の大きさ」に対して「多項式で表される」か「指数関数で表される」か, という区別です. 「計算量がステップ数の多項式で表される」というのは意味不明. 「時間計算量」でも「空間計算量」でも, 「ステップ数の多項式で表される」のは当然です.

で, 理論的にはこの区別をするわけですが, もちろん現実的には「多項式的だから有用」ということではないです. 問題の大きさにもよるけど, せいぜい 3乗くらいに収まってくれないと「現実的に使えるもの」ではありません. できれば 2乗以下にしたいところ.

お礼

ありがとうございます．