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

アルゴリズム概要入門

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

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

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

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

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

計算量の評価には「漸近記法」と呼ばれるものが使われます。「オーダー記法」「ラウダウの記号」などと呼ばれることがあります。数学的に厳密な定義は本サイトの意図とズレてしまうので、まずは大雑把な意味だけ書いておきましょう。入力の大きさに対して、計算量がどれくらいの大きさになるのかを数式で表したもので、

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

という特徴があります。

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

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\)を関数とします。数式がよく分からなければ、意味と具体例を中心に見てもらえれば大丈夫です。

ビッグ・オー

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

ビッグ・オメガ

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

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

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

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

ビッグ・シータ

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

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

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

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

アルゴリズム概要入門

Posted by cs-learner