【アルゴリズム性能評価】Big O(オーダー)記法をやさしく解説

こんにちは。iQeda [@iQeeeda] です。

これからアルゴリズム性能を記述する Big O 記法について解説します。

Big O 記法を理解していなければアルゴリズム開発に苦労しますし、
ちゃんとしたテック企業のエンジニアは知ってて当然レベルの知識なので必ず押さえましょう。

ひらすら練習問題を解きたい人はこちらの記事。

計算量オーダーについて

時間計算量とは

時間計算量とは「物理的にかかる時間」を表します。
プログラムの実行時間・ファイルの転送時間という解釈で大丈夫です。

空間計算量とは

空間計算量とは「アルゴリズムを実行するのに必要なメモリ・スタック量」を表します。

Big O 記法とは [オーダー記法]

時間計算量でも、空間計算量でも、なにかしらのアルゴリズム性能を表すとき「Big O (ビッグ・オー) 記法」というもので「計算量の割合」を表現します。
ここでは「時間計算量」における Big O 記法の説明をします。

後述しますが Big θ (ビッグ・シータ) 記法というものもあって、
IT 業界では Big O 記法は「 Big θ 記法の意味で使われることが多い」点に気をつけて下さい。

上限以上の値を設定しても構わない

A さんの年齢は x 才で、130 才以上生きる人間は存在しない

計算量の話ですが、人間の年齢にたとえて説明します。
命題「 A さんの年齢は x 歳で、130 歳以上生きる人間は存在しない」があるとします。

このとき A さんの年齢は x <= 130 になるので「O(130)」と上限値を設定します。
しかし Big O 記法では x <= 1000000 でも x <= 10000000000 でも構わないものとします。
※ なぜなら x が 130 才以下なのは確実だから

なので「O(1000000) 」も「O(10000000000) 」も認められます。

表現される性能 [オーダー] の種類

Big O で表現される計算量には様々な種類があり「オーダー」と呼びます。
そんなオーダーの一例を紹介します。

最悪、時間計算量が O(N) を超えないアルゴリズムを書くようにしましょう。

O(1)

function log(arr) {
    // 特定の要素にしかアクセスしない
    console.log(array[0]);
    console.log(array[1]);
}

log([1, 2, 3, 4]);
log([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

O(N)

function logAll(array) {
    for (let i = 0; i < array.length; i++) {
        // 全ての要素にアクセスする
        console.log(array[i]);
    }
}

logAll([1, 2, 3, 4, 5]);
logAll([1, 2, 3, 4, 5, 6]);
logAll([1, 2, 3, 4, 5, 6, 7]);

O(N^2)

function addAndLog(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = 0; j < array.length; j++) {
          console.log(array[i] + array[j]);
        }
    }
}
// 9 パターンの組み合わせを表示: 3^2
addAndLog(["A", "B", "C"]);

// 16 パターンの組み合わせを表示: 4^2
addAndLog(["A", "B", "C", "D"]);

// 25 パターンの組み合わせを表示: 5^2
addAndLog(["A", "B", "C", "D", "E"]);

O(logN)

// 二分探索
function binarySearch(array, key) {
    var low = 0;
    var high = array.length - 1;
    var mid;
    var element;

    while (low <= high) {
        mid = Math.floor((low + high) / 2, 10);
        element = array[mid];
        if (element < key) {
            low = mid + 1;
        } else if (element > key) {
            high = mid - 1;
        } else {
           return mid;
        }
    }
    return -1;
}

// 第一引数の配列から、第二引数の値のインデックスを発見する
console.log(binarySearch([1, 2, 3, 4, 5, 6], 3));

二分探索について

Big Ω 記法とは

「Big Ω (ビッグ・オメガ) 記法」というものもあります。

下限以下の値を設定しても構わない

A さんの年齢は x 才で、0 才以下の人間は存在しない

また計算量の話ですが、人間の年齢にたとえて説明します。
命題「 A さんの年齢は x 歳で、0 歳以下の人間は存在しない」があるとします。

このとき A さんの年齢は 0 <= x になるので「Ω(0)」と下限値を設定します。
しかし Big Ω 記法では -1 <= x でも -1000000 <= x でも構わないものとします。
※ なぜなら x が 0 才以上なのは確実だから

なので「Ω(-1) 」も「Ω(-1000000) 」も認められます。

Big θ 記法とは

最後に「Big θ (ビッグ・シータ) 記法」を紹介します。
Big O 記法はしばしば「Big θ 記法の意味で使われる」ので注意してください。

下限と上限を厳密に定義するのですね。

アルゴリズム実行時間の表現

アルゴリズムの実行時間は以下 3 つのケースがあります。

今回は「クイックソート」という順番を入れ替えるアルゴリズムを例に説明します。
クイックソートの説明は以下リンク先がわかりやすいので紹介しておきます。

ざっくりクイックソートの説明をしておきます。

最善ケースとは

配列要素すべての値が等しい場合、クイックソートの走査は一回で済みます。
これを「最善ケース」とします。

最善ケースを試したいだけなら O(1) のオーダーで十分なので、あまり議論されません。

最悪ケースとは

配列 0 番目の要素が必ずピボットとして選ばれる仕様、かつ、
配列要素の値がすべて降順になっていた場合を「最悪ケース」とします。

最も大きい値をピボットとして選び続けてしまうので、非効率なグループ作成ばかりしてしまいます。

期待ケースとは

最善でも最悪でもない、よくあるパターンを「期待ケース」とします。

空間計算量における Big O 記法

Big O 記法で PC メモリ領域・スタック領域を表すとき、以下のルールに従います。

再帰的な呼び出しを行うときの注意点

再帰的な呼び出しを行うとき、スタック領域に注意してください。

O(n) のメモリ領域が必要になる例

下記の例だと、メモリ領域が O(4) 以上じゃないと実行できません。
sum(10000) だとメモリ領域が O(10000) 以上必要です。注意しましょう。

/* 
 * O(n) の実行時間が必要
 * O(n) のメモリ領域が必要
 */

int sum(int n) {
    if (n <= 0) {
        return 0;
    }
    // 再帰的に sum() を O(n) 回呼び出して return する
    // O(n) の空間計算量になる
    return n + sum(n - 1);
}

// 実行
sum(4);

/*
 * sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0)
 * ...と、呼び出されるごとにコールスタックに積まれてメモリを消費する
 */ 

O(1) のメモリ領域で済む例

下記の例だと、メモリ領域が O(1) で実行できます。
実行時間が O(n) だからといって、メモリ領域も O(n) 必要になるとは限らないのです。

/*
 * O(n) の実行時間が必要
 * O(1) のメモリ領域だけでよい
 */

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        // ループ処理で pairSum() を O(n) 回呼び出す
        // しかしコールスタック上に同時に存在させていないので、空間計算量は都度 O(1) でよい
        sum += pairSum(i, i + 1);
    }
    return sum; 
}

int pairSum(int a, int b) {
    return a + b;
}

// 実行
pairSumSequence(4);

CS シリーズ

次回

前回

参考