什么更大：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)？

- Omid Ebrahimi

---

这似乎是不相关的，因为... 数学。 - naththedeveloper

我认为只有当 m=n 时它才能相等。 - Sina R.

有关m和n的输入定义吗？例如，m是n的子字符串或子集吗？ - jgroenen

我们有一些数组。m是数组的数量，n是每个数组的最大长度。 - Omid Ebrahimi

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 是主导的。因此，两者都不总是大于另一个，因此我们不能将它们抵消掉。

- Bernhard Barker

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)

- doptimusprime

---

你的第一个论点是正确的，即 如果 m^2 <= n，则它将是 O(mn)。你确实证明了它。然而，你的第二个论点 如果 m^2 > n，则它将是 O(m^2/n) 是不正确的。m^2 可以大于 n，但 mn 仍然可以大于 m^2/n。一个简单的反例是 m = 3，n = 4。mn = 12，m^2 = 9 > n。m^2 / n = 9 / 4 小于 mn = 12，所以 m*n 仍然占主导地位。请参见 Dukeling 的答案以查看更紧密的界限。 - Shashank

@ShashankGupta：请发一个例子的编辑。谢谢。我没有意识到这一点。 - doptimusprime