O はランダウの記号
「問題が無限に大きいときの値が」「定数倍の違いを除いてだいたいこんなもの」という意味(厳密な定義はググれ)
無限にという言葉が嫌なら n = 10^100000000000000 くらいを仮定すればいい
例えば 10n^2 + 4n + 2 という式があるとき n = 10^100000000000000 を代入すると
4n+2 は 10n^2 より 100000000000000 桁も小さいゴミなので無視できる
10n^2 の 10 も n = 10^100000000000000 と比べれば些細な違いなので無視する
だから 10n^2 + 4n + 2 = O(n^2)
1. 空間計算量はメモリ使用量だと思えばいい
バイト数でもビット数でもGBで数えてもなんでも構わない
なぜなら何を単位として数えても定数倍変わるだけだから
(ビット単位とGB単位ならたった80億倍しかかわらない n = 10^100000000000000 と比べれば微々たる違い)
2. 計算量を考えるときはまず「問題の大きさ」を定義する。一次元配列なら要素数 n を「大きさ」にすればいい
二次元配列についての問題なら幅wと高さhの二つを「大きさ」としてもいいし
全要素数 n = w*h を「大きさ」としてもいい。考えやすいように何かを自分勝手に採用すればいい
次に空間計算量を求める場合「何が一番メモリを食うか」を考える
ソートなら仮に要素数 n に対して 100^(1000n) 行のプログラムが必要ならば
プログラム自体を格納するためのメモリのほうがワーキング領域よりたぶん大きい
でも普通そんなことはないのでプログラムの大きさは無視し「テンポラリに確保する要素数」を採用する
もちろん「テンポラリに確保するバイト数」でもいい。定数倍違うだけ
あとはゴリゴリ文章題を解く
「要素数 n の配列をこの方法でソートするとき、テンポラリに確保する要素数はいくつになりますか？」
答えが 1000000 log(30n + 2) とかになったならこれを O(logn) と答えればよい