Next: 2.2.1.0.2 問
Up: 2.2.1 計算量についての準備
Previous: 2.2.1 計算量についての準備
計算量の議論をする時は、ごく粗いオーダーを示すだけのときが多い。例え
ば、正確に数えて 回である場合、低次の項を無視して、
回と言ったり、Landau の記号を用いて、 である、と言った
りする。
空間計算量とは、要するに、どれだけのメモリーが必要になるか、である。
プログラムがどの程度の量のメモリーを使用するか、
- 必要とあれば、見積もれるようになっておかなければならない。
- 新しいプログラムで計算する時、あるいは同じプログラムを使い続ける場合
でも、これまでとは大きくパラメーターを変える時、必要とするメモリー量を
見積もるべきである。
今回のような問題では、行列を記憶するのに必要とするメモリーの量だけ計
算すれば、普通は十分である。 次正方行列には、 個の成分がある。
通常、倍精度浮動小数点数は 1 つ 8 バイト(1 バイトとは、通常 8 ビットの
ことを指す。以下では「バイト」を ``B'' と略記する。)だから、 B
必要になる。例えば ならば、
B 約 MB
必要になる2.5。
Next: 2.2.1.0.2 問
Up: 2.2.1 計算量についての準備
Previous: 2.2.1 計算量についての準備
Masashi Katsurada
平成17年6月2日