多項式時間
出典: フリー百科事典『ウィキペディア（Wikipedia）』
多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。
多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。求解にかかる時間というよりも、問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。
たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 
である。したがって、この場合の最悪計算量のオーダーはO記法を用いてO(n2)と表される。 またクイックソートの期待計算量のオーダーはO(nlogn)、最悪計算量のオーダーはO(n2)である。
目次 |
[編集] 定義
多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。
[編集] 多項式時間アルゴリズム
Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという
- ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。
なお「多項式時間アルゴリズム」と言った場合、決定性アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。
[編集] 多項式時間アルゴリズムが存在する問題とクラスP
Mを問題とする、問題は問題例（通常は実際の入力データを意味する）の集合として定義される。 次が満たされる時、問題Mは多項式時間で解けるという： あるアルゴリズムAとある多項式l(k)が存在して、任意の問題例m∈Mに対し、問題例mの入力サイズをkとすると、Aにmを入力したときAは問題例mの答えをl(k)ステップ以内に出力する。
決定性アルゴリズムで多項式時間で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。
