多項式時間のソースを表示

'''多項式時間'''（たこうしきじかん）とは[[計算理論]]において[[多項式]]で表される計算時間。

多項式時間のアルゴリズムとは、解くべき問題の入力サイズ<math>n</math>に対して、処理時間の上界として<math>n</math>の多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。

たとえば[[バブルソート]]の処理時間は要素数<math>n</math>に対して要素の比較・交換を行う回数は高々 <math>\frac {1}{2}n(n-1)</math> である。したがって、この場合の最悪計算量のオーダーは[[O記法]]を用いてO<math>({n^2})</math>と表される。 また[[クイックソート]]の期待計算量のオーダーはO<math>(n \log n)</math>、最悪計算量のオーダーはO<math>({n^2})</math>である。

==定義==
多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。

===多項式時間アルゴリズム===
Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは'''多項式時間アルゴリズム'''であるという
:ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。

なお「多項式時間アルゴリズム」と言った場合、決定性アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、[[確率的アルゴリズム]]をも許す場合とがある。

===多項式時間アルゴリズムが存在する問題とクラスP===

決定性の多項式時間アルゴリズム（上で定義した）で解ける'''判定問題'''の集合をクラス'''[[P (計算量理論)|P]]'''と呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。

==関連項目==
* [[計算量理論]]
* [[定数時間]]
* [[指数関数時間]]
* [[多項式時間変換]]
* [[凖指数関数時間]]
* [[時間計算量]]

[[Category:計算複雑性理論|たこうしきしかん]]
[[Category:時間|たこうしき]]
[[Category:数学に関する記事|たこうしきしかん]]

[[en:Time complexity#Polynomial time]]