我有一个具有如下时间复杂度的算法:
O((m^2)/n) + O(mn)我想知道:它是否等同于 O(mn)?
O((m^2)/n) > O(mn) 还是 O((m^2)/n) < O(mn)?
我有一个具有如下时间复杂度的算法:
O((m^2)/n) + O(mn)我想知道:它是否等同于 O(mn)?
O((m^2)/n) > O(mn) 还是 O((m^2)/n) < O(mn)?
你应该说这个复杂度是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
是主导的。因此,两者都不总是大于另一个,因此我们不能将它们抵消掉。(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)
如果 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
m=n
时它才能相等。 - Sina R.