競技プログラミング講習/計算量

概要

今回は、競技プログラミングにおいて知っておくと便利な計算量ついて解説します。
計算量について知っていると、今書いたプログラムが大体どれくらいの時間で終わるかを見積もることができます。
A問題,B問題は制約が緩くなっているので、特に計算量を意識しなくても解ける問題が多いですが、
C問題,D問題などでは工夫して計算量を落とす問題などがあるため、何が通って何が通らないのかを意識しましょう。

重要語

時間計算量

プログラムがどれくらいの時間で終わるかの指標

空間計算量

プログラムがどれくらいのメモリを使用するかの指標

必要語

今回の必要語はありません。

オーダー記法

コンピュータが計算をするときには僅かですが時間がかかるので、計算回数が多くなると実行時間が長くなります。
そのため、100000回計算するプログラムと10回計算するプログラムでは、10回計算するプログラムのほうが早いです。
また、入力によって計算のステップ数が違うこともよくあります。
例えばNが入力として与えられていて、N2回計算するといったようなことです。
早いプログラムを選ぶときには計算量を比較したいわけですが、厳密に2N2+N+3と求めることは大変です。
そこで、便利な記法としてオーダー記法があります。それは以下のように求めることができます。
  1. 係数を無視する（ただし定数は1とする）。
  2. Nを大きくしていったときに最も影響の強い項以外無視する。
例えば2N2+N+3であれば、
  1. 係数を無視して、N2+N+1とする。
  2. N2,N,1のうちN2が最も影響が強い。
よって、O(N2)と表すことができます。

時間計算量

プログラムには時間がかかります。その時間の見積もりは重要です。

計算量の例

例えばNが入力として与えられて、1+2+3+...+Nを求めろという問題に対して、以下のような回答が考えられます。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += i;
    }
    cout << ans << endl;
    return 0;
}
しかし、これには足し算をN回繰り返す必要があり、時間計算量はO(N)です。一方、こちらのプログラムはどうでしょう。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = n * (n + 1) / 2;
    cout << ans << endl;
    return 0;
}
これは和の公式1+2+3+...+N=N(N+1)/2を用いて計算しています。こちらは四則演算を数回しているだけなので、O(1)です。
このように、同じ結果でも違うアルゴリズムが考えられます。この場合、O(N)とO(1)を比較して、和の公式を用いたほうが早いと判断することができます。

TLE

AtCoderのジャッジではTLE(Time Limit Exceeded)というものがあります。これが出た場合は計算量を見積もってみましょう (TLEが出てから計算量を見積もってもいいですが、コードを書く前に見積もることをお勧めします)。
問題名の下に「実行時間制限」が書いてあり、実行時間がこれを超えるとたとえ正しい答えを出力していてもTLEと判定されます。
実行制限時間は問題ごとに決まっていますが、たいていは2秒です。
AtCoderのジャッジはC++の場合1秒間に108回くらいの計算をすることができます。
そのため、制約が1≦N≦105となっていたら、O(N2)はTLEですが、O(N)であれば間に合います。
また、1+2+3+...+Nを求めろという問題で、制約が1≦N≦105であればO(1)もO(N)もどちらも間に合ってACをとることができます。 ABCなどのコンテストにおいてTLEでなければ実行時間は順位に関係ないため、O(1)とO(N)の両方を思いついた場合は無理にO(1)を書かずに、書きやすい（もしくはバグらせにくい方）を書きましょう。 しかし、1≦N≦109であれば、O(N)はTLEになりますので、諦めてO(1)を書きましょう。

空間計算量

C++において、空間計算量を気にすることはあまりありませんが、
少なくともint a[100000][100000]のような大きすぎる配列は確保できないということを知っておきましょう。

空間計算量の例

入力としてa,b,cが与えられ、a*b*cを出力します。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << a * b * c << endl;
    return 0;
}
この場合、どのような入力でも使う変数はa,b,cの3つなので、空間計算量はO(1)です。 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        ans *= a[i];
    }
    cout << ans << endl;
    return 0;
}
この場合、変数はn,ans,i,vector<int> a(n)を使っています。 このうちvector<int> a(n)は入力Nに比例してメモリを消費するので、空間計算量はO(N)となります。
※typedef long long ll;はlong longという型名をllとして使えるようにする記述で、 タイプ数が少なくなって便利であるため使用しています。

MLE

AtCoderのジャッジではMLE(Memory Limit Exceeded)というものがあります。これはC++においてなかなか起こりづらいですが、 問題名の下に「メモリ制限」が書いてあり、メモリ使用量がこれを超えるとMLEと判定されます。
メモリ制限は問題ごとに決まっていますが、たいていは1024MBです。
1024MB≒109Bですから、int型の配列であれば要素数は108位が限度でしょう。
しかしそもそも、そのような配列をfor文などで見ていたらTLEしてしまいます。より効率の良いアルゴリズムを使用したり、本当にその配列は必要なのかを考え直してみてください。

練習問題

理解できたか確認するために、練習問題を解いてもらいます。
実際のコンテストで出題された問題ではなく入門教材のため少し特殊な問題形式ですが、以下の問題を解いてみてください。
EX21 - 計算量の見積もり