某算法的输入大小为n^2+n*m。它的运行时间是 O(m*n^3)。运行时间可以被认为是输入大小的多项式吗？
最佳答案
是的。它在 O(max{n,m}^4) 中运行，这是小于 O(max{n^2,n*m}^2) 的输入的多项式时间)，它是输入大小的二次方。
注意:这假设输入是 SIZE n^2+n*m，而不是这个“大小”的数字 - 因为数字可以表示作为 log(n^2+n*m) 位，这只会让你得到一个 pseudo-polynomial解决方案。
关于algorithm - 这是输入大小的运行时间多项式吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13034058/