No.2ベストアンサー
- 回答日時:
具体的に、という事なので、具体的にやってみます。
まずステップ数とは、演算量という事で良いでしょうか?。そうであれば、数値計算プログラム(数値計算プログラムだけですよ)の計算時間は、演算量に比例すると思って、実用的には問題ありません。比例係数は、問題の種類とマシンの性能で決まります。特に演算が四則演算のみなら、ほぼマシンの性能で、比例係数は決まります。四則演算の1回は、CPUの1クロック(1動作)に正確に対応する、と思ってかまわないからです。
四則演算のみの問題として、n×nの係数行列を持つ、連立1次方程式を考えます。未知数の数はnなので、nが問題の規模です。ガウスの掃き出し法を使うとすると、演算量はn^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程度にまで抑えられます。これなら約6日です。スカイライン法や共役勾配法は、有用な方法でした。他にやりようがなかったし、6日待つ事は不可能ではないからです。
次にフーリエ変換を考えます。フーリエ変換を定義通りに計算すると、波数nまでとるとして、n^2の演算量です。ふつうはnを100もとれば十分ですから、さっきの例でいくと、10分程度です。ところがフーリエ変換は四則演算だけではありません。sin,cosの計算があります。sin,cosは、内部で本質的にはテーラー展開に従い、四則演算で処理されます。この時間が余計にかかります。計算時間は、四則演算だけのケースの3倍くらいには、すぐなります。するとやはり30分です。フーリエ変換は、問題の種類が違います。
ふつうはn=100くらいが適正規模で、30分は人間の許容範囲だからOKでは?・・・、とはなりません。問題の種類には、その計算の使われ方も入ってきます。フーリエ変換は、多数の波形データの周波数特性を比較するために、よく使用されます。波の数は、実際問題として、100や200にはすぐなります。20日や40日に、すぐなってしまう訳です。
そこで高速フーリエ変換が出てきます。高速フーリエ変換は、演算量をlog2(n^2)=2×log2(n)程度に抑えます。そうすると単純計算すれば、1波形あたり、1/2000秒という驚くべき結果になり、100や200の波形処理は、1秒以内にできる事になります。
1/2000秒は単純にしすぎで、実際の時間はもっとかかりりますが、100倍だとしてもたかが知れてます。オーダー比較としてはこんなものです。高速フーリエ変換は、とにかく「桁違いに」速いです。その理由はlogの性質です。logの発散って、数値で追跡すると発散するように見えませんよね?。logの収束が、これが収束か?と言いたくなるように。
そういう訳で、演算量がlog(n)の計算方法は、コンピューターが信じられないほど速くなった現在でも、非常に有用です。
最後に指数関数的、2^nのような場合。指数関数がlogの逆関数である事を思えば、ちょっとした問題規模に対してさえ、ほぼ望みがなく有用でないのは、明らかと思います(今でも)。しかし他に方法がなければ使います。有用と言わざる得ないが、ひどいもんだ・・・、とボヤキながら(^^)。
今から20年くらい前の大型汎用機(ビルの1フロアを占領するような奴)やスパコンは、CPU10MHz程度,メモリ64MB,HDだけは沢山あった、という状態でした。今ではPCでさえ、CPU3GHz×クワッドコア×64bit,メモリ4GB,HD500GBなど当たり前になって来てます。
計算時間など体感する事はないのかも知れませんが、昔はこんな状況でした(^^)。
No.1
- 回答日時:
「問題の大きさ」に対して「多項式で表される」か「指数関数で表される」か, という区別です. 「計算量がステップ数の多項式で表される」というのは意味不明. 「時間計算量」でも「空間計算量」でも, 「ステップ数の多項式で表される」のは当然です.
で, 理論的にはこの区別をするわけですが, もちろん現実的には「多項式的だから有用」ということではないです. 問題の大きさにもよるけど, せいぜい 3乗くらいに収まってくれないと「現実的に使えるもの」ではありません. できれば 2乗以下にしたいところ.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) プログラミングって本来数学的な計算をする為のものではないのですか? 学校で配られたFortran90 11 2022/08/25 22:14
- 数学 『因数に分解するということ』 9 2022/06/27 06:14
- 数学 数2Bの数列の問題です。 自分は、 まず数列 an=ar^(n-1)と置き こちらの問題の、y= の 1 2022/07/07 16:26
- 数学 高3の微分についての質問です。 ある説明に「数学IIで扱ったのは多項式関数で、この時極限値は必ず存在 6 2023/07/02 10:04
- 数学 多変数関数の微分とテイラー展開について 5 2022/04/24 16:55
- 数学 多項式の性質と無理数・有理数 2 2022/06/21 06:50
- 数学 特定の座標点を通る回帰を行う方法について。 2 2022/10/10 10:27
- 物理学 ポテンシャルが有限で不連続の時、右側の波動関数をφ1(x)、左側をφ2(x)とする。境界条件の「波動 2 2023/06/04 13:53
- その他(Microsoft Office) 従業員増減対応で当番種類の増減対応な当番表 21 2022/07/19 07:30
- 数学 『数は実在するのか』 6 2023/06/04 15:15
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
2次関数って何の仕事で必要な...
-
倍率とデシベルの計算式
-
2の128乗の計算方法
-
信頼区間90%は何σ?
-
10^0.2 = 1.58489319246111の計...
-
「再帰的」の意味を教えてください
-
100の101乗と101の100乗ではど...
-
指数計算を教えてください
-
常用対数の求め方 log10の2は約...
-
中3の有効数字の範囲の問題で √...
-
IEEE標準形式とエクセス64形式
-
1512の1/5乗
-
らせんRの計算の仕方
-
値引きの計算
-
「評価する」とは?
-
減少率計算式教えて下さい
-
「理論計算」と「数値結果」の違い
-
1.01の12乗の計算
-
3割の計算
-
正規分布表の問題なんですが(;_;)
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
2の128乗の計算方法
-
libre 表計算ソフトの計算がう...
-
信頼区間90%は何σ?
-
3割の計算
-
減少率計算式教えて下さい
-
倍率とデシベルの計算式
-
1.01の12乗の計算
-
らせんRの計算の仕方
-
中3の有効数字の範囲の問題で √...
-
電力ケーブルのインピーダンス...
-
◯分を時間になおすと
-
常用対数の求め方 log10の2は約...
-
10^0.2 = 1.58489319246111の計...
-
「再帰的」の意味を教えてください
-
出来高の計算
-
2次関数って何の仕事で必要な...
-
実生活で役に立つ数学ってあり...
-
「評価する」とは?
-
電卓の機能の名称が分からない...
-
円周率の計算式って何ですか?
おすすめ情報