我有一个这样的算法： O((m^2)/n) + O(mn)
我想知道：它是否等于O(mn)？
O((m^2)/n) > O(mn)或O((m^2)/n) < O(mn) ???
问问题
727 次
2 回答
10
您应该只说复杂性是O(m^2/n + mn).
让我们看看它们何时相等：
(m^2)/n = mn
m^2 = m(n^2)
m = n^2
所以，如果m = n^2，它们是相等的，
当m > n^2，m^2/n是显性的，
当m < n^2，mn是显性的。
因此，两者都不总是大于另一个，因此我们也不能抵消。
于 2013-10-25T10:07:16.973 回答
0
从维度上来说，它们是无法比较的。如果 m 和 n 的单位相同，请说 UNIT
但是 (m^2)/n 以 UNIT 为单位，mn 以 UNIT^2 或 UNIT-Squared 为单位。
(m^2)/n < mn
如果你服用m = n，那么m^2/n就会n。
这意味着 m 和 n 具有相同的数量级（或相同的量级），则复杂度为O(mn)。
如果 m 和 n 的阶数不同，
if m^2 < n, then it will be O(mn)
if m^2 > n, then it will be O(m^2/n)
于 2013-10-25T10:37:34.293 回答