多項式時間
提供: miniwiki
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。
多項式時間のアルゴリズムとは、解くべき問題の入力サイズ[math]n[/math]に対して、処理時間の上界として[math]n[/math]の多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。
たとえばバブルソートの処理時間は要素数[math]n[/math]に対して要素の比較・交換を行う回数は高々 [math]\frac {1}{2}n(n-1)[/math] である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いて[math]O({n^2})[/math]と表される。 またクイックソートの期待計算量のオーダーは[math]O(n \log n)[/math]、最悪計算量のオーダーは[math]O({n^2})[/math]である。
定義
多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。
多項式時間アルゴリズム
Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという
- ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。
なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。
多項式時間アルゴリズムが存在する問題とクラスP
決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。