algorithm - 这个运行时间多项式是输入大小吗？

Question

某个算法的输入大小为n^2+n*m。它的运行时间是 O(m*n^3)。运行时间可以被认为是输入大小的多项式吗？

Answer 1

是的。它运行在O(max{n,m}^4)，这是输入的多项式时间，小于O(max{n^2,n*m}^2)，这是输入大小的二次方。

注意：这假设输入是 SIZE n^2+n*m，而不是这个“大小”的数字- 因为数字可以表示为log(n^2+n*m)位，这只会得到一个伪多项式解决方案。

Answer 2

如果 S 中有一个多项式是 T(n,m) 的上界，则运行时间 T(n,m) 被称为输入大小 S(n,m) = n^2+n*m 的多项式.

考虑多项式 S^2(n,m) = (n^2+n*m)^2 = n^4 + 2(n^2)n*m + (n^2)(m^2)。由于 n^4 和 (n^2)(m^2) 是正整数的平方，它们是正数，所以 S^2(n,m) > 2(n^2)n*m > n^3 * m。

由于 T(n,m) 是 O(n^3 * m) 并且 S^2(n,m) > n^3 * m 我们有 T(n,m) 是 O(S^2(n,m) ) 因此运行时间受输入大小的多项式限制。