時間計算量と空間計算量

• 時間計算量(time complexity): アルゴリズムの実行時間
• 空間計算量(space complexity): アルゴリズムに要求されるメモリの量

計算量の表記法

• O 表記法(big-O notation):計算時間の上限を表す
  • n 個の要素を持つ配列のすべての要素を出力する時間計算量は $O(n)$ と記述できるが $O(2n)$, $O(n^2)$ と表記することも可能
  • n 個の要素を持つ配列のすべての要素を出力する時間計算量は $O(1)$ を超える例があることから $O(1)$ とは記述できない
• Ω 表記法(omega notation): 計算時間の下限を表す
  • n 個の要素を持つ配列のすべての要素を出力する時間計算量は $O(n)$ と記述できるが $O(1)$, $O(log(n))$ と表記することも可能
  • n 個の要素を持つ配列のすべての要素を出力する時間計算量は $O(n^2)$ を下回る例があることから $O(n^2)$ とは記述できない
• Θ 表記法(theta notation): ある計算について $O = Ω$ なるオーダーが存在するとき、これを $Θ$ と表記できる
  • n 個の要素を持つ配列のすべての要素を出力する時間計算量は $O(n)$ かつ $Ω(n)$ であるため、この時間計算量は $Θ(n)$ と記述できる
  • ソフトウェア開発の文脈では慣例的に O 表記法を Ω 表記法のような意味で利用することが多い

計算量の分類

• 最悪時計算量(best case vomplexity): 最も時間を要する入力を与えた場合の計算量
• 最良（最善）時計算量(worst case complexity): 最も時間を要しない入力を与えた場合の計算量
• 平均時計算量(average case complexity): 入力がランダムに与えられたと仮定した場合の平均的な計算量

計算量の比較

償却計算量（ならし解析）

1. $O(1)$:確保された 1 要素分のメモリに書き込み
2. $O(n)$: 確保された 1 要素分のメモリに不足が生じたので 2 要素分のメモリを確保し既存の n 個の要素をコピー
3. $O(n)$: 確保された 2 要素分のメモリに不足が生じたので 4 要素分のメモリを確保し既存の n 個の要素をコピー
4. $O(1)$: 確保された 4 要素分のメモリに書き込み
5. $O(n)$: 確保された 4 要素分のメモリに不足が生じたので 8 要素分のメモリを確保し既存の n 個の要素をコピー
6. $O(1)$: 確保された 8 要素分のメモリに書き込み
7. $O(1)$: 確保された 8 要素分のメモリに書き込み
8. $O(1)$: 確保された 8 要素分のメモリに書き込み
9. $O(n)$: 確保された 16 要素分のメモリに不足が生じたので 16 要素分のメモリを確保し既存の n 個の要素をコピー
10. $O(1)$: 確保された 16 要素分のメモリに書き込み
11. $O(1)$: 確保された 16 要素分のメモリに書き込み
12. $O(1)$: 確保された 16 要素分のメモリに書き込み

時間計算量の具体例

ループの時間計算量

for (int i = 0; i < n, i++) {
  doSomething()
}

for (int i = 0; i < n, i++) {
  for (int j = 0; j < n; j++ ) {
    doSomething()
  }
}

連続文の時間計算量

for (int i = 0; i < n, i++) {
  doSomething()
}

for (int j = 0; j < n, j++) {
  doSomething2()
}

if 文の時間計算量

if (condition) {
  doOrderN()
} else {
  doOrderNLogN()
}

再帰の時間計算量

int f(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + f(n - 1);
}

int f(int n) {
    if (n <= 0) {
        return 0;
    }
    return f(n - 1) + f(n - 1);
}

やや複雑な計算量となるアルゴリズムの実例

log (n) の計算量

for (int i = 1; i <= n, i = i * 2) {
  doSomething()
}

int as[] = {1, 3, 6, 9, 13, 23, 31, 35, 40, 43};

int find(int input[], int target, int startIndex, int endIndex) {
    int n = (startIndex + endIndex) / 2;
    int extracted = input[n];
    if (extracted == target) {
        return n;
    } else if (extracted > target) {
        return n == endIndex ? -1 : find(input, target, startIndex, n);
    } else {
        return n == startIndex ? -1 : find(input, target, n, endIndex);
    }
}

n log (n) の計算量

参考文献

1. 入門データ構造とアルゴリズム
2. 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~
3. できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事
4. 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