漸近記法の定義とアルゴリズムの計算量の解析

2019年11月20日アルゴリズム概要入門

なぜアルゴリズムを解析する必要があるのか

プログラムを書く際は、読みやすく・保守が容易で・使いやすいものになるように注意しながら書く必要があります。なぜアルゴリズムの計算量を見積もる必要があるのでしょうか。

その答えは単純で、コンピュータのリソースにも限界があるからです

私達は時間やメモリという限られた資源を使って計算を行います。パフォーマンスが悪ければ、アルゴリズムを実行することができなかったり、できても終了するのが何百万年後になったりしてしまいます。

コンピュータの処理能力は年々と進化していますが、処理するデータやアルゴリズムの複雑さもその分増えています。一瞬で計算をしているように見えるコンピュータも、実際には限られたプロセッサやメモリを使用しているのです。

計算量の評価に使われる漸近記法

計算量の評価には「漸近記法」と呼ばれるものが使われます。「オーダー記法」「ラウダウの記号」などと呼ばれることがあります。

数学的に厳密な定義は本サイトの意図とズレてしまうので、まずは大雑把な意味だけ書いておきましょう。入力の大きさに対して、計算量がどれくらいの大きさになるのかを数式で表したもので、

  • 影響力の大きい(次数の大きい)項以外は無視する
  • 定数倍の差は無視する

という特徴があります。

具体的に書いてみましょう。例えば以下のようなループを含んだプログラムがあるとします。

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)\) である」とか言うこともあり、これは基本的にはビッグ・オーのことを表します。

※2つ目の具体例は、1つ目の例と「 \(2n^2+n+2\) 」の部分が同じですが、「 \(n^5\) より計算量が大きくなることはない」ということを表しているので正しいものです。もちろん1つ目よりも意味的に弱くなります。

ビッグ・オメガ:\(\Omega\)

数式: \(f(n) = \Omega (g(n))\)
意味: 十分大きな \(n\) について、定数倍を無視すれば \(f(n)\) の値は \(g(n)\) が下限となる

具体例: \(2n^2+n+2 = \Omega (n^2)\)、\(2n^2+n+2 = \Omega (n)\)

「ビッグ・オー」とはある意味逆の記号です。

「どれだけ理想的な入力が来ても計算時間はこれ以上早くならない」というのが見積もれます。

※2つ目の具体例は、1つ目の例よりも意味的に弱いものです。

ビッグ・シータ:\(\Theta\)

数式: \(f(n) = \Theta (g(n))\)
意味: 十分大きな \(n\) について、定数倍を無視すれば \(f(n)\) の値は \(g(n)\) が上限にも下限にもなる

具体例: \(2n^2+n+2 = \Theta (n^2)\)

「ビッグ・オー」「ビッグ・オメガ」を合わせた記号です。

「理想的な入力でも最悪の入力でも、計算量が大体このくらい」というのが見積もれます。