計算量とは
ある問題を解くのにどのくらい手間を要したかを数値で表したものを計算量といいます。
時間計算量、空間計算量とは
コンピュータが特定の手順に従って与えられた問題を解く際に必要とする手順の回数を時間計算量、必要とする記憶領域の容量のことを空間計算量といいます。
O記法について
入力サイズnに対して、アルゴリズムがどれくらい時間がかかるか予測を立てるのにO記法が使われます。
例：O(n), O(n^2), O(log n), O(2^n)
計算量については、入力サイズに対してどのようにスケーリングするかが重要です。そのため最も影響の多い項のみが考慮され、他の項は無視されます。
例：O(3n^2+2n+1) ≒ 0(n^2)
nが大きくなると、例えばO(2^n)はどんどん大きくなっていきますが、O(log n)はnが大きくなってもあまり大きくならず少ない計算回数で済みます。
このように、アルゴリズムを実装するときには、時間計算量、空間計算量を意識しながら最適化されたコードを書くことが重要です。