一定時間の擬ポリモニアル

Question

偽多項式は、入力の大きさに対して多項式であるが、入力のサイズに対して指数関数的であることを意味します。したがって、ナップザックでは、O（nW）は擬多項式とみなされます。 nが大きくなると、nのビット長をもっと考慮する必要があるため、nとnyと呼ぶ人もいます。その多項式とみなせる変数を持つものは、実際には擬多項式であるということは本当ですか？

Answer 1

あなたの入力は、単一の番号であれば、"is the number x a prime number"のように、その後、O(x)（またはO(sqrt(x))は擬似多項式である - 。入力サイズは、この場合にO(logx)ので、xの多項式は、入力サイズに多項式を意味するものではありません

しかし、入力が配列の場合、n要素では、入力の長さはnで線形であり、O(n)は擬似多項式ではない多項式を意味します。