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