ビッグオー(Big O)記法 | 時間計算量、空間計算量

時間計算量、空間計算量

時間計算量

時間計算量は、ソースコードロジックの実行時間(Execution Time)を予測し、どれほど効率的なコードかを表す概念である。実行時間は演算(Operation)に比例して長くなる。CPU使用量と関係がある。

空間計算量

空間計算量は、コードがメモリ空間をどれほど効率的に使うかに関する概念である。静的配列やハッシュテーブルのように、あらかじめ空間を確保するデータ構造でよく登場する概念である。RAM使用量と関係がある。

ソースコードロジックはまず動作しなければならないが、動作だけでなく時間・空間計算量を計算することで、どれほど効率的なコードかが判断される。

ビッグオー(Big O)記法とは

ビッグオー(Big-O)は、時間・空間計算量を数学的に表す代表的な方法である。ただし、コードの実際の実行時間を示すものではなく、入力データの増加率に応じたアルゴリズム性能を論理的に予測するために使う。ビッグオー記法には次の2つの規則がある。

最も高い次数だけを残す。

O(n² + 2n) -> O(n²)

係数と定数は大胆に捨てる。

O(4n + 5) -> O(n)

ビッグオー記法で時間計算量を区分する

O(1) (Constant)

入力データの大きさに関係なく、常に一定時間かかるアルゴリズムを表す。データが増えても性能にはほとんど影響しない。

O(log₂ n) (Logarithmic)

入力データの大きさが大きくなるほど、処理時間がログ(log: 指数関数の逆関数)分だけ増えるアルゴリズムである。例えばデータが10倍になると、処理時間は2倍になる。二分探索が代表的であり、再帰が有効に働く場合も該当する。

O(n) (Linear)

入力データの大きさに比例して処理時間が増加するアルゴリズムである。例えばデータが10倍になると、処理時間も10倍になる。線形探索アルゴリズムが代表的である。

O(n log₂ n) (Linear-Logarithmic)

データが多くなるほど、処理時間がログ(log)倍だけさらに増えるアルゴリズムである。例えばデータが10倍になると、処理時間は約20倍になる。ソートアルゴリズムであるMerge sort、Quick sortの平均時間計算量である。

O(n²) (Quadratic)

データが多くなるほど、処理時間が急激に増えるアルゴリズムである。例えばデータが10倍になると、処理時間は最大100倍になる。二重ループ(n² matrix)が代表的である。ただし、mがnより小さい場合は、必ずO(nm)と表記するのが望ましい。

O(2ⁿ) (Exponential)

データ量が多くなるほど、処理時間が幾何級数的に増えるアルゴリズムである。代表的にはフィボナッチ数列があり、再帰が逆効果になる場合も該当する。

時間計算量の計算方法

命令が終わるたびに実行回数を書いてみる。

基本計算方法

public static void basic() {
    int[] a = {7, 3, 6, 3, 3, 5, 6, 9};          // 1
    for (int i = 0; i < a.length - 1; i++) {     // n             [i > 0 to n-1 : n times called]
        for (int j = i + 1; j < a.length; j++) { // (n-1) * n     [j > 1 to n   : n times called]
            if (a[i] == a[j]) {                  // (n-1) * (n-1) [if文は結局n-1回だけ実行]
                a[j] = 0;
            }
        }
    }

    for (int i : a) {
        System.out.println(i);
    }
}

命令語の実行回数をすべて足すと2n²-2n+2となる。定数を省略し、最高次項だけを考えるとO(n²)と表記される。

再帰関数の時間計算量の計算方法

public static int factorial(int n) {
    System.out.println("n:" + n);
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

再帰呼び出しは以下のようにn回呼び出される。したがってO(n)と表記される。

factorial(n) -> factorial(n -1) .... ->factorial(2) -> factorial(1)