O(オーダー)記法とアルゴリズムの計算量の求め方

O記法

概要

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

計算量(オーダー)とは

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

Big O/Big θ/Big Ω

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

  • Big O
    • 計算時間の上限
  • Big θ
    • 計算時間の下限
  • Big Ω
    • OとΩの両方

最善/最悪/期待ケース

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

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

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

O(オーダー)記法

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

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

計算量の求め方

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

  • 最大次数項以外を省略する
    • O(n²+n)
      • O(n²)とする
  • 係数を省略する
    • O(2n)
      • O(n)とする

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

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

for (condition) {
  // do something
}

for (condition) {
  // do something
}

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

for (condition) {
  for (condition) {
    // do something
  }
}

リニアサーチ

const targetData = 4; // 1回実行
const data = [1, 2, 3, 4, 5]; // 1回実行

for (let i = 0; i < data.length; i++) {
    if (targetData == data[i]) {
      console.log(`${i}番目でデータを発見した`); // data.length回実行される→n回実行
    return;
  }
}

console.log('目的のデータはない'); // 1回実行

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

for文の二重構造

const data = [1, 2, 3, 4, 5]; // 1回実行

for (let i = 0; i < data.length; i++) {
    console.log(`${i}回目の処理`); // 1回実行される
    for (let j = 0; j < data.length; j++) {
        console.log(j); // 4 * 4 回実行される→n²回実行
  }
}

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

計算量が対数を取るようなアルゴリズム

const n = 10;  // 1回実行される

for (let i = 0; i < n; i = i * 2) {
  console.log(i++); // log2ⁿ回実行される
}

nが1の時
ループ回数 1

nが4の時
ループ回数 2

nが8の時
ループ回数 3

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

参考リンク

参考書籍

About the author

Image

bmf san @bmf_san
A web developer in Japan.