next up previous contents
Next: 2.2.1.0.2 問 Up: 2.2.1 計算量についての準備 Previous: 2.2.1 計算量についての準備

2.2.1.0.1 注

計算量の議論をする時は、ごく粗いオーダーを示すだけのときが多い。例え ば、正確に数えて $N^3/3+N^2/2+2$ 回である場合、低次の項を無視して、 $N^3/3$ 回と言ったり、Landau の記号を用いて、$O(N^3)$ である、と言った りする。

空間計算量とは、要するに、どれだけのメモリーが必要になるか、である。 プログラムがどの程度の量のメモリーを使用するか、

今回のような問題では、行列を記憶するのに必要とするメモリーの量だけ計 算すれば、普通は十分である。$N$ 次正方行列には、$N^2$ 個の成分がある。 通常、倍精度浮動小数点数は 1 つ 8 バイト(1 バイトとは、通常 8 ビットの ことを指す。以下では「バイト」を ``B'' と略記する。)だから、$8 N^2$ B 必要になる。例えば $N=1000$ ならば、 $8\times 1000^2$ B $=$$8$ MB 必要になる2.5
next up previous contents
Next: 2.2.1.0.2 問 Up: 2.2.1 計算量についての準備 Previous: 2.2.1 計算量についての準備
Masashi Katsurada
平成17年6月2日