多項式時間
多項式で表されるような計算時間
計算量
の話
指数時間
と対の概念として用いられる
わざわざ「多項式時間」という単語を持ち出すときは、「(
指数時間
ではなく)多項式時間で〜」という暗黙の前提を強調している感がある
mrsekut.icon
多項式時間アルゴリズムとは
入力サイズ
$ n
に対して、高々
$ n
の多項式で表現できるようなアルゴリズム
ex.
$ O(n)
、
$ O(n^3)
指数時間
に比べるとだいぶ小さい
参考
多項式時間 - Wikipedia