ラボラジアン 目次
1. アルゴリズムの計算量
探索アルゴリズムやソートアルゴリズムを勉強すると、「計算量」という言葉が出てきます。
計算量を簡単に説明すると、
です。
もう少し説明を加えると、
となるため、「\(n\) の増加に対する計算量の増加の程度を表す式」であるとも言えます。
アルゴリズム内における命令には、いろいろな種類があるはずですが、「\(n\) が十分大きい場合の命令数の規模」を考える場合は、「\(n\) の増加に伴って、一番増え方の程度が大きい命令の数」を考えればよいと考えます。それ以外の命令や、式にしたときの係数などは無視することができます。
ということで、計算量は「命令数の規模（増え方の規模）」ですが、実際には「計算に必要な時間」と捉えて考えることが多いです。
表記方法
この計算量を表記するには、
という形で記述します。
※ \(O\) は order の頭文字で、Wikipedia には「程度」という意味だと書いてありますが、「次数」という意味でも良さそうです。
例えば、\(O(n) \) であれば、「オーダー \(n\) のアルゴリズム」と呼ぶことができます。
では、ランダウの記号 – Wikipedia に載っているアルゴリズム（一部だけですが）の計算量を見ていきます。 ※ クイックソートだけは独自に選びました。
2. \(O(1) \)
アルゴリズムの例：（整数の）偶奇判別
整数が偶数か奇数か判別する場合、対象となる1つ数について調べるだけなので、\(O(1)\) となります。
3. \(O(\log n) \)
アルゴリズムの例： ソート済み配列における二分探索
ソート済みの配列に対する二分探索というのは、
- 対象となる値全体を半分にする
- 目的の値が入っている方を、更に半分にする
- 目的の値が入っている方を、更に半分にする
- …
を繰り返し、最終的に目的の値に到達するアルゴリズムです。
\(n\) 個の数に対して \(\frac{1}{2}\) → \(\frac{1}{2}\) → \(\frac{1}{2}\) → \(\frac{1}{2}\) と範囲を狭くするため、「\(n\) を \(k\) 回 \(\frac{1}{2}\) して、値を1つに絞る」と考えると、 \(n \times \frac{1}{ 2^{k}} = 1\) という式が書けます。これを変形すると \(n = 2^{k}\) となりますが、「2 を \(k\) 乗すると、 \(n\) になる」を対数で書くと \(\log_2 n = k \) です。\(\frac{1}{2}\) を実行した回数 k が、この場合の計算量であるので、\(O(\log_{2} n)\) と表すことができます。
4. \(O(n) \)
アルゴリズムの例： 非ソート配列上の探索
ソートされていない配列から目的の値を探すということなので、\(n\) 個の要素があるなら、\(n\) 個すべてをチェックしていくことになります。\(n\) 回の命令なので、計算量は \(O(n)\) です。
5. \(O(n \log n)\)
アルゴリズムの例： クイックソート
クイックソートは、おおまかに言うと 以下の操作を行うアルゴリズムです。
- ある数より大きいか小さいかで、\(n\) 個を2つのグループに分ける（このとき、\(n\) 個すべてにアクセスして判別処理する必要があります）。
- それぞれのグループに対して、同じ操作を行います。
- \(n\) 個すべての大小関係が決まるまで、この操作を繰り返します。
\(n\) 個が 1つになるまで、\(\frac{1}{2}\) する場合に必要な回数は、\(\log_2 n\) 。グループ分けする度に、各要素を判定しなければいけないので、グループ分けした階層毎に \(n\) 回の判定処理が必要。よって、以下の図から、計算量は \(O(n \times \log_2 n)\) となります。
※ この図は、[改訂新版]C言語による標準アルゴリズム事典 (Software Technology) に載っています（少なくとも、改定前のには載っていました）
6. \(O(n^2)\)
アルゴリズムの例： 挿入ソート
クイックソートは、\(n\) 個の数に対して 左端からソート済みのかたまりを作っていくアルゴリズムです。 (参照：挿入ソート – Wikipedia）
- 左端から見て2つ目の要素から右端の要素まで順番に処理する。
- \((n – 1)\)回の処理になる
- 1のループ処理内では、既にソート済の配列（最大 \((n – 1)\)個）を順番に見ていき、大小関係が成立する位置に現在処理対象の数を挿入する。
\((n – 1)\) 個の要素に対して、最大 \((n – 1)\) 個の中から位置を見つけるので、\((n – 1) \times (n – 1) = n^{2} -2n + 1\) となり、一番次数の大きい項だけ見ると、計算量は \(O(n^{2})\) となります。
7. 計算量のグラフ
取り上げた計算量をグラフにして比較します。
\(n\) の増加に対する計算量の増え方に注目してください。「\(n\) が増えても計算量がなるべく増えない」アルゴリズムが望まれます。
