今回は、アルゴリズムとデータ構造を扱う上で、重要な計算量についての解説です。
アルゴリズムとは
アルゴリズム（Algorithm）とは、問題を解くための有限の操作手順で必ず有限の手順で終了し、答えが得られるものです。ここで、手順とは加算、乗算、条件分岐などの命令を指します。これらを組み合わせて得られる一連の処理（命令系列）のことをアルゴリズムと本ページでは呼びます。
ここで、重要なことは「有限の手順で終了」ということです。一般に命令系列はループ処理を含むため、有限の手順で停止するとは限りません。このようなものも含める場合は、「手続き（Procedure）」と呼ばれます。
計算量
ある問題を解くアルゴリズムに対して、入力系列を入れると、有限の手順で正しい答えが出力される。しかし、実用上の観点から単に有限の手順で停止するだけではなく、どの程度の多さの手順で停止するか、ということも重要になってきます。高速に動作するアルゴリズムを構築するためには、効率よく動作するアルゴリズムを考える必要があります。
この「アルゴリズムの効率性」を定量的に評価するために計算量という概念があります。
以下2つのをまとめたものを計算量（Computational Complexity）と呼びます。
- 計算時間（Time Complexity）
- アルゴリズムの実行に必要な時間を評価する指標。 アルゴリズムの手順数は、計算の実行時間と直接関係している。 基本演算を１手順（加減乗除、代入、条件判定、論理演算など）として考える。
- 領域量（Space Complexity）
- アルゴリズムの実行に際し、どの程度のメモリを必要とするかを評価する指標。
アルゴリズムの設計時には、計算時間と領域量のトレードオフなどを考えて、アルゴリズムを設計します。領域量よりも計算時間のほうが課題となることが多いです。そのため、書籍やWebページによっては計算時間のことのみを計算量として説明を進めているものもあります。
このアルゴリズムの効率さを定量的に評価する指標の一つとしてO（オーダー）記法があります。
オーダー記法の定義は以下です。
ある正定数\(c\)と\(n_0\)が存在し、\(n_0\)以上の\(n\)に対し常に
$$T(n)\leq cf(n)$$
が成立する。計算量の上階値を評価するとき、\(T(n)=O(f(n))\)という記法を用いて、オーダー\(f(n)\)と読む。難しく書いていますが、簡単にいうと、\(n\)が十分大きい時にどのような\(n\)の基本的な関数になるかを見たい、ということです。
例：
$$O(2.5n^2) = O(n^2)$$
$$O(n^2+50000n+1000) = O(n^2)$$
このように、オーダ表記では、簡単な関数に書き直し、アルゴリズムの効率さを評価します。
特に\(O(1)\)は定数オーダーと呼ばれ、\(n\)に独立なある定数で抑えられることを意味します。この定数オーダーの時間量を簡単に定数時間とも言います。
オーダー表記は、関数の細部を無視し、\(n\)を十分大きくした場合の挙動を見る場合に特に有効です。
オーダー記法として、よく現れる関数の挙動を見てみます。
$$O(\log \log n) < O(\log n) < O(\log_k n) < O(n^{\frac{1}{k}}) < O(n)$$
$$O(n) < O(n\log n) < O(n^k) (k>1)< O(n^{\log n})< O(2^n) < O(n!)$$
| n=2 | n=10 | n=100 | n=1000 | n=5000 | |
|---|---|---|---|---|---|
| \(O(\log \log n)\) | 0.0 | 1.73 | 2.73 | 3.31 | 3.61 |
| \(O(\log n)\) | 1.0 | 3.32 | 6.64 | 9.96 | 12.28 |
| \(O(n^{\frac{1}{2}})\) | 1.41 | 3.16 | 10.0 | 31.62 | 70.71 |
| \(O(n)\) | 2 | 10 | 100 | 1000 | 5000 |
| \(O(n \log n)\) | 2.0 | 33.21 | 664.3856189774724 | 9965.784284662088 | 61438.56189774724 |
| \(O(n^2)\) | 4.0 | 100.0 | 10000.0 | 1000000.0 | 25000000.0 |
| \(O(n^{\log n})\) | 2.0 | 2098.592395866662 | 19396009115566.36 | 7.89e+29 | 2.83e+45 |
| \(O(2^n)\) | 4.0 | 1024.0 | 1.26e+30 | – | – |
| \(O(n!)\) | 2 | 3628800 | 9.33e+157 | – | – |
表より、\(O(n^\frac{1}{2}), O(log n), O(n \log n)\)などのアルゴリズムは\(n\)が増加しても、計算量がそれほど大きくならないことがわかります。
一方で、オーダーが\(O(2^n), O(n!)\)のアルゴリズムは、\(n\)が少し増加するだけで計算量が大幅に増加してしまいます。
アルゴリズムを考える上で、「このアルゴリズムの計算量はいくら」ということを意識する必要があります。
まとめ
アルゴリズムを考える上で、計算量を考慮することは非常に大事です。
特に、アルゴリズムが\(O(2^n)\)以上であれば、指数関数的に計算量が多くなるため、注意しましょう。
コメント