「計算複雑性理論」の版間の差分

[[アルゴリズム]]の'''計算量'''（けいさんりょう）とは、[[計算機]]がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムの[[スケーラビリティ]]を示す。形式的には計算機を[[チューリング機械]]や[[即時呼出機械]]（{{lang|en|random access machine}}）などの[[計算模型|計算モデル]]として定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する[[関数 (数学)|関数]]として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視する[[ランダウの記号|O記法]]で書き表すことが多い。計算モデルとしては、[[チューリング機械]]や[[論理回路]]などがある。計算資源の量としては、チューリング機械における'''時間計算量'''（動作動ステップ数）や'''空間計算量'''（テープ長）、また論理回路における素子数や深さなどがある。

* '''時間計算量'''は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が ''n''ビットの入力に対して、ある計算モデルで ''n''² ステップで動作動する場合、時間計算量は ''n''² であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、[[ランダウの記号|O記法]]を使えば計算モデルによらず問題の時間計算量をO(''n''²) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を[[二分探索]]する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。