時間計算量

「プログラムの実行に必要な計算のステップ数が入力に対してどのように変化するか」という指標を時間計算量といいます。 計算ステップ数とは、四則演算や数値の比較などの回数です。

空間計算量

「プログラムの実行に必要なメモリの量が入力に対してどのように変化するか」という指標を空間計算量といいます。

計算量の例

次のプログラムは1からNまでの総和(1+2+3+ \cdots +N)を計算するものです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int sum = 0;
  for (int i = 1; i <= N; i++) {
    sum += i;
  }
  cout << sum << endl;
}

このプログラムではfor文でN回の繰り返し処理を行っているので、計算ステップ数は入力のNに応じて変わります。 N回の繰り返しを行うので、計算ステップ数はおおよそN回になります。 このときの時間計算量は次で紹介するオーダー記法を用いてO(N)と表します。

このプログラムで使用している変数は入力のNに関わらずint Nとint sumとint iの3つです。 このときの空間計算量はオーダー記法を用いてO(1)と表します。

オーダー記法

厳密な計算ステップ数や必要な記憶領域の量は実装に用いるプログラミング言語や実装方法などによって変わるので、 計算量を厳密に見積もるのは大変です。

そこで時間計算量や空間計算量の表現として、オーダー記法 O(\cdot)が用いられることが多いです。

例えば、3 N^2 + 7N + 4という式はオーダー記法ではO(N ^ 2)と表されます。

以下の手順によってオーダー記法による表記を得ることができます。

• ステップ1：係数を省略する。ただし定数については1とする。
• ステップ2：Nを大きくしたときに一番影響が大きい項を取り出し、O(項)と書く。

  補足：N^2 + N + 1という式の場合「N^2」「N」「1」それぞれを項といいます。

「一番影響が大きい項」というのは、Nを大きくしていったときに「大きくなるスピードが最も速い項」と考えてください。 例えばNとN^2を比較すると、以下の表のようになるので3N^2の方が影響が大きいといえます。

3 N^2 + 7N + 4という式をオーダー記法で表す場合の手順以下の通りです。

• ステップ1：係数を省略してN^2 + N + 1とします。
• ステップ2：N^2 + N + 1で一番影響が大きい項はN^2なのでO(N^2)とします。

同じように2N + 10ならO(N)となります。

例題

次の式をそれぞれオーダー記法で表してください。

1. N + 100
2. 10N + N^3
3. 3 + 5
4. 2^N + N^2

   補足：2^N = \underbrace{2 \times 2 \times \cdots \times 2}_{N個}

答え

計算量(オーダー記法)の求め方

計算量を求めるには計算ステップ数がどうなるかを式で表す必要があります。

次のプログラムは意味の無いものですが、計算量がどうなるかを考えてみましょう。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  int sum = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      sum += i * j;
    }
  }

  for (int i = 0; i < N; i++) {
    sum += i;
  }

  for (int i = 0; i < N; i++) {
    sum *= i;
  }

  cout << sum << endl;
}

1つの2重ループと2つの1重ループがあるので計算ステップ数はN^2 + 2Nくらいになります。 これをオーダー記法で表すとO(N^2)となります。 よってこのプログラムの時間計算量はO(N^2)です。

このように、 簡単なアルゴリズムであれば厳密な式を求めなくても 「N回の繰り返し処理があるからO(N)」や「0からNまで回す2重ループがあるからO(N^2)」 などと見積もることができます。

例

いくつかの計算量オーダーについて、具体的なプログラムの例を挙げます。

O(1)

次のプログラムは、1からNまでの総和を公式を使って計算するものです。 このプログラムの計算量はO(1)です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int sum = N * (N + 1) / 2;
  cout << sum << endl;
}

入力

10

実行結果

55

O(N)

次のプログラムは要素数Nの配列の中に含まれる偶数の個数を数えるものです。 このプログラムの計算量はO(N)です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a.at(i) % 2 == 0) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

入力

5
1 4 2 5 9

実行結果

2

O(N ^ 2)

次のプログラムは九九の要領でN×Nマスを埋めるものです。 このプログラムの計算量はO(N^2)です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  vector<vector<int>> table(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      table.at(i).at(j) = (i + 1) * (j + 1);  // N×N回実行される
    }
  }

  // 出力
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << table.at(i).at(j);
      if (j != N - 1) {
        cout << " ";
      }
      else {
        cout << endl;
      }
    }
  }
}

入力

9

実行結果

1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

N \times N要素の二次元配列を使っているので空間計算量もO(N^2)となります。

O(\log N)

初めに簡単に\logを説明します。

\log_x Nという式は「xを何乗したらNになるか」を表します。 例えば、2^4 = 16なので、\log_2 16 = 4です。

