algorithm - 哪个更大：O(mn) 或 O((m^2)/n)？

Question

我有一个这样的算法： O((m^2)/n) + O(mn)

我想知道：它是否等于O(mn)？

O((m^2)/n) > O(mn)或O((m^2)/n) < O(mn) ???

Answer 1

您应该只说复杂性是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是显性的。

因此，两者都不总是大于另一个，因此我们也不能抵消。

Answer 2

从维度上来说，它们是无法比较的。如果 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)