計算量について

質問

プログラムの計算量について質問です。計算量には時間計算量と空間計算量がありますが、そのうち空間計算量の概念がいまいち分かりません。アルゴリズムが必要とする記憶容量といっても漠然としててどのように求めたらいいのか分かりません。
例えばプログラムの基本構成が
for(n回){
for(n回){
処理
}
}
のようだったら時間計算量がO(n^2)というのはわかるんですが、この場合の空間計算量はどのようになりますか?

回答No.2

Tacosan

malloc や配列などを使わないで, 「単純な変数」を使うだけなら O(1) になります. 例えば
double x = 0;
for (i=0; i < n; ++i) {
for (j=0; j < n; ++j) {
x += a[i] * b[j];
}
}
なんかだと, 結局 (入力の他に) x しか使っていないので O(1).
これがリストに結果を全部保存したりすると O(n^2) になっちゃいます.

お礼

返答ありがとうございます。
結果をx[i][j]などの行列に格納していくようならO(N^2)になるということですか。なるほどわかりました。ありがとうございます。

回答No.1

Tacosan

この形だと「処理」のところで使うメモリを使い回せるのが普通なので O(1) になりそうな雰囲気はありますが, 厳密には「処理」がどのようなことをしているかわからないのでなんともいえません.
空間計算量は時間計算量より常に小さいので O(n^2) であることは確実なんですが....

お礼

返答ありがとうございます。メモリを使い回せるときと新たにメモリを使う場合というのは具体的にどのような処理になるのでしょうか？毎回メモリを新たに使う場合だとO(n^2)になるという解釈でよろしいのでしょうか?