algorithm - 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) 其中 Ω 表示这是一个下限，您的算法(渐近地)总是至少一样好；即没有其他算法渐进地优于您的算法的限制情况。但我们确实知道在有限的情况下你的更好。所以，总的来说，你的更好。