W - 2.06.計算量 /

Time Limit: 0 msec / Memory Limit: 0 KB

前のページ | 次のページ

キーポイント

  • プログラムを実行するときには処理内容に応じた実行時間がかかる
  • コンピュータの記憶領域(メモリ)は有限であり、プログラムで変数を使用した分だけメモリを消費する
  • プログラムの実行時間・メモリ使用量が入力に応じてどのように変化するかを見積もったものを、それぞれ時間計算量空間計算量という
  • 計算量の表記にはオーダー記法を用いることが多い

アルゴリズム

ある処理を行うプログラムを作成するときに、どのような計算を行っていくかという計算手順のことをアルゴリズムといいます。
例えば、1から100までの総和を計算するプログラムを考えます。 1+2+3+...+99+100と順番に足していくというのは1つのアルゴリズムです。これをアルゴリズムAとします。 一方、\frac{100 \cdot (1 + 100)}{2}という式を用いて計算するというのもアルゴリズムです。これをアルゴリズムBとします。

この例のように、プログラムを作成するにあたって複数のアルゴリズムが考えられることがあります。 そのような場合には、どちらのアルゴリズムを用いるのかを選ぶことになります。

コンピュータの一回の計算には僅かに時間が掛かるので、計算回数が多くなるほど実行時間が長くなります。 より計算回数が少ないアルゴリズムを選択することによって、高速に動作するプログラムを作成できます。

上の例でのアルゴリズムAは99回の足し算が必要ですが、アルゴリズムBでは足し算・掛け算・割り算の計3回の計算で結果を求めることができます。 99回の計算が必要なアルゴリズムAと、3回の計算が必要なアルゴリズムB、というように必要な計算の回数で大まかな性能を見積もることができます。

アルゴリズムの性能を比較する方法は色々ありますが、1つの指標として計算量という考え方があります。

計算時間と記憶領域

既に説明しましたが、コンピュータがプログラムを実行するときには、処理内容に応じた時間が掛かります。

コンピュータの記憶領域のことをメモリといいます。メモリは有限であり、変数を使用した分だけメモリを消費します。 文字列や配列の変数は内部の要素数に応じてメモリを消費します。 例えば、int型のN要素の配列はN個のint型の変数を使用したのと同じくらいのメモリを消費します。 同様に長さNの文字列はN個のchar型の変数を使用したのと同じくらいのメモリを消費します。

計算量

プログラムは入力に対して必要な計算を行い、結果を出力します。 このときに必要な計算時間や必要な記憶領域の量が、入力に対してどれくらい変化するかを示す指標を計算量といいます。

計算量には時間計算量空間計算量があります。単に計算量という場合、時間計算量を指すことが多いです。

時間計算量

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

空間計算量

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

計算量の例

次のプログラムは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 Nint sumint 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を大きくしていったときに「大きくなるスピードが最も速い項」と考えてください。 例えばNN^2を比較すると、以下の表のようになるので3N^2の方が影響が大きいといえます。

N N^2
N=1 1 1
N=10 10 100
N=100 100 10,000
N=1,000 1,000 1,000,000

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個}

答え

クリックで答えを開く

  1. O(N)
  2. O(N^3)
  3. O(1)
  4. O(2^N)

2^NN^2の比較は次の表の通りです。

2^N N^2
N=1 2 1
N=10 1,024 100
N=30 1,073,741,824 = 約10億 900

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

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

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

#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
実行結果
45

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 NNに対して非常に小さくなるので、計算量の中に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と実行時間の感覚の対応を次の表に示します。

N O(1) O(\log N) O(N) O(N \log N) O(N^2) O(2^N)
1 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
10 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
1000 一瞬 一瞬 一瞬 一瞬 0.01秒くらい 地球爆発
10^6 一瞬 一瞬 0.01秒くらい 0.2秒くらい 3時間くらい 地球爆発
10^8 一瞬 一瞬 1秒くらい 30秒くらい 3年くらい 地球爆発
10^{16} 一瞬 一瞬 3年くらい 170年くらい 地球爆発 地球爆発

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

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

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

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

プログラムの入力が複数ある場合もオーダー記法で計算量を表すことができます。 この場合それぞれの変数を残して書きます。 例えば、2つの入力NMを受け取る場合は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の関数で紹介した関数の計算量は以下のようになります。

STLの関数 計算量(配列の要素数N)
sort O(N \log N)
reverse O(N)

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

#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)


演習問題

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