O(mn) 比 O((m+n)^2) 好吗? [英] Is O(mn) better than O((m+n)^2)?

问题描述

算法的输入是m和n.

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

The time complexity of my algorithm comes out to be O(mn).

我有一个时间复杂度为 O((m+n)²) 的基准算法.

I have a benchmark algorithm that has a time complexity of O((m+n)²).

我的实现在时间复杂度方面是否优于基准测试?

Is my implementation better than the benchmark in terms of time complexity?

推荐答案

很多评论者和回答者希望只考虑 m = n 或至少当它们通过一个常数因子相关时的情况.事情不是这样的.

So many commenters and answerers wish to consider only the case when m = n or at least when they are related by a constant factor. That is not how this works.

当我们保持 m 或 n 常量时，你的算法显然更快；例如，如果我们将自己限制在 m = 1 的情况下，那么算法的复杂度是 O(n) 而替代方案是 O(n^2)，所以在这个受限的情况下，你的显然更好.

Your algorithm is clearly faster when we hold either m or n constant; for example, if we restrict ourselves to the case m = 1 then the complexity of your algorithm is O(n) whereas the alternative is O(n^2), so yours is clearly better in this restricted case.

我们可以说的是，(m+n)^2 = m^2 + n^2 + 2mn 显然是 Ω(mn) 其中 Ω 表示这是一个下界，并且您的算法(渐近)始终至少一样好；即，没有其他算法渐近优于您的算法的限制情况.但是我们确实知道在某些情况下您的情况更好.所以，总的来说，你的更好.

What we can say is that (m+n)^2 = m^2 + n^2 + 2mn is clearly Ω(mn) where Ω means this is a lower bound, and your algorithm is (asymptotically) always at least as good; i.e. there are no restricted cases where the other algorithm is asymptotically better than yours. But we do know there are restricted cases where yours is better. So, overall, yours is better.

这篇关于O(mn) 比 O((m+n)^2) 好吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！