【Big O】オーダー記法「実行時間」の頻出問題を解説【28問】

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

基本の 16 問

O(N)

例1

void foo(int[] array) {
    int sum = 0;
    int product = 1;

    for (int i = 0; i < array.length; i++) {
        sum += array[i];
    }

    for (int i = 0; i < array.length; i++) {
        product *= array[i];
    }

    System.out.println(sum + ", " + product);
}

ループを使って配列を 2 回走査していますが、何も問題になりません。
実行時間は O(N) です。

O(N^2)

例2

void printPairs(int[] array) {
    // 外側のループは「内側のループを N 回繰り返す」
    for (int i = 0; i < array.length; i++) {
        // 内側のオーダーは O(N)
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

内側ループのオーダー O(N) が外側のループで N 回繰り返されるので実行時間は O(N^2) です。

またループで生成される i と j の値を使って、配列内にある 2 つの要素の組をすべて表示しています。
そのパターンは O(N^2) あるので、実行時間も O(N^2) …という考え方もできます。

例3

void printUnorderedPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        /*
         * j = i + 1 からはじまる
         * 初回は N - 1 回実行 / 二回目は N - 2 回実行 / 三回目は N - 3 回実行 / ... / 3 回実行 / 2 回実行 / 1 回実行
         * → 1 から N - 1 までの和は N(N - 1) / 2
         * → 実行時間は O(N^2)
         */ 
        for (int j = i + 1; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

「ループ処理の回数」で考える

二重ループの処理回数から実行時間を考えてみましょう。

全体を 2 倍して「N – 1 と 1, N – 2 と 2, N – 3 と 3 …」 とペアを作るとします。
すると、数字 N を N – 1 ペアつくることができます。

全体を 2 倍したので 1/2 して戻してあげると N(N - 1) / 2 となります。

そして定数を切り捨てると、実行時間は O(N^2) と考えることができます。
この「整数の和の求め方」は以下の記事で詳しく説明しているので参考にしてみてください。

「コードの意味」で考える

ループ生成される j は常に i よりも大きい状態で (i, j) の組を出力します。
N = 8 のとき、(i, j) は以下のように出力されます。

これは N * N 行列の半分になっているので N^2 / 2 といえます。
従って実行時間は O(N^2) です。

「ループ処理の回数の平均」で考える

外側のループ処理の回数は N 回です。
内側のループ処理の回数は変動します。

しかし、内側のループ処理の平均回数を考えることはできます。

たとえば 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 の平均値は 10/2 で 5 です。
なので N だったら、その平均値は N/2 になります。

外側のループ処理の回数が N 回、内側のループ処理の平均回数が N/2 であるなら、
全体のループ処理の回数は N^2/2 なので、実行時間は O(N^2) といえます。

O(1)

例4-1

以下は二重ループになっているので O(N^2) とよく勘違いしてしまうのですが、
if 文を考慮すると O(1) になります。

// 配列 2 つを引数にとる -> 2 つの配列は異なるデータ
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
    for (int i = 0; i < arrayA.length; i++) {
        for (int j = 0; j < arrayB.length; j++) {
            // この if 文は定数時間で実行しているので O(1)
            if (arrayA[i] < arrayB[j]) {
                System.out.println(arrayA[i] + ", " + arrayB[j]);
            }
        }
    }
}

O(ab)

例4-2

例4-1のコードを以下のように書き換えました。
あらためて実行時間がどうなるのか考えてみましょう。

// 配列 2 つを引数にとる -> 2 つの配列は異なるデータ
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
    for (int i = 0; i < arrayA.length; i++) {
        /* 
         * 内側のループは配列 B の長さだけ、配列 A の各要素に対する処理を行う
         */
        for (int j = 0; j < arrayB.length; j++) {
            /* 実行時間 O(1) */
        }
    }
}

配列 A の長さが a で、配列 B の長さが b とするなら、その実行時間は O(ab) となります。
関連性のないデータは a と b のように区別する必要があるのです。

例5

void printUnorderedPairs(int[] arrayA, int[] arrayB) {
    for (int i = 0; i < arrayA.length; i++) {
        for (int j = 0; j < arrayB.length; j++) {
            // 100000 回ループする
            for (int k = 0; k < 100000; k++) {
                System.out.println(arrayA[i] + ", " + arrayB[j]);
            }
        }
    }
}

100000 回のループも結局は定数です。例4-2 と同じく O(ab) となります。

O(N)

例6

以下は配列を逆順に並べかえるアルゴリズムです。

void reverse(int[] array) {
    // 並べかえるには、配列サイズの半分だけループすればよい
    for (int i = 0; i < array.length / 2; i++) {
        int other = array.length - i - 1;
        int temp = array[i];
        array[i] = array[other];
        array[other] = temp;
    }
}

配列サイズの半分をループ処理していますが、特にそれは問題にならず O(N) になります。

例7

以下のうち O(N) と同等になるのはどれでしょうか？

答え

O(a * s(log a + log s)): 論理的な名前をつける

例8

各要素の文字列をソートし、その後、配列全体もソートするアルゴリズムがあるとします。

誤った実行時間

上記は誤りとなります。

なぜなら N が「文字列の長さ・配列の長さ」で 2 種類の使い方がされており、
全く区別されていないからです。

N を使うことで曖昧さが残らないようにしたり、
N をまったく使わないようにするなど配慮が必要です。

O(a^2) と O(ab) では意味がまったく違うことを意識しましょう。

正しい実行時間

改めて N の代わりに、論理的な名前で文字の定義をします。

O(N): 平衡二分探索木

例9

// 平衡二分探索木における、全ノードの値を合計する
int sum(Node node) {
    if (node == null) {
        return 0;
    }
    // 再帰実行
    return sum(node.left) + node.value + sum(node.right);
}

「コードの意味」で考える

木構造の各ノードに 1 回ずつ訪れているので、計算量は定数時間になります。

よって実行時間はノードの数に比例します。
ノードが N 個なら O(N) が実行時間になります。

「再帰」で考える

一般的に、複数の枝をもつ再帰関数の実行時間は O(枝の本数^深さ) になります。
ここでは left / right の 2 本の枝を使っているので O(2^深さ) になります。

実行時間 O(2^深さ) はパッと見、すごく効率の悪いアルゴリズムに見えてしまうかもしれません。
これは「指数関数」のアルゴリズムですが、実際はそこまで悪い計算時間じゃありません。

平衡二分探索木の深さは「log N」なので O(2^log N) になるからです。

2^P を対数にすると…

2^log N を対数にすると…

ノード数を N とすると、実行時間は O(N) になることがわかります。

O(√N)

例10

// 素数かどうか判定する
boolean isPrime(int n) {
    /*
     * x * x <= n
     * ループを回すのは n の平方根までで十分ということ
     * ※ n の平方根より大きな数で割れる場合があったとしても、必ずそれより小さな数で割ることができるため
     */ 
    for (int x = 2; x * x <= n; x++) {
        // ターゲットより小さい数 x で割り切れた場合、素数ではない
        if (n % x == 0) {
            return false;
        }
        return true;
    }
}

isPrime(33); // false
/*
 * たとえば 33 / 11 = 3 になります。
 * 11 は 33 の平方根より大きい数ですが、それより先に 33 / 3 = 11 が検証されて false が返却されます
 * よって isPrime 内で 11 まで試し割りする必要はなく、ループを回すのは 33 の平方根 √33 (5.74...) までで十分です
 */

素数かどうか判定する関数です。
ループ処理は定数時間になっています。

最悪ケース (for文を最後まで回すケース) は「x が n の平方根に達した場合」となっています。
数式にすると x = √n ですね。

for 文の終了条件は以下のように書き換えることが可能です。

boolean isPrime(int n) {
    // x <= sqrt(n)
    // x が n の平方根に達した場合
    for (int x = 2; x <= sqrt(n); x++) {
        if (n % x == 0) {
            return false;
        }
        return true;
    }
}

最悪ケースから判断して、実行時間は O(√n) ということになります。

O(N): 階乗

例11

// 階乗の計算をする
int factorial(int n) {
    if (n < 0) {
        return -1;
    } else if (n == 0) {
        return 1;
    } else {
        // 再帰実行
        return n * factorial(n - 1);
    }
}

引数が n, n – 1, … , 2, 1 と減少しながら再帰実行しています。
ただそれだけなので O(n) になります。

O(N^2 * N!)

例12

void permutation(String str) {
    permutation(str, "")
}

// 受け取った文字列から得られる「置換の総数」をすべて表示する
void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.prontln(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            // 再帰実行
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

「関数は全部で何回呼ばれるか」で考える

順序を考えて並べた総数 (置換の総数) はいくつになるか、考えてみましょう。
引数に 7 文字を渡した場合だと、順列は 7 * 6 * 5 * 4 * 3 * 2 * 1 通り存在します。

1 文字目は 7 通り、2 文字目は 6 通り、3 文字目は 5 通り … の候補になっていくからです。

これは 7! の階乗と言い換えることもできるので、n 文字だったら n! 通りになるわけです。
よって関数は n! 呼ばれることになります。

なお、以下の記事では「順序」を詳しく解説しているので参考にしてみてください。

「関数は途中で何回呼ばれるか」で考える

再帰に加えて、for 文のループ処理が加わります。
そこで関数は n * n! 回実行されます。

「個々の関数の呼び出しはどれくらい時間がかかるか」で考える

System.out.prontln(prefix); の実行時間は O(n) です。

String rem = str.substring(0, i) + str.substring(i + 1); と、
permutation(rem, prefix + str.charAt(i)); を合わせた実行時間も O(n) です。

rem, prefix, str.charAt(i) の合計は常に n です。
よって関数の呼び出し自体の実行時間は O(n) です。

「合計の実行時間」で考える

permutation 関数は O(n * n!) 回呼び出され、呼び出し毎に O(n) の時間を要します。
よって合計時間は O(n^2 * n!) を超えることはありません。

O(2^n): フィボナッチ数列

例13

フィボナッチ数列とは 1, 1, 2, 3, 5, 8, 13, 21 … のように、
2 つ前の値と 1 つ前の値を足すとその数になり、ずっとそれが成立する数列です。

以下のサイトが説明がわかりやすいと思います。

そんなフィボナッチ数を求めるアルゴリズムの時間計算量はいくらでしょうか。

// n 番目のフィボナッチ数を求める
int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    // 再帰実行
    return fib(n - 1) + fib(n - 2);

}

再帰なので O(枝の本数^深さ) で OK です。
呼び出しごとに 2 つの枝ができるので、深さ N のとき O(2^N) になります。

通常、複数の再帰呼び出しがあるアルゴリズムの実行時間は「指数時間」になります。

例14

// 0 から n 番目までのフィボナッチ数を表示する
int allFib(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i + ": " + fib(i));
    }
}

