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。