zukaついに競技プログラミングを始めました！
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回は2.06.計算量です。
実装
#include <bits/stdc++.h>
using namespace std;
int f0(int N) {
return 1;
}
int f1(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
s++;
}
for (int i = 0; i < M; i++) {
s++;
}
return s;
}
int f2(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
int t = N;
int cnt = 0;
while (t > 0) {
cnt++;
t /= 2;
}
s += cnt;
}
return s;
}
int f3(int N) {
int s = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
s++;
}
}
return s;
}
int f4(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s += i + j;
}
}
return s;
}
int f5(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s += i + j;
}
}
return s;
}
int main() {
int N, M;
cin >> N >> M;
int a0 = -1, a1 = -1, a2 = -1, a3 = -1, a4 = -1, a5 = -1;
// 計算量が最も大きいもの1つだけコメントアウトする
a0 = f0(N);
a1 = f1(N, M);
a2 = f2(N);
a3 = f3(N);
// a4 = f4(N);
a5 = f5(N, M);
cout << "f0: " << a0 << endl;
cout << "f1: " << a1 << endl;
cout << "f2: " << a2 << endl;
cout << "f3: " << a3 << endl;
cout << "f4: " << a4 << endl;
cout << "f5: " << a5 << endl;
}ポイント
計算量には時間計算量と空間計算量がある
オーダー記法を用いて計算量を記述できる
入力のオーダーにしたがって適切な計算量のアルゴリズムを実装する必要がある
競技プログラミングで計算量と言うときは，たいていの場合時間計算量を指します。APG4bによれば，時間計算量は以下のように定義されています。
「プログラムの実行に必要な計算のステップ数が入力に対してどのように変化するか」という指標を時間計算量と呼びます。
APG4b「2.06.計算量」より
時間量の記述に用いられるのがオーダー記法です。
\[ O(\cdot) \]
このオーダー記法を用いることで，プログラムの実行時間を簡単に見積もることができます。今回の例題実装でオーダー記法を確認してみましょう。
int f0(int N) {
return 1;
}f0は1を返すだけの関数です。ですので，計算量は$O(1)$になります。
int f1(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
s++;
}
for (int i = 0; i < M; i++) {
s++;
}
return s;
}f1は$N$回のforループと$M$回のforループを回すだけの関数です。ですので，計算量は$O(N+M)$になります。
int f2(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
int t = N;
int cnt = 0;
while (t > 0) {
cnt++;
t /= 2;
}
s += cnt;
}
return s;
}f2は$N$回のforループの中で$N$が$2$で何回割り切れるかを数えている関数です。ですので，計算量は$O(N\log N)$になります。
int f3(int N) {
int s = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
s++;
}
}
return s;
}f3は$3$回のforループの中で$3$回のforループが計算される関数です。ですので，計算量は$O(1)$になります。
int f4(int N) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
s += i + j;
}
}
return s;
}f4は$N$回のforループの中で$N$回のforループが計算される関数です。ですので，計算量は$O(N^2)$になります。
int f5(int N, int M) {
int s = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
s += i + j;
}
}
return s;
}f5は$N$回のforループの中で$M$回のforループが計算される関数です。ですので，計算量は$O(NM)$になります。
今回の入力オーダーは以下のようになっています。
0 &\leq N & \leq 10^{6} \\
0 &\leq M & \leq 10^{2}
\end{alignat}
これを踏まえると，計算量が$O(N^2)$であるf4のみ計算が間に合わないということが分かります。ちなみに，入力オーダーと計算量の関係は以下の通りです。
| $N$ | $O(1)$ | $O(\log N)$ | $O(N)$ | $O(N \log N)$ | $O(N^2)$ | $O(2^N)$ |
| $1$ | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 |
| $10$ | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 | 一瞬 |
| $10^3$ | 一瞬 | 一瞬 | 一瞬 | 一瞬 | $\fallingdotseq 0.01$[s] | 地球爆発 |
| $10^6$ | 一瞬 | 一瞬 | $\fallingdotseq 0.01$[s] | $\fallingdotseq 0.2$[s] | $\fallingdotseq 3$[h] | 地球爆発 |
| $10^8$ | 一瞬 | 一瞬 | $\fallingdotseq 1$[s] | $\fallingdotseq 30$[s] | $\fallingdotseq 3$[y] | 地球爆発 |
| $10^{16}$ | 一瞬 | 一瞬 | $\fallingdotseq 3$[y] | $\fallingdotseq 170$[y] | 地球爆発 | 地球爆発 |
表中の[s]は秒，[h]は時間，[y]は年を表す
$O(\log N)$までは入力オーダ気にせずに使用しても良さそうですね。たとえ$O(N)$であっても，入力が$10^{16}$になってしまうと3年もかかってしまうようです。
$O(N \log N)$は$10^8$くらいのオーダーから時間がかかってしまうことを意識する必要がありそうです。$O(N^2)$になると，もはや$10^3$程度しか入力を受け付けられず，$O(2^N)$であれば$1$程度しか受け付けられないことも分かります。
コメント