こんにちわ、iimonでバックエンドを担当している玉山です。

今回は、設計、実装する上で案外知っていると便利なオーダーの紹介です。

オーダーの概念を知っていれば実装前にどのくらいのオーダーになるアルゴリズムを作らないといけないかが分かり実装の助けになったりします。

ここでは詳細は他のサイトに任せて、ふんわりとオーダーって何？みたいなのを解決することを目的としています。

オーダー（計算量）とは

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

時間計算量
- 処理時間
空間計算量
- メモリ使用量
一般に同じ問題を解決できるアルゴリズムは多数考えることができる
アルゴリズムによって所要時間が大きく変わる
良いアルゴリズムとは、解決したい問題の規模が大きくなっても対応できるようなもののことである

計算量の表現方法

Big O（O表記法）
- 計算時間の上限
Big θ（θ表記法）
- 計算時間の下限
Big Ω（Ω表記法）
- Oとθの両方

ここではよく使われるO表記法について説明していきます。

O（オーダー）記法

処理時間が短い順に代表的なものになります。

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

nは入力サイズになり、下記例で出てくるnがそれになります。

例：O(n)

for (int i = 0; i < n; ++i) {
    console.log("i: " + i)
}

例えば、線形探索や、九九の掛け算、偶数の出力といったアルゴリズムに使われます。

例：O(n²)

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        console.log("i: " + i, "j: " + j)
    }
}

例えば、単純な入れ替えるソートや二頂点間の最小距離を出すようなアルゴリズムに使われます。

例：O(n³)

for (int i = 0; i < n; ++i) 
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k) 
            console.log("i: " + i, "j: " + j, "k: " + k)

例えば、行列式の計算をするようなアルゴリズムに使われます。

実際のところ

O(n)や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となります。

また、オーダーを出す時は下記のような決まりがあります。

最高次数の項以外は落とす:

5n²+5n+100

→5n²
係数を無視する:

5n²

→n²

こうすることで概ねn²回に比例する計算時間を要するO(n²)のアルゴリズムであると考えます。

これは数式で表すと

となり5n²+5n+100は漸近的にn²に比例していて、比例係数が5だと言うことになります。

オーダーの使い方

計算量オーダーの概念を掴んだところで、実際の問題に対してアルゴリズムを設計するときの考え方について解説します。現実世界の問題では

実行時間の制限時間がどの程度か
解きたい問題のサイズnがどの程度の大きさか

がある程度決まっているケースが多いです。そうすると、どの程度の計算量オーダーのアルゴリズムを達成する必要があるのかを逆算できることになります。

参考

qiita.com

bmf-tech.com

iimon TECH BLOG

iimonエンジニアが得られた経験や知識を共有して世の中をイイモンにしていくためのブログです

オーダー(計算量)とは