漸近記法の定義とアルゴリズムの計算量の解析
なぜアルゴリズムを解析する必要があるのか
プログラムを書く際は、読みやすく・保守が容易で・使いやすいものになるように注意しながら書く必要があります。なぜアルゴリズムの計算量を見積もる必要があるのでしょうか。
その答えは単純で、コンピュータのリソースにも限界があるからです。
私達は時間やメモリという限られた資源を使って計算を行います。パフォーマンスが悪ければ、アルゴリズムを実行することができなかったり、できても終了するのが何百万年後になったりしてしまいます。
コンピュータの処理能力は年々と進化していますが、処理するデータやアルゴリズムの複雑さもその分増えています。一瞬で計算をしているように見えるコンピュータも、実際には限られたプロセッサやメモリを使用しているのです。
計算量の評価に使われる漸近記法
計算量の評価には「漸近記法」と呼ばれるものが使われます。「オーダー記法」「ラウダウの記号」などと呼ばれることがあります。
数学的に厳密な定義は本サイトの意図とズレてしまうので、まずは大雑把な意味だけ書いておきましょう。入力の大きさに対して、計算量がどれくらいの大きさになるのかを数式で表したもので、
- 影響力の大きい（次数の大きい）項以外は無視する
- 定数倍の差は無視する
という特徴があります。
具体的に書いてみましょう。例えば以下のようなループを含んだプログラムがあるとします。
for i range(n):
for j range(n):
# ここでなにか処理を行うこのような時に、計算時間（コンピュータが命令を実行する回数）がピッタリ \(n^2\) などになることは稀です。\(2n^2+n+2\) とかの時間がかかったりします。
「漸近記法」である「ビッグ・オー」を用いると、この計算時間を大体で見積もることができるので便利です。例えば今回では、$$2n^2+n+2 = O(n^2)$$ などと表すことができるのです。
つまり、一番大きい \(n^2\) 以外の項を無視して、\(n^2\) の係数である \(2\) も無視すると、「入力サイズ \(n\) が非常に大きい時に計算量がどの様に変化するか」を大体で表すことができます。
なぜなら、\(n\) が無限大に近いほど \(n^2\) の項が寄与する部分が大きくなり、他の項は比較的小さく無視できるからです。
漸近記法の種類
漸近記法にも種類があります。アルゴリズムを学ぶ上では以下の3つを知っておけば良いでしょう。以下では、\(f,g\) を関数とします。数式がよく分からなければ、意味と具体例を中心に見てもらえれば大丈夫です。
ビッグ・オー：\(O\)
数式: \(f(n) = O(g(n))\)
意味: 十分大きな \(n\) について、定数倍を無視すれば \(f(n)\) の値は \(g(n)\) が上限となる
具体例: \(2n^2+n+2 = O(n^2)\)、\(2n^2+n+2 = O(n^5)\)
先ほども出てきた記号です。計算量の話をする際に一番よく使われるので、とりあえずこれだけは覚えてください。
「最大でも計算時間はこれくらい」というのが分かりやすいので、アルゴリズムの計算量を実際に見積もる際によく使われます。「オーダーが \(g(n)\) である」とか言うこともあり、これは基本的にはビッグ・オーのことを表します。
※２つ目の具体例は、１つ目の例と「 \(2n^2+n+2\) 」の部分が同じですが、「 \(n^5\) より計算量が大きくなることはない」ということを表しているので正しいものです。もちろん１つ目よりも意味的に弱くなります。
ビッグ・オメガ：\(\Omega\)
数式: \(f(n) = \Omega (g(n))\)
意味: 十分大きな \(n\) について、定数倍を無視すれば \(f(n)\) の値は \(g(n)\) が下限となる
具体例: \(2n^2+n+2 = \Omega (n^2)\)、\(2n^2+n+2 = \Omega (n)\)
「ビッグ・オー」とはある意味逆の記号です。
「どれだけ理想的な入力が来ても計算時間はこれ以上早くならない」というのが見積もれます。
※２つ目の具体例は、１つ目の例よりも意味的に弱いものです。
ビッグ・シータ：\(\Theta\)
数式: \(f(n) = \Theta (g(n))\)
意味: 十分大きな \(n\) について、定数倍を無視すれば \(f(n)\) の値は \(g(n)\) が上限にも下限にもなる
具体例: \(2n^2+n+2 = \Theta (n^2)\)
「ビッグ・オー」「ビッグ・オメガ」を合わせた記号です。
「理想的な入力でも最悪の入力でも、計算量が大体このくらい」というのが見積もれます。