この記事での学習内容 基本情報 応用情報

計算量の理論の考え方を理解する。

用語例：時間計算量、領域計算量、オーダ記号、P(Polynomial)問題、NP(Non-deterministic Polynomial)問題、NP完全問題

計算量

ある問題を解く場合に、問題を解く手順（＝アルゴリズム）は複数存在します。例えば、以下のような単純な掛け算を取ってみても、複数の計算方法があります。
例）3×1977

• ３を1977回足す
• 1977を3回足す

この例の場合、明らかに1977を3回足すほうが計算の回数が少なく、優れた解法といえます。

この例のように、問題を解くためのアルゴリズムは一つとは限らず、いくつかあるアルゴリズムから最良のものを選ぶためには、アルゴリズムを定量的に評価する指標が必要となります。この指標が「計算量」と言われるものです。
アルゴリズムに基づいて処理するデータ量によって、プログラムの実行時間がどのように変化するかを表し、アルゴリズムの複雑さをはかることが出来ます。
時間計算量はあるアルゴリズム手順（＝処理手順）の数と繰り返し回数の最大数で表すことが出来ます。

解く問題の種類によっては、計算量が一定でない場合があります。例えば検索処理です。

検索処理では場合によっては、処理開始直後に見つけられることもあれば、最後の最後で見つかることもあります。このような一定でない計算量を表現するために、最大計算量と平均計算量という考え方もあります。それぞれ、計算量の最大値と平均値を示すものです。
計算量の代表値としては、平均計算量のほうが適切ですが、平均計算量は算出が難しい場合があり、最大計算量で評価することも多くあります。

時間計算量の他に、「領域計算量」も評価指標として使うことがあります。この場合は使用するメモリの容量を指標とし、より使用メモリの少ないアルゴリズムを良いアルゴリズムとしてみなすものです。
但し、現在はメモリが大容量化、かつ低価格化しているので、時間計算量がより優先される傾向にあります。

オーダ記法

良いアルゴリズムを考える場合に、「実行速度が早い」という点は大変重要ですが、実際の速度というのはコンピュータの性能によって異なってきます。
そこで、実行にかかる時間の目安を「時間計算量」として計算して評価します。その際に時間計算量は「O（オーダ）」という記号を使って表します。この表記法を「オーダ記法」といいます。