NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。
0. はじめに
世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います:
アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると「$n$ ってなんだよ」「$\log$ がどこから出て来るんだよ」という疑問が湧いて馴染めない方も多いかもしれません。しかし計算量は慣れるとものすごく使い勝手がよく、実装しようとしているアルゴリズムを実際にプログラミングしなくても
計算実行にどのくらいの時間がかかるかを予め大体見積もることができる
ようになります！！！ 本記事では
- 計算量オーダーの「求め方」の豊富な実例
- 計算量の概念を「どう役立てるか」
- 様々な計算量オーダーをもつ具体的なアルゴリズム
の紹介をしていきます。また本記事の続編として、実務で気を付けたい計算量の罠の話を書きました。併せて読んでいただけたらと思います:
1. 計算量とは
計算量という概念を理解するためには、まずは以下のことを悟ることが重要です:
- 一般に同じ問題を解決できるアルゴリズムは多数考えることができる
- アルゴリズムによって所要時間が大きく変わる
- 良いアルゴリズムとは、解決したい問題の規模が大きくなっても対応できるようなもののことである
例として、ちょっとした数当てゲームを考えてみましょう。本質的にはこの記事の冒頭に挙げている年齢当てゲームと同じものです。
【数当てゲーム】
相手に「0 以上 32 未満の整数値」をなにか 1 つ思い浮かべてもらい、それを当てたいです。
相手に何回か「Yes / No で答えられる質問」をすることができます。できるだけ少ない回数で当てるにはどうしたらよいでしょうか？
パッと思いつく方法は
- 0 ですか？
- 1 ですか？
- 2 ですか？
- ...
と順々に聞いていく方法でしょう。これでは最悪 32 回かかってしまいます。もっと賢い方法があります。
「16 以上ですか？」
と聞いてみましょう。そうすると
- Yes なら: 0 以上 16 未満だとわかる
- No なら: 16 以上 32 未満だとわかる
といったように、どちらの答えだったとしても、選択肢が半分に絞れます。あとは同様のことを繰り返していけば、たった 5 回の質問で当てることができます！なお、前者のようなやり方を線形探索法、後者のようなやり方を二分探索法 (二分法)と呼びます。応用情報技術者試験などでも頻出のテーマですので、馴染みのある方も多いでしょう。
さて、さらに話を進めてみましょう。
今回は相手の思い浮かべる数が 32 未満という条件下だったので、質問回数に差があるとはいっても「(最悪) 32 回」と「5 回」の差で済みました。これに対して相手の思い浮かべる数の制限が 65536 未満だったとしましょう。そうすると
- 前者の線形探索法: (最悪) 65536 回 (より一般に $O(n)$ 回)
- 後者の二分探索法: 16 回 (より一般に $O(\log{n})$ 回)
とおぞましいほどの差が生じます。このように「アルゴリズムの良し悪し」というのは、入力サイズ $n$ (今回の問題では相手の思い浮かべる値の上限制約) が大きくなった場合にどうなっていくか、という視点で考えるものです。できれば実装する前に「どのくらいの計算時間がかかるのか」を判断できるようにしたいところです。すごいことに、実際にアルゴリズムを実装することなく大まかに計算時間を測ることができる「ものさし」が存在します！
それが計算量オーダーとよばれるものです。
1-1. 計算量オーダー
先に述べた通り、アルゴリズムへの入力サイズを $n$ として、アルゴリズムの計算実行時間が $n$ に応じてどのように変化していくかを考えます。それを $O(n)$ や $O(n^2)$ や $O(n\log{n})$ といった記法で表します。これらの意味はざっくりと言ってしまえば
- $O(n)$ のアルゴリズムは、$n$ に比例した回数の計算ステップを要する
- $O(n^2)$ のアルゴリズムは、$n^2$ に比例した回数の計算ステップを要する
- $O(n\log{n})$ のアルゴリズムは、$n\log{n}$ に比例した回数の計算ステップを要する
という感じです。例えば
for (int i = 0; i < n; ++i) {
// なにかする (各 i に対する処理は軽いものとする)
}
の形をしたアルゴリズムは $O(n)$ ですし、
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// なにかする (各 i, j に対する処理は軽いものとする)
}
}
の形をしたアルゴリズムは $O(n^2)$ になります。入力サイズ $n$ が具体的に何を表すかについてですが、多くの場合、処理する配列のサイズだったり、参照データベースのサイズだったりします。
1-2. ランダウの O 記法
ランダウの $O$ 記法はとても便利です。現実のプログラムは
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// なにかする
}
}
のように「なにかする」回数が綺麗にピッタリ $n^2$ 回になるなんてことはほとんどなく、$3n^2 + 5n + 100$ 回などになったりするのですが、それをざっくりと
- 最高次数の項以外は落とす: $3n^2 + 5n + 100$ -> $3n^2$
- 係数を無視する: $3n^2$ -> $n^2$
という風にして「概ね $n^2$ 回に比例する計算時間を要する $O(n^2)$ のアルゴリズムである」という風に考えます。数学IIIで学ぶ「極限」に馴染みのある方であれば
$\lim_{n \to \infty} \frac{3n^2 + 5n + 100}{n^2} = 3$
であることを思い出すとピンと来ると思います。つまり $n$ が大きくなると $3n^2 + 5n + 100$ は漸近的に $n^2$ に比例していて、比例係数は $3$ だということです。
極限がピンと来ない方向けに、まず最高次数の項以外を落とす理由を説明します。以下のグラフに見る通り、$n$ が大きくなると、$n^2$ は $n$ よりも圧倒的に大きくなります。やがて $3n^2 + 5n + 100$ の $5n$ の部分はほとんど無視できるようになります。具体的に $n = 100,000$ などを代入してみるとよくわかります:
\begin{align}
3n^2 + 5n + 100 &= 30,000,500,100 \\
3n^2 &= 30,000,000,000
\end{align}
次に $3n^2$ -> $n^2$ と係数を落とす理由です。確かに極限まで高速化を追求する場面では、係数の差は重要になって来ます。しかしその前段階では係数の差はほとんど無視できます。例えば $O(n^3)$ なアルゴリズムを $O(n^2)$ に改良しようとしている場面を考えてみます。$n^3$ 回ステップのアルゴリズムに対して、係数は $10$ 倍だがオーダーは小さい $10n^2$ 回ステップのアルゴリズムが得られたとします。$n = 100,000$ とすると
\begin{align}
n^3 &= 1,000,000,000,000,000 \\
10n^2 &= 100,000,000,000
\end{align}
という風に、係数が $10$ 倍になっているのもかかわらず $10,000$ 倍の高速化が達成できます。プログラムの実行時間を短くするには、まずはアルゴリズムの計算量のオーダーを小さくすることが重要であることがわかります。
1-3. 計算量の使い方
計算量オーダーの概念を掴んだところで、実際の問題に対してアルゴリズムを設計するときの考え方について解説します。現実世界の問題では
- 実行時間の制限時間がどの程度か
- 解きたい問題のサイズ $n$ がどの程度の大きさか
がある程度決まっているケースが多いです。そうすると、どの程度の計算量オーダーのアルゴリズムを達成する必要があるのかを逆算できることになります。ここでは
- 実行制限時間 $1$ 秒
- 計算に使用するマシンは普通の家庭用 PC
という状況を想定します。このとき目安として
$1$ 秒間で処理できる for 文ループの回数は、$10^8 = 100,000,000$ 回程度
というのが有効です。PC の性能は年々良くなっているため、この目安は時代とともに流動的です。例えば 8 年前に初版の刊行されたプログラミングコンテストチャレンジブック (通称蟻本) の P.20 の記載と比較すると現在では以下のような感じです:
| ループ回数 | 蟻本の記載 | 現在 |
|---|---|---|
| $10^6$ | 余裕を持って間に合う | |
| $10^7$ | おそらく間に合う | 余裕を持って間に合う |
| $10^8$ | 非常にシンプルな処理でない限り厳しい | おそらく間に合う |
| $10^9$ | 非常にシンプルな処理でない限り厳しい |
それではこれを踏まえて各オーダーのアルゴリズムが、入力サイズ $n$ に応じて計算ステップ数がどうなるかを大まかに整理してみます。1 秒以上かかる部分 (計算ステップ数が $10^8$ 回を超える部分) は 「-」 で記載しています。
| $\log{n}$ | $n$ | $n\log{n}$ | $n^2$ | $n^3$ | $2^n$ | $n!$ |
|---|---|---|---|---|---|---|
| 2 | 5 | 12 | 25 | 130 | 30 | 120 |
| 3 | 10 | 33 | 100 | 1,000 | 1,024 | 3,628,800 |
| 4 | 15 | 59 | 225 | 3.375 | 32,768 | - |
| 4 | 20 | 86 | 400 | 8,000 | 1,048,576 | - |
| 5 | 25 | 116 | 625 | 15,625 | - | - |
| 5 | 30 | 147 | 900 | 27,000 | - | - |
| 7 | 100 | 664 | 10,000 | 1,000,000 | - | - |
| 8 | 300 | 2,468 | 90,000 | 27,000,000 | - | - |
| 10 | 1,000 | 9,966 | 1,000,000 | - | - | - |
| 13 | 10,000 | 132,877 | 100,000,000 | - | - | - |
| 16 | 100,000 | 1,660,964 | - | - | - | - |
| 20 | 1,000,000 | 19,931,568 | - | - | - | - |
こうしてみると、$O(\log{n})$ はすごいですね。$n$ をいくら増やしてもビクともしません。それに比べて $O(n!)$ は一瞬で力尽きました。$O(2^n)$ も早々に力尽きてしまいました。$O(n^2)$ はそこそこ頑張りますがやはり $n$ が大きくなると厳しいです。$O(n\log{n})$ はかなり頑丈です。まとめると、解きたい問題のサイズと適用可能なアルゴリズムの計算量オーダーの上限は以下のように整理できます。
| サイズ $n$ | 実世界での規模間 | 可能な計算量 | アルゴリズム例 | 備考 |
|---|---|---|---|---|
| $10^{9}～10^{12}$ | Facebook ユーザ数、Web ページ数 | $O(\log{n})$ | 二分探索など | $O(\sqrt{n})$ も有効です。このサイズの問題を扱う場合は全データを読み込むとメモリに収まらないことも多く、あらかじめ登録されたデータベースから必要に応じて入力を読み取るようにすることも多いです。 |
| $10^7～10^8$ | 国内 Facebook ユーザ数、全米の道路網の交差点数 | $O(n)$ | 線形探索、グラフ探索など | データ読み込みを数回繰り返す程度の計算時間 |
| $10^5～10^6$ | Qiita ユーザ数、ニューヨーク道路網の交差点数 | $O(n\log{n})$ | ソートなど | $O(n\sqrt{n})$ も有効、平方分割など |
| $10^3～10^4$ | arXiv 論文共著網 | $O(n^2)$ | 挿入ソートなど | 工夫なしの単純なアルゴリズムはしばしばこの計算量になります |
| $300$ | $O(n^3)$ | 行列演算、Floyd-Warshall 法、重み付き二部マッチングなど | 何気によく登場します | |
| $100$ | $O(n^4)$ | 二次元配列の部分長方形全部を愚直に処理するとこの計算量になりがちです | ||
| $30$ | $O(2^{\frac{n}{2}})$ | $O(2^n)$ かかりそうな問題で、半分全列挙するとこの計算量になったりします | ||
| $20$ | $O(2^n)$ | bit 全探索など | 指数時間アルゴリズムは悪と言われますが、サイズが小さければ OK です | |
| $10$ | $O(n!)$ | 順列全探索など | $n = 10$ まで小さければ $n!$ 通りの全探索も間に合います |
実用上の多くの場面では、$n = 10^5～10^7$ 付近のデータを扱うケースが多く、$O(n^2)$ なアルゴリズムを $O(n)$ や $O(n\log{n})$ に改善できるかどうかが鍵となるケースが多いように思います。ソートアルゴリズムなどはまさにその典型と言えるでしょう。普段標準ライブラリを用いているために高速化の恩恵を意識することはないですが、愚直に実装すると 1 時間かかる処理が僅か 0.1 秒で終えられるようになっています。
また、本当は $O(n)$ のアルゴリズムを実装したつもりが、データ構造を雑に扱ってしまった結果 $O(n^2)$ になってしまった、というケースは極めて多いです。そうすると処理がありえないくらい遅くなってしまいがちなので、計算量についての意識をしっかりと持ちたいところです。その手の話題については以下の記事に特集してみました:
多くの書籍では、$O(n^3)$ 辺りが限界としています。これよりオーダーの大きなアルゴリズムは実用にならないといった感じです。実際のところ $O(n^3)$ でも厳しい場面も多いです。典型例として重み付き二部マッチング問題は実用上頻出の問題ですが、よく知られたアルゴリズムは $O(n^3)$ で $n = 1000$ 程度までしか扱えず厳しいので、実際には厳密解法ではない近似的なヒューリスティック解法を考える流れになるケースも多いです。
一方、$O(2^n)$ といった指数時間アルゴリズムは蔑視されがちですが、$n \le 20$ であることが確定しているなど、サイズが小さい問題に対しては十分有効だと言えます。なお反対に極端に高速なアルゴリズムとして、問題のサイズ $n$ に依存しない定数時間で終了する $O(1)$ アルゴリズムという概念もあります。
2. 計算量の求め方の例
具体的なアルゴリズムの計算量を解析する例を挙げて行きます。
例 1: 線形探索 O(n)
サイズ $n$ の配列 a が与えられて、そこに値 v があるかどうかを判定するコードです。フラグ変数 exist が最終的に true になるか false になるかによって判定します。
bool exist = false; // 存在しなかったら false のままになるように初期化
for (int i = 0; i < n; ++i) {
if (a[i] == v) {
exist = true; // 存在したら true に
break;
}
}
一見すると「場合によりけり」に思えます。もし配列の先頭 a[0] が v だったら一瞬で終了します。
しかし、計算量オーダーは「最悪ケースについて考える」のが鉄則です。この問題の場合、v が存在しなかったら、$n$ 回のループが回るので計算量オーダーは $O(n)$ になります。
例 2: 偶数出力 O(n)
正の整数 $n$ が与えられて、$n$ 以下の正の偶数をすべて出力する問題を考えます。以下のように簡潔に実装できます。
for (int i = 2; i <= n; i += 2) {
cout << i << ", ";
}
ループが回る回数は $n/2$ 回 (切り下げ) になります。計算量オーダーについて考えるときは係数は無視するので $O(n)$ になります。
例 3: かけ算九九 O(n^2)
かけ算九九は 1x1 から 9x9 までですが、1x1 から nxn までを出力する問題を考えます。
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << i << " x " << j << " = " << i * j << endl;
}
}
多重 for 文ループになると頭が混乱する方もいるかもしれません。上のコードを実行してみるとイメージが掴めると思います。$n = 3$ とすると以下のような出力になります:
1 x 1 = 1
1 x 2 = 2
1 x 3 = 3
2 x 1 = 2
2 x 2 = 4
2 x 3 = 6
3 x 1 = 3
3 x 2 = 6
3 x 3 = 9
まず i = 1 の場合を処理 (j = 1, 2, 3 と回る) してから、次に i = 2 の場合を処理して、最後に i = 3 の場合を処理する流れになっています。ループ回数は $n^2$ 回で、計算量オーダーも $O(n^2)$ です。
例 4: 二頂点間の最小距離 O(n^2)
$n$ 個の座標 (x, y) が与えられて、最も近い距離にある二点間の距離を求めます。
下の実装の注意点ですが、今回は二頂点の順番は関係ないため、添字 j のまわる範囲は i+1 からとしています。このようにしないと、例えば
- (x[2], y[2]) と (x[5], y[5]) との間の距離
- (x[5], y[5]) と (x[2], y[2]) との間の距離
を両方求めることになってしまい、無駄が生じます。
double minimum_dist = 10000000; // 十分大きい値
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
double dist = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); // 距離
if (dist < minimum_dist) {
minimum_dist = dist; // dist の方が小さかったら更新
}
}
}
ループが回る回数ですが
- $i = 0$ のとき $n - 1$ 回 ($j = 1, 2, \dots, n-1$)
- $i = 1$ のとき $n - 2$ 回 ($j = 2, \dots, n-1$)
- …
- $i = n-2$ のとき $1$ 回 ($j = n-1$ のみ)
- $i = n-1$ のとき $0$ 回
になるので、合計回数は
$(n-1) + (n-2) + \dots + 1 + 0 = \frac{1}{2} n^2 - \frac{1}{2} n$
となります。なおこれは、$n$ 個のものから $2$ 個選ぶ場合の数が ${}_n {\rm C}_{2} = \frac{1}{2} n^2 - \frac{1}{2} n$ であることからすぐに求めることもできます。
最高次以外の項は無視して、最高次の係数も無視するので、計算量オーダーは $O(n^2)$ になります。
二頂点間の最短距離を求める問題に限らず、$n$ 個のものから最適なペアを求めるような問題では同じようなアルゴリズムが使えます。発展的話題として、「二頂点間の最短距離」を求める問題は最近点対問題と呼ばれる有名問題であり、分割統治法に基づく $O(n\log{n})$ のアルゴリズムが知られています。
例 5: 行列乗算 O(n^3)
$n$ x $n$ の行列 $A, B$ の乗算を考えます。$C = A * B$ とすると以下のように実装できます。$C$ の各要素は $0$ で初期化されているものとします。
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
C[i][j] += A[i][k] * B[k][j];
for 文が 3 重ループになっており、計算量オーダーは $O(n^3)$ になります。
なお発展的話題として、行列乗算は $O(n^3)$ より小さいアルゴリズムで実現できることが知られています。Strassen のアルゴリズムが有名で、$O(n^{\log_2{7}}) \simeq O(n^{2.807})$ のアルゴリズムとなっています。どこまでオーダーを小さくできるのかは未解決問題です。
例 6: 二進法展開 O(logn)
正の整数 $n$ を二進法で表したときに何個の $1$ があるかを数えます。これは $n$ をビット (bit) だと思ったときの「立っているフラグの数」を表しています。GCC のビルトイン関数 __builtin_popcount() もそれを求める処理になっています。
int bit_count(int n) {
int count = 0;
while (n > 0) {
if (n % 2 == 1) ++count;
n /= 2;
}
return count;
}
具体的な処理内容の解説についてはこの問題の解説を見ていただけたらと思います。
計算量オーダーについて考えます。
- $n = 2$ のとき、ループ回数は $2$ 回
- $n = 4$ のとき、ループ回数は $3$ 回
- $n = 8$ のとき、ループ回数は $4$ 回
- $n = 16$ のとき、ループ回数は $5$ 回
- …
- $n = 2^k$ のとき、ループ回数は $k+1 (= \log_{2}{n} + 1)$ 回
となっています。ざっくり $\log_2{n}$ 回のループ回数ということになります。$n$ が $2$ のべき乗でない場合であっても、「$n$ 以下の最大の $2$ のべき乗」と同じループ回数になるので気にしなくて大丈夫です。したがって計算量オーダーは $O(\log{n})$ となります。
細かい注意点として、対数の底を省略して書くとき、一般には底は $e$ を表していますが、情報科学においては $2$ を表していることが多いです。しかし次の例で詳述するように、計算量オーダーについて考えるときは対数の底の違いは無視できることがわかります。
例 7: ナベアツ O(logn)
正の整数 $n$ が $3$ の倍数か、または $3$ の付く数字であるかどうかを判定します。$3$ の付く数字かどうかの判定は、前の例の二進法展開を応用して十進法展開すればよいです。
bool is_aho(int n) {
if (n % 3 == 0) return true; // 3 の倍数か
while (n > 0) {
if (n % 10 == 3) return true; // 3 が付くか
n /= 10;
}
return false; // 3 の倍数でなければ、3 も付かない場合
}
計算量オーダーについてですが、$3$ の倍数判定の方が $O(1)$ でできますが、$3$ がつくかどうかの判定は $O(\log_{10}{n})$ になります。対数 $\log{}$ の底が $10$ なのが気になるのですが、高校数学で懐かしい「底の変換公式」を用いると
\log_{10}{n} = \frac{\log_{2}{n}}{\log_{2}{10}}
となるので、実は $\log_{2}{n}$ と $\log_{10}{n}$ とでは定数倍の差しかないことがわかります。したがって、このアルゴリズムの計算量は $O(\log{n})$ になります。
なお注意点として、上の実装では $n$ を int 型としていますが、$n$ の桁数が大きくなる場合には「十進法表記の文字列」として入力が与えられるものとします。文字列の桁数は $O(\log{n})$ になります。その場合 $3$ が付くかどうかの判定は文字列 $n$ の各桁を一通り確認すればよく、やはり $O(\log{n})$ でできます。$n$ が int 型の場合に $10$ で割った余りを順々に求めている上記の実装は、実は $n$ を文字列だと思った時に一の位から順に見て行く操作を実現していることになります。また $n$ が $3$ の倍数かどうかの判定は、各桁の総和が $3$ で割り切れるかどうかを判定すればよいです。全体としてやはり $O(\log{n})$ で実現できます。
例 8: 二分探索 O(logn)
C++ の std::lower_bound() に相当する実装をします。すなわち、サイズ $n$ の配列 a の index (正確には iterator) のうち値 v 以上となる最小の index を返す実装をします。これは二分探索法と言ったときに一般にイメージされる「配列 a の中に値 v があるかどうかを検索する処理」を少し一般化したものになっています。詳細は
を読んでいただけたらと思います。
int binary_search(int v) {
/* 目的の index は [left, right) のどこかにある */
int left = -1;
int right = (int)a.size();
while (right - left > 1) {
int mid = left + (right - left) / 2;
/* a[mid] と v との大小関係に応じて候補区間を左右半分に分ける */
if (a[mid] >= v) right = mid; // 候補区間を [left, mid) に
else left = mid; // 候補区間を [mid, right) に
}
/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
return right;
}
最初は
- left = -1
- right = n
となっていて、right - left = n+1 ですが、1 回ループが回るごとに right - left の値は半分になります。そして right - left = 1 となるまでループを繰り返します。ループ回数は「例 6: 二進法展開」とほぼ同じ議論により、$O(\log{n})$ 回になることがわかります。一般にループが回る度にある量 $x$ の値が半分になっていくとき、ループ回数は $O(\log{x})$ 回になります。
したがって、この二分探索法の計算時間オーダーは $O(\log{n})$ になります。
例 9: マージソート O(n logn)
$O(n\log{n})$ なアルゴリズムな代表例としてマージソートがあります。詳しくは
を読んでいただけたらと思います。分割統治法に基づいた以下のようなアルゴリズムです。
/* 配列 a の [left, right) をソートします */
void MergeSort(vector<int> &a, int left, int right) {
if (right - left == 1) return;
int mid = left + (right - left) / 2;
// 左半分 [left, mid) をソート
MergeSort(a, left, mid);
// 右半分 [mid, right) をソート
MergeSort(a, mid, right);
// 一旦「左」と「右」のソート結果をコピーしておく (右側は左右反転)
vector<int> buf;
for (int i = left; i < mid; ++i) buf.push_back(a[i]);
for (int i = right-1; i >= mid; --i) buf.push_back(a[i]);
// マージする
int iterator_left = 0; // 左側のイテレータ
int iterator_right = (int)buf.size() - 1; // 右側のイテレータ
for (int i = left; i < right; ++i) {
// 左側採用
if (buf[iterator_left] <= buf[iterator_right]) {
a[i] = buf[iterator_left++];
}
// 右側採用
else {
a[i] = buf[iterator_right--];
}
}
}
先のソート記事では計算量解析は「お気持ち」で済ませているので、ここではきちんと漸化式を用いて導出したいと思います。マージソートの計算量を $T(n)$ とすると、以下のような漸化式が成立します:
$T(1) = O(1)$
$T(n) = 2T(n/2) + O(n)$ ($n > 1$)
サイズ $n$ の問題を半分ずつに分割してそれぞれ解く部分の計算量が $2T(n/2)$ で、マージする部分の計算量が $O(n)$ なのでこのような漸化式になります。これはマージソートに限らず、分割統治法アルゴリズムを用いたときに広く見られる漸化式です。一般に
$T(1) = O(1)$
$T(n) = aT(n/b) + O(n)$ ($n > 1$)
という漸化式で表された計算量が
T(n) = \left\{
\begin{array}{ll}
O(n) & (a < b) \\
O(n\log{n}) & (a = b) \\
O(n^{\log_{b}{a}}) & (a > b)
\end{array}
\right.
で表されることを付録で略証します。今回は $a = b = 2$ なので、マージソートの計算量は $O(n\log{n})$ になります。
例 10: 素数判定 O(√n)
$2$ 以上の整数 $n$ が素数かどうかを判定します。
素数とは $1$ と自分自身以外では割り切れない数なので、各 $a$ ($1 < a < n$) に対して $n$ が $a$ の倍数かどうかを調べればよいです。しかしよく考えると $1 < a \le \sqrt{n}$ について調べれば十分であることがわかります。なぜなら、$n$ が $a$ で割り切れるならば、$a * b = n$ として $b$ も $n$ の約数になっているからです。$a$ が大きいときは $b$ が小さくなります。つまり、$n$ が $a$ で割り切れることが判定されるよりも先に $b$ で割り切れることが判定されます。例えば $n = 39$ とするとこれは $a = 13$ で割り切れますが、それより前に $b = 39/13 = 3$ で割り切れることが判定されます。従って $a \le \sqrt{39}$ まで試せば十分です。
bool is_prime(int n) {
for (int i = 2; i*i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
計算量オーダーは $O(\sqrt{n})$ になります。このように $\sqrt{}$ が登場することもあります。
発展的話題として、ここでの $O(\sqrt{n})$ について、一見すると多項式時間アルゴリズムであると勘違いしそうになるのですが実は指数時間アルゴリズムです。その理由をしっかりと理解するためにはチューリングマシンなどを理解する必要が出て来るのですが、ざっくりと
- 「個数」を表す $n$ について多項式オーダーなら多項式時間 (平方分割などでよく登場する $O(n\sqrt{n})$ などはちゃんと多項式時間です)
- 「数値」を表す $n$ について多項式オーダーでも指数時間 (真の入力サイズは $n$ ではなく、$n$ の桁数 $\log{n}$ とみなされるためです)
という感じです。例えば数値 $n$ について一見多項式な $O(n^3)$ なアルゴリズムが得られたとしても、真の入力サイズは $\log{n}$ ですので、
n^3 = 2^{3\log{n}}
より、確かに指数時間アルゴリズムになっています。今回の $O(\sqrt{n})$ な素数判定アルゴリズムも同様に
\sqrt{n} = 2^{\frac{1}{2}\log{n}}
より指数時間アルゴリズムです。
しかし数値を表す $n$ に依存する計算時間であっても、$n$ の桁数 $\log{n}$ について多項式時間であれば多項式時間アルゴリズムであると言えます。そのようなアルゴリズムを弱多項式時間アルゴリズムと呼び、計算量オーダーが「個数」のみに依存する多項式時間アルゴリズムを強多項式時間アルゴリズムと呼んで区別することもあります。
恐るべきことに、素数判定には多項式時間アルゴリズムが存在します！！！！！
AKS素数判定法と呼ばれる $\tilde{O}((\log{n})^{7.5})$ の恐ろしいアルゴリズムがあります。$\tilde{O}$ の意味は wikipedia を参考にしてもらえたらと思います。
- 論文 (2005): M. Agrawal et al., PRIMES is in P
例 11: bit 全探索 O(n2^n)
有名な部分和問題を考えます。これも多項式時間アルゴリズムは存在しないだろうと広く信じられている NP 完全問題です。部分和問題とは、$n$ 個の正の整数値 a[0], a[1], ..., a[n-1] をいくつか選んでその総和を $A$ にできるかどうかを判定する問題です。(a[0], a[1], ..., a[n-1]) の部分集合は $2^n$ 通りあるため、愚直に全探索すると $2^n$ 通りの探索をすることになります。実装方法については
を参考にしていただけたらと思います。
#include <iostream>
#include <vector>
using namespace std;
int main() {
/* 入力 */
int n; // 個数
int A; // 作りたい数
cin >> n >> A;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
// 全探索 --- bit は {0, 1, ..., n-1} の 2^n 通りの部分集合全体を動きます。
bool exist = false;
for (int bit = 0; bit < (1 << n); ++bit)
{
int sum = 0; // 部分集合の和
for (int i = 0; i < n; ++i) {
if (bit & (1 << i)) { // i が S に入っているなら足す
sum += a[i];
}
}
// sum が A に一致するか
if (sum == A) exist = true;
}
if (exist) cout << "Yes" << endl;
else cout << "No" << endl;
}
計算量オーダーですが、$2^n$ 通りの探索をしていて、それぞれ最悪 $n$ 個の足し算を実行するので $O(n2^n)$ になります。まごうことなき指数時間アルゴリズムです。発展的話題として、この問題に対して動的計画法を用いることで $O(nA)$ のアルゴリズムを作ることができます (リンク先で解説しています)。一見すると多項式時間アルゴリズムに見えるのですが、上の「例 10: 素数判定」で見た通り、$A$ は「個数」ではなく「数値」なので指数時間アルゴリズムです。このように「数値」についての多項式になっている指数時間アルゴリズムのことを擬多項式時間アルゴリズムと呼ぶことがあります。
例 12: 順列全探索 O(nn!)
またしても有名な巡回セールスマン問題を考えます。これも多項式時間アルゴリズムは存在しないだろうと広く信じられている NP 困難問題です。
$n$ 個を都市を、好きな都市から出発してちょうど一度ずつすべての都市を訪れる方法のうち、最短の所要時間を求める問題です。同じ都市を二度訪れてはダメです。単純に全探索すると $n!$ 通りの方法があります。以下の実装では $n!$ 通りすべて調べています。C++ の std::next_permutation() がちょうどよく使えます。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 100000000; // 十分大きな値
int main()
{
// 入力
int n; // 都市数
cin >> n;
vector<vector<int> > dist(n, vector<int>(n)); // 各都市間の所要時間
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> dist[i][j];
}
}
// 初期順列
vector<int> order(n);
for (int i = 0; i < n; ++i) order[i] = i;
// 探索
int res = INF;
do {
/* 順序 order についての所要時間を計算 */
int temp_dist = 0;
for (int i = 1; i < n; ++i) {
temp_dist += dist[order[i-1]][order[i]];
}
/* 暫定値より小さかったら更新 */
if (temp_dist < res) {
res = temp_dist;
}
} while (next_permutation(order.begin(), order.end()));
// 答えを出力
cout << res << endl;
}
計算量は、$n!$ 通りにつき $O(n)$ 個分足し算をしていることから $O(nn!)$ 通りになります。部分和問題に対する $O(n2^n)$ の全探索アルゴリズムよりさらにずっと悪い計算量オーダーになっています。
発展的話題として、通称 bit DP と呼ばれる動的計画法手法に基づいて $O(nn!)$ から $O(n^22^n)$ に改善することができます。詳しくはリンク先で解説を行っています。
例 13: ループの中で素数判定などの重い処理 O(n√n)
ここまでループの中の処理は軽くてループ回数さえ求めれば計算量オーダーが求まるような問題を中心に見て来ました。ここではループの中身の処理が重たい問題を見て行きたいと思います。具体的には、正の整数 $n$ が与えられて、
「$1$ から $n$ までの素数をすべて求める問題」
を考えます。まずは単純に $1$ から $n$ までの各整数について素数判定をするアルゴリズムを考えます。
#include <iostream>
using namespace std;
// 素数判定
bool is_prime(int n) {
if (n < 2) return false;
for (int i = 2; i*i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n; cin >> n; // 入力
for (int i = 1; i <= n; ++i) {
if (is_prime(i)) cout << i << endl;
}
}
計算量は、各ループ内の処理が $O(\sqrt{i})$ だけかかるので、合計ではざっくりと
\sqrt{1} + \sqrt{2} + \dots + \sqrt{n}
だけかかります。直感的には最悪 $\sqrt{n}$ かかる処理が $n$ 回なので計算量オーダーは $O(n\sqrt{n})$ になりそうです。厳密に示すには、高校数学で懐かしい「区分求積法」を用いて示すことができます。上記の和計算は $\sqrt{n}$ を積分するような計算を行っているため、$O(n\sqrt{n})$ になります。
例 14: エラトステネスのふるい O(n loglogn)
最後に、例 13 の「$1$ から $n$ までの素数をすべて求める」問題に対する $O(n\sqrt{n})$ の愚直なアルゴリズムを $O(n \log\log{n})$ に高速化します。エラトステネスのふるいと呼ばれています。アイディアは非常に単純です。例えば $n = 30$ だとすると、まず $2$ から $30$ までの整数をふるいにまとめて入れます:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
まず $2$ は素数なので $2$ だけ残して $2$ の倍数をふるい落とします:
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29]
次に、$2$ の次に残っている数 $3$ は素数になっていて、$3$ だけ残して $3$ の倍数をふるい落とします:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29]
... というのを繰り返すと最後に残るのは以下のようになります:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
このように、合成数を次々とふるい落としていくアルゴリズムです。実際上の実装では、ふるいはビットで管理し、ふるい落とす作業は「フラグを消す」ことで行います。
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int n; cin >> n; // 入力
// エラトステネスのふるい
bitset<1000000> is_prime(0); // 十分大きなサイズを確保します
for (int i = 2; i <= n; ++i) is_prime.set(i); // とりあえず全部ふるいに入れます
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) { // 素数 i を発見したら
for (int j = i * 2; j <= n; j += i) {
is_prime.reset(j); // i の倍数をふるい落とす
}
}
}
// 結果出力
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) cout << i << endl;
}
}
計算量解析が非常に面白いです。
- 2 の倍数をふるい落とすのに必要な計算ステップ数: $\frac{n}{2}$ 回
- 3 の倍数をふるい落とすのに必要な計算ステップ数: $\frac{n}{3}$ 回
- 5 の倍数をふるい落とすのに必要な計算ステップ数: $\frac{n}{5}$ 回
- …
となっていくので、合計計算ステップ回数は
\sum_{p は n 以下の素数}{\frac{n}{p}} = n (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \dots)
となります。ここで素数の逆数和は $O(\log\log{n})$ のオーダーで発散する (「素数の逆数和が発散することの証明」を参照) ということを思い返すと、エラトステネスのふるいの計算量オーダーは RAM (Random-access machine) モデル上で $O(n \log\log{n})$ になります。
3. どこから log が出て来るか
ここまで例を見て来た中で、計算量が $O(\log{n})$ になるアルゴリズムとしては
- 二進法展開
- 二分探索
- (例には登場していないが) 繰り返し二乗法 / ダブリング
がありました。3 つめの繰り返し二乗法とは、例えば $a^n$ の計算を効率良く実現できるアルゴリズムです。これらの 3 つのアルゴリズムはいずれも「$n$ が毎ステップごとに半分になる」という構造をしていました。より一般に「$n$ が毎ステップごとに定数分の１になる」場合の繰り返し回数は $O(\log{n})$ になります。
他に $O(\log{n})$ や $O(n\log{n})$ が登場する場面としては
- 二分木に類するデータ構造を使う (ヒープ、平衡二分探索木、セグメントツリーなど)
- ユークリッドの互除法を使う
- 分割統治法を使う (マージソートや最近点対問題など)
- 高速たたみ込み演算を使う (高速フーリエ変換 (FFT) など)
- ソートを前処理として使う (凸包や Kruskal 法など)
- $1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n} \simeq O(\log{n})$ であることを使う (大分マニアックです)
などが挙げられます。
4. 参考資料
さらに進んだ学習をする上で参考になる文献たちを挙げます:
気軽にわかりやすく計算量について知ることができます。
アルゴリズムの世界的教科書で、日本語では三巻に訳されています。そのうちの第一巻では「計算量」「ソート」「データ構造の初歩」について詳細に解説がなされています。オーダー記法の数学的取扱いがしっかりしています。
計算量理論について体系立ててとてもわかりやすく解説した書籍です。計算量理論へ入門するための書籍としてとてもよいです。
計算量理論に関する世界的入門書です。特に NP 完全問題に関する理論をきちんと理解できます。付録の NP 困難問題リストは「今直面している問題が NP 困難かもしれない」と感じたときに参照するととても便利です。
上の本は少し古い古典という感じですが、こちらは 2008 年出版と新しいです。分厚く内容が豊富で、高度な話題まで扱っています。
各計算量オーダーのアルゴリズムとしてどんなものがあるのかを、より詳細に紹介しているスライドです。
5. 付録
計算量に関する発展的トピックを紹介します。
5-1. ランダウの O 記法の詳細
冒頭で「極限」の概念を援用してざっくりと O 記法の概念を紹介したのですが、それだと通用しない場面もあるのでちゃんと定義します。
$T(n)$ と $P(n)$ を自然数 $n$ 上で定義された $2$ つの関数とします。このとき、$T(n) = O(P(n))$ であるとは、ある定数 $c$ とある自然数 $n_0$ が存在して、$n_0$ 以上の任意の自然数 $n$ に対して
0 \le T(n) \le c P(n)
が成り立つことをいいます。
特に冒頭で見たように $\lim_{n \to \infty} \frac{T(n)}{P(n)}$ が収束するときはこの性質を満たしますが、収束しなくても (例えば振動している場合など)、有界であればこの性質を満たします。
なおこの定義から、$O(n^2)$ アルゴリズムは $O(n^3)$ アルゴリズムでもあります。したがって「マージソートは $O(n^5)$ アルゴリズムです」と言っても、非常に誤解を招きやすいですが間違ってはいないです。
5-2. Ω 記法と Θ 記法
前節で見たように、$O$ 記法は計算量オーダーを上から抑える考え方でした。反対に下から抑える考え方として $\Omega$ 記法があり、上からも下からも抑える (ピッタリ評価する) 考え方として $\Theta$ 記法があります。しばしば本来は $\Theta$ 記法を使うとよい場面で $O$ 記法が慣用的に使われがちです。本記事でも慣用的に $O$ 記法を用いました。
5-3. 漸化式で表された計算量解析
$T(1) = O(1)$
$T(n) = aT(n/b) + O(n)$ ($n > 1$)
という漸化式で表された計算量が
T(n) = \left\{
\begin{array}{ll}
O(n) & (a < b) \\
O(n\log{n}) & (a = b) \\
O(n^{\log_{b}{a}}) & (a > b)
\end{array}
\right.
となることの略証を示します。まず簡単のために漸化式を定数 $c$ を用いて
$T(1) = c$
$T(n) = aT(n/b) + cn$ ($n > 1$)
とします。さらに簡単のために $n = b^k$ として漸化式を繰り返し用いると
$T(n) $
$= aT(\frac{n}{b}) + cn$
$= a(aT(\frac{n}{b^2}) + \frac{cn}{b}) + cn$
$= \dots$
$= a(a(\dots a(aT(\frac{n}{b^k}) + c\frac{n}{b^{k-1}}) + c\frac{n}{b^{k-2}}) + \dots) + \frac{cn}{b}) + cn$
$= ca^k + cn(1 + \frac{a}{b} + (\frac{a}{b})^2 + \dots + (\frac{a}{b})^{k-1})$
$= c(n^{\log_{b}{a}} + n(1 + \frac{a}{b} + (\frac{a}{b})^2 + \dots + (\frac{a}{b})^{k-1}))$
になります。よって、
- $a < b$ のとき、$1 + \frac{a}{b} + (\frac{a}{b})^2 + \dots + (\frac{a}{b})^{k-1} = \frac{1 - (\frac{a}{b})^{k} }{1 - \frac{a}{b}}$ は $n \to \infty$ で収束するので $T(n) = O(n)$
- $a = b$ のとき、$T(n) = cn(k+1) = O(n\log{n})$
- $a > b$ のとき、$n(1 + \frac{a}{b} + (\frac{a}{b})^2 + \dots + (\frac{a}{b})^{k-1}) = n\frac{(\frac{a}{b})^{k} - 1}{\frac{a}{b} - 1} = O(a^k - n) = O(n^{\log_{b}{a}})$ であることから、$T(n) = O(n^{\log_{b}{a}})$
となります。
5-4. 時間計算量以外の計算量について
本記事では「計算量」の指標として時間計算量 (time complexity) のみに焦点を当てました。実際には計算量と呼ばれるものには他に
- 領域計算量 / 空間計算量 (space complexity、いわゆるメモリ消費量)
- 通信計算量 (communication complexity、並列計算が重要な現代では重要な概念です)
- 回路計算量 (circuit complexity)
などがあります。時間計算量のみの観点にとらわれず、様々な視点から「計算の本質」を追求して行くのが、計算複雑性理論であると言えます。
5-5. 計算量の概念を数学的にきっちりとしたい方へ
特に数学畑の人であれば気になることだと思います。
本記事では計算ステップ回数というものをざっくりと for 文や while 文のループ回数と考えて計算量オーダーを議論しました。結局それで特に問題はないのですが、やはり数学的にきっちりと定義したいと感じる方も多いと思います。そのためには
- チューリングマシン (TM) を用いて「計算」というものをきちんと定義する
- 「問題」の計算可能性について、きちんと議論する
- ランダムアクセスマシン (RAM) を定義して、その下で「計算の 1 ステップ」を定義する
といった根本的な事柄を議論することになります。参考資料に挙げた書籍たちを学ぶことで、この辺りの事情をスッキリと整理できると思います。
5-6. P ≠ NP 予想
計算量理論において重要な未解決問題である「P ≠ NP 予想」については、以下の記事に整理しました:
6. むすび
今回は計算量オーダーという概念の解説から始まり、様々なアルゴリズムの計算量解析、周辺トピックの紹介を行いました。次の記事では実際に「愚直なアルゴリズム」の計算量オーダーを改善して高速化する事例をいくつか紹介します。