次の図を見てください。長さ8の棒を長さが1になるまで半分に切る(2で割る)ことを繰り返したときに切る回数は\log_2 8回です。

このように計算量に出てくる\logは「半分にする回数」を表すことが多いです。

\log NはNに対して非常に小さくなるので、計算量の中にO(\log N)が出てきた場合でも実行時間にそこまで影響しないことが多いです。 具体的な値が知りたい場合は、Google検索で「log_2 値」のように検索することで確認できます。

補足：厳密な定義は高校数学の範囲なので詳しく知りたい人は別で勉強してください。
また、オーダー記法ではlogの底は省略して書かれることが多いです。この場合は2が省略されていると考えましょう。
実はlogの底の違いは定数倍の違いだけとみなすことができるので、係数を省略するオーダー記法では省略されます。

次のプログラムはNが2で何回割れるかを数えるものです。 このプログラムの計算量はO(\log N)です。

上に挙げたイメージと同じような処理を行うプログラムなので、ループする回数が大体\log_2 N回になることが分かります。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int cnt = 0;
  while (N > 0) {
    cnt++;
    N /= 2;
  }
  cout << cnt << endl;
}

計算量のおおまかな大小

主な計算量の大まかな大小は次のようになります。

O(1) < O(log N) < O(N) < O(N log N) < O(N ^ 2) < O(2 ^ N)

時間計算量ならO(1)側ほど高速に計算可能で、O(2^N)側ほど時間が掛かります。

これらの関係をグラフに示すと次のようになります。

入力Nと実行時間の感覚の対応を次の表に示します。

1秒くらいで計算が終わるようなプログラムを作ろうというときは、 入力の大きさの上限を見積もった上で1秒以内に収まるような計算量のアルゴリズムを選択する必要があります。

例えば、N=10^6くらいまでの入力で1秒以内に計算を終えるプログラムを作成するのであれば、 O(N^2)のアルゴリズムでは間に合わないので、O(N)のアルゴリズムを用いて実装する必要があります。

AtCoderの問題では実行時間制約が2秒くらいであることが多いです。 コンテストに参加する人は、1秒あたり10^8回くらいの計算ができることを覚えておきましょう。

複数の入力がある場合のオーダー記法

プログラムの入力が複数ある場合もオーダー記法で計算量を表すことができます。 この場合それぞれの変数を残して書きます。 例えば、2つの入力NとMを受け取る場合はO(N + M), O(NM), O((N + M) \log N)のように書きます。

N^2 M + NM + NM^2という計算ステップ数になった場合は、影響が一番大きくなりうる項のみ残すのでO(N^2M + NM^2)となります。

どの項を残すのかが分からなくても計算量が比較できればよいので問題無いです。複数の入力が計算量に影響することがあるということは頭に入れておきましょう。

細かい話

オーダー記法の落とし穴

計算量をオーダー記法で表記すると比較しやすくなりますが、オーダー記法は大まかな比較しかできない点に注意する必要があります。

オーダー記法では影響の一番大きな項のみを残して係数を省略して書きます。 これによって、例えば計算ステップ数が20Nになるアルゴリズムと2Nになるアルゴリズムを比較しようとしたときに、 実際には10倍もの差があるのに、オーダー記法ではどちらもO(N)となってしまいます。

同様の理由で、O(N)のアルゴリズムAとO(N \log N)のアルゴリズムBを比較するときに、 計算量上はアルゴリズムAの方が高速でも、実際に動かしてみるとアルゴリズムBの方が高速だったということも起こり得ます。

正確に比較する必要がある場合は、実際に時間を計測して比較する必要があります。

STLの関数の計算量

1.14 STLの関数で紹介した関数の計算量は以下のようになります。

次のプログラムは入力される配列をソートして出力するものです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);

  // O(N)
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  // O(N log N)
  sort(A.begin(), A.end());

  // O(N)
  for (int i = 0; i < N; i++) {
    cout << A.at(i) << endl;
  }
}

N回のループが2つあるので全体の計算量がO(N)であるように思えますが、 sort関数の計算量はO(N \log N)でループ部分のO(N)より大きいので、このプログラム全体の計算量はO(N \log N)となります。

logの性質

• O(\log 5N) → O(\log N)　logの中の係数は省略します。

• O(\log NM) → O(\log N + \log M)　どちらで書いてもよいですが、大きさを考えるときにこの関係を知っていると見積もりやすいかもしれません。

• O(\log N^2) → O(\log N)

• O(\log 2^N) → O(N)

演習問題

リンク先の問題を解いてください。

EX21.計算量の見積もり

前のページ | 次のページ