About: 多項式時間

多項式時間（たこうしきじかん）とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズに対して、処理時間の上界としての多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数に対して要素の比較・交換を行う回数は高々 である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてと表される。 またクイックソートの期待計算量のオーダーは、最悪計算量のオーダーはである。