O(mn) 比 O((m+n)^2) 好吗？

Question

算法的输入是m和n。

我的算法的时间复杂度为O(mn).

我有一个时间复杂度为O((m+n)²).

在时间复杂度方面，我的实现是否比基准测试更好？

Answer 1

如此多的评论者和回答者希望只考虑当m = n或至少当他们通过一个常数因子相关时的情况。这不是它的工作原理。

当我们保持m或n保持不变时，您的算法显然更快；例如，如果我们将自己限制在这种情况下，m = 1那么您的算法的复杂性是，O(n)而替代方案是O(n^2)，因此在这种受限制的情况下，您的算法显然更好。

我们可以说的是，(m+n)^2 = m^2 + n^2 + 2mn显然是?(mn)其中?的手段，这是一个下限，而你的算法是（渐近）总是至少为好; 即，没有其他算法渐近优于您的算法的限制情况。但是我们确实知道在某些情况下您的情况更好。所以，总的来说，你的更好。