計算複雑性理論
シンプルな例として、ある問題に対する解法が nビットの入力に対して、ある計算モデルで n ステップで動作する場合、時間計算量は n であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、O記法を使えば計算モデルによらず問題の時間計算量をO(n) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を二分探索する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
空間計算量は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にもO記法が使われる。
計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば回路計算量がある。これは問題の解法をブール論理による論理回路ゲートに置き換え、その回路の規模で計算量を現すものである。これは集積回路の設計などで利用される。
計算問題の複雑性(または計算量)とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。