O(nm + n2 log n) 复杂时间多项式时间？

Question

如果算法在 O(nm + n^2 log n) 时间内计算。那么你能说它是在多项式时间内计算的吗？

我知道 O(n log n) 是 O(n^2) 所以多项式时间。只是不确定 n^2 是如何工作的..

Answer 1

记住 O(n) 意味着 "upper-bounded"。如果函数 T(n) 是 O(n)，则 n*T(n) 是 O(n²).

当然，您也可以将 T(n) 乘以其他某个 O(n) 的函数 --- 不一定是 f(n)=n。所以 T(n)*O(n) 也是 O(n²).

如果您知道 O(n logn) 是 O(n²)，那么您可以将两者乘以一个 O(n) 的函数并得出结论O(n² logn) 是 O(n³)，这是多项式。

最后，如果O(a)、O(b)和O(c)都是多项式，那么O(a+b+c)也是多项式。因为他们都可以upper-bounded按增长更快的术语