algorithm - 恒定时间的伪多项式

Question

伪多项式意味着它是关于输入大小的多项式，但关于输入大小的指数。所以在背包中，O(nW) 被认为是伪多项式。我看到有些人称 nx 或 ny，几乎所有带有 n 的东西都称为伪多项式，因为当 n 变大时，他们会更多地考虑 n 的位长度。那么，任何具有可以被认为是多项式大小的变量的东西实际上都是伪多项式的吗？

Answer 1

如果您输入的是单个数字，例如 "is the number x a prime number" ，则 O(x)(或 O(sqrt(x)) 是伪多项式 - 输入大小为 O(logx)情况下，所以 x 中的多项式并不意味着输入大小中的多项式。

但是，如果您的输入是一个数组，包含 n 个元素，那么输入长度本身在 n 中是线性的，并且 O(n) 表示多项式而不是伪多项式。