多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。多項式時間のアルゴリズムとは、解くべき問題の入力サイズformula_1に対して、処理時間の上界としてformula_1の多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。たとえばバブルソートの処理時間は要素数formula_1に対して要素の比較・交換を行う回数は高々 formula_4 である。したがって、この場合の最悪計算量のオーダーは"O"記法を用いてformula_5と表される。 またクイックソートの期待計算量のオーダーはformula_6、最悪計算量のオーダーはformula_5である。多項式時間アルゴリズムと多項式時間アルゴリズムが存在する問題クラスについて、簡単に記す。Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるというなお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。決定的な多項式時間アルゴリズム（上で定義した）で解ける判定問題の集合をクラスPと呼ぶ（判定問題以外の問題はクラスPに含まれないことに注意）。

出典:wikipedia