int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    // 再帰実行
    return fib(n - 1) + fib(n - 2);

}

fib(n) が O(2^n) であれば、
allFib(n) は O(n2^n) になると思うかもしれません。

しかし、合計の実行回数 (ノード数) は n によって変化していきます。

合計の実行回数が 2^n+1 – 1 ということは、
fib(n) と同じく allFib(n) も O(2^n) ということになります。

O(N): メモ化を使ったフィボナッチ数列

以下ソースコードは「メモ化」と呼ばれる方法を使って、
指数時間の再帰アルゴリズムを最適化しています。

// 0 から n 番目までのフィボナッチ数を表示する
// 計算したフィボナッチ数はキャッシュ保存して、それを参照しながら n 番目まで計算する
int allFib(int n) {
    int[] memo = new int[n + 1];
    for (int i = 0; i < n; i++) {
        System.out.println(i + ": " + fib(i, memo));
    }
}

int fib(int n, int[] memo) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else if (memo[n] > 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

fib(i) が呼ばれるたびに、fib(i – 1) と fib(i – 2) が呼び出れますが、
それらの計算結果はすでにキャッシュされているので、参照して足し算するだけです。

キャッシュ保存・参照を利用すれば、定数時間で計算できることになります。
定数時間の処理を N 回おこなうと、実行時間は O(N) になります。

O(log N)

例16

// 1 から n の範囲内の 2 のべき乗の値を表示する
int powersOf2(int n) {
    if (n < 1) {
        return 0;
    } else if (n == 1) {
        System.out.println(1);
        return 1;
    } else {
        // 再帰実行
        int prev = powerOf2(n / 2)
        int curr = prev * 2;
        System.out.println(curr);
        return curr;
    }
}

たとえば n = 50 を渡すと n = 1 になるまで 2 で割り続けます。
n = 1 になると関数の呼び出しが止まって、そこから結果を返却していきます。

これは n を 1/2 にしていくので、実行時間は O(log N) になります。

「コードの意味」で考える

powersOf2 を呼び出すごとに、1 つの値が出力されて呼び出し元に戻ります。
6 個の数が出力されたのであれば、powersOf2 が 6 回呼び出されたことを意味します。

1 から 50 の範囲内の値をもつ 2 のべき乗は 2^0, 2^1, 2^2, 2^3, 2^4, 2^5 の 6 個です。
なので powersOf2 は 6 回呼び出されます。

1 から n の範囲内の値をもつ 2 のべき乗は log n 個です。
なので powersOf2 は log n 回呼び出されます。

よって実行時間は O(log N) となります。

「増加率」で考える

n が大きくなると、実行時間はどれだけ変化するか「増加率」に注目してみましょう。

powersOf2 は「 2 のべき乗の値を返却する関数」なので、
n が 2^x の値を超えると呼び出し回数が 1 ずつ増えていきます。

上記 n の値が呼び出し回数が増えるタイミングということです。

n = 2 から n = 3 に変わるだけでは、呼び出し数は変化しませんが、
n = 2 から n = 4 に変わると、呼び出し数は 1 増えます。

n = 2^x の x は log n です。
この x の増加率に呼び出し回数は依存しているので、実行時間は O(log n) となります。

練習の 12 問

O(b)

練習1

// a と b の積を計算する
int product(int a, int b) {
    int sum = 0;
    for (int i = 0; i < b; i++) {
        sum += a;
    }
    return sum;
}

for 文のループを b 回繰り返しているので、実行時間は O(b) です。

練習2

// a の b 乗の計算
int power(int a, int b) {
    // エラー
    if (b < 0) {
        return 0;
    } else if (b == 0) {
        return 1;
    } else {
        // 再帰実行
        return a * power(a, b - 1);
    }
}

a の b 乗の計算です。
再帰的に関数を b 回呼び出すので、実行時間は O(b) となります。

O(1)

練習3

// 余り算 a % b
int mod(int a, int b) {
    if (b <= 0) {
        return -1
    }
    int div = a / b;
    return a - div * b;
}

余り算のアルゴリズムです。実行時間は O(1) つまり定数時間です。

O(a/b)

練習4

// 整数の割り算 ※ a と b は正の値
int div(int a, int b) {
    int count = 0;
    int sum = b;
    while (sum <= a) {
        sum += b;
        count++;
    }
    // count は a/b に等しい
    return count;
}

while 文のループ回数は count で管理しています。
count は a/b と等しいので、実行時間は O(a/b) です。

O(log N)

練習5

// 整数値の平方根を返却する
int sqrt(int n) {
    return sqrt_helper(n, 1, n);
}

int sqrt_helper(int n, int min, int max) {
    // 平方根ではない場合 (平方根が整数値じゃない場合)
    // n が 2 乗の数でなければ -1 を返す
    if (max < min) return -1;

    // 例えば n が 100 の場合、最初は 50 から試す
    // 値が大きすぎた場合、次は 1 と 50 の間の 25 を試す
    int guess = (min + max) / 2;

    // 発見 
    if (guess * guess == n) {
        return guess;
    // 小さすぎる
    } else if (guess * guess < n) {
        // 再帰実行 ※ もっと大きい値で試す
        return sqrt_helper(n, guess + 1, max);
    // 大きすぎる
    } else {
        // 再帰実行 ※ もっと小さい値で試す
        return sqrt_helper(n, min, guess + 1);
    }
}

平方根を求めるために二分探索を行っています。実行時間は O(log n) です。

O(sqrt(N))

練習6

// 平方根ではない場合 (平方根が整数値じゃない場合)
// n が 2 乗の数でなければ -1 を返す (平方根が整数値じゃない)
int sqrt(int n) {
    // 1 から順番に値を増やして、一致する値があるか調べる
    for (int guess = 1; guess * guess <= n; guess++) {
        if (guess * guess == n) {
            return guess;
        }
    }
    return -1;
}

for 文は guess * guess > n になると終了します。言い換えると guess > sqrt(n) です。
よって実行時間は O(sqrt(n)) です。

O(N)

練習7

要素を見つけるのにかかる最大の時間は「木の深さ」で決まります。
木のノード数を n とすると、深さ n の直線的なリスト状態が考えられます。

実行時間は O(n) になります。

練習8

順序の性質が何もないので、すべてのノードを探索しないといけません。
よって実行時間は O(n) になります。

O(N^2)

練習9

int[] copyArray(int[] array) {
    int[] copy = new int[0];
    for (int value : array) {
        copy = appendToNew(copy, value);
    }
    return copy;
}

/*
 * 新たに大きいサイズの配列を作り、値を追加して、その配列を返却する
 */
int[] appendToNew(int[] array, int value) {
    // すべての要素を新しい配列にコピー
    int[] bigger = new int[array.lenght + 1];
    for (int i = 0; i < array.length; i++) {
        bigger[i] = array[i];
    }

    // 新しい要素を追加
    bigger[bigger.length - 1] = value;
    return bigger;
}

copyArray() は繰り返し appendToNew() を呼び出します。
配列のコピーを行うのにどれくらい時間がかかるでしょう。

appendToNew() を最初に呼び出すと 1 回のコピーが生じます。
2 回目の呼び出しでは 2 回のコピーが生じます。
3 回目の呼び出しでは 3 回のコピーが生じます。

配列の要素数を n とすると、合計のコピー回数は 1 から n までの和となりますので、
実行時間は O(n^2) となります。

O(log N)

練習10

// 各位の値を足し算する
int sumDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

実行時間は値の桁数に依存します。

d 桁の値であれば、10^d までになります。
n = 10^d の場合は d = log n となります。

よって実行時間は O(log n) となります。

O(kc^k)

練習11

int numChars = 26;

/*
 * 長さ k の文字列の中で、ソートされた文字すべてを表示する
 */
void printSortedStrings(int remaining) {
    printSortedStrings(remaining, "");
}

/*
 * 長さ k の文字列をすべて生成し、文字がソートされているかどうかチェックする
 */
void printSortedStrings(int remaining, String prefix) {
    if (remaining == 0) {
        if (isInOrder(prefix)) {
            System.out.println(prefix);
        }
    } else {
        for (int i = 0; i < numChars; i++) {
            char c = ithLetter(i);
            // 再帰実行
            printSortedStrings(remaining - 1, prefix + c);
        }
    }
}

boolean isInOrder(String s) {
    for (int i = 1; i < s.length(); i++) {
        int prev = ithLetter(s.charAt(i - 1));
        int curr = ithLetter(s.charAt(i));
        if (prev > curr) {
            return false;
        }
    }
    return true;
}

char ithLetter(int i) {
    return (char) (((int) 'a') + i);
}

文字列の長さが k で、文字の数を c とすると、
文字列の生成に O(c^k) の時間を要し、ひとつの文字列のソートチェックに O(k) かかります。

よって実行時間は O(kc^k) となります。

O(b log b + a log b)

練習12

/*
 * 2 つの配列の共通する値を数える ※ a と b は全く同じではない配列
 */
int intersection(int[] a, int[] b) {
    // b をソートする
    mergesort(b);
    int intersect = 0;

    // a の要素を順番に、配列 b に含まれるかどうか調べる
    for (int x : a) {
        // 二分探索を使う
        if (binarySearch(b, x) >= 0) {
            intersect++;
        }
    }
    return intersect;
}

配列 b のソートの実行時間は O(b log b) です。

そのあと配列 a の各要素を O(log b) で二分探索しますが、
すべての要素を調べると O(a log b) となります。

よって実行時間は O(b log b + a log b) となります。

CS シリーズ

次回

前回