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