概要

アルゴリズムの演算性能をざっくりと計算するO記法と計算量の求め方についての前提知識をまとめる。

計算量（オーダー）とは

アルゴリズムの演算性能をデータ量の増加に対し、実行時間がどれくらい増加するかの割合で表した指標。
- 時間計算量
  - 処理時間
- 空間計算量
  - メモリ使用量

それぞれ計算時間を記述するものだが、学術的な意味の違いについてまとめる。

アルゴリズムの実行時間を表す3パターンについてまとめる。

最善（best）ケース
- 計算量の下限。すべての要素の値が等しいケース。最悪ケースや期待ケースと値が大きくかけ離れ、大抵はO(₁)で実行できてしまうようなケースになるため、あまり議論されない。
最悪（worst）ケース
- 計算量の上限。
期待（average）ケース
- 計算量の平均。要素の値が平均的なケース。

多くのアルゴリズムでは、最悪ケースと期待ケースは同じになるようなことが多い。　

処理時間が短い順に代表的なものをまとめる。

O記法	計算理論における名称	概要
O(₁)	定数時間	データ量が増加しても処理時間が増加しない
O(log n)	対数時間	データ量が増えても計算時間がほとんど増えない。増えても計算量の増え幅は小さくなる。
O(n)	線形時間	データ量が増加した分だけ処理時間が増える
O(n log n)	準線形、線形対数時間	O(n)よりやや重い程度
O(n²)	二乗時間	要素から全ての組み合わせペアについて調べるような処理。データ量が増えるほど計算量の増え幅が大きくなる
O(n³)	多項式時間	三重ループ
O(kⁿ)	指数時間	要素から全ての組み合わせを取得するような処理
O(n!)	階乗時間	nの階乗に比例した時間がかかる

ステップ数を計算して、その合計を元に計算量を求める。計算量を求める際に、以下の二点は重要度が低いため、省略する。

ステップの計算で処理の実行時間を足すか掛けるかは、それぞれの処理が同時に起きるか、起きないかで考える。

同時に起きない場合は実行時間を足すケース。

同時に起きる場合は、実行時間を掛けるケース。

上記のコードの場合、ステップ数の合計は1+1+n+1=3nとなる。係数は除くので、計算量はO(n)となる。

上記の場合は、1+1+n²=2n²のステップ数となるので、計算量は係数を除き、O(n²)となる。

nが1の時ループ回数 1

nが4の時ループ回数 2

nが8の時ループ回数 3

ループ回数はlog2ⁿで求められる。 1+log2ⁿのステップ数となるので、諸々を省略して計算量はlog nととなる。