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

O記法 アルゴリズム

アルゴリズム

2018-04-22 12:42:55

概要

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

計算量(オーダー)とは

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

O(オーダー)記法

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

※処理時間が短い順

まとめ

  • O(₁)
    • データ量が増加しても計算量が変わらない
  • O(log n)
    • データ量が増えれば計算量も増える
    • データ量が大きくなればなるほど計算量の増え幅は小さくなる
    • データ量が増えても計算量に大きな影響は出ない
  • O(n)
    • データ量が増えれば増えるほど計算量も増える
    • データ量が増えれば同じくらい計算量も増える
  • O(n²)
    • データ量が増えれば増えるほど計算量が増える
    • データ量が大きいほど計算量の増え幅は大きい

計算量の求め方

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

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

リニアサーチ

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.