比较O(n + m)和O(max(n，m))的复杂度 [英] Comparing complexity of O(n+m) and O(max(n,m))

问题描述

我今天进行了面试.并被问及std:set_intersection的复杂性.当我回答时，我提到了

I had a job interview today. And was asked about complexity of std:set_intersection. When I was answering I mentioned that

O(n + m)

等于:

O(max(n，m))

有人告诉我这是不正确的.我尝试与以下对象显示等效项:

I was told that this is incorrect. I was unsuccessfully trying to show equivalence with:

O(0.5 *(n + m))≤O(max(n，m))≤O(n + m)

我的问题是:我真的不正确吗?

My question is: am I really incorrect?

推荐答案

对于所有 m ， n ≥0，max( m ， n )≤ m + n →max( m ， n )在 O ( m + n )中，并且 m + n ≤2max ( m ， n )→ m 中的 m + n (max( m ， n )).

For all m, n ≥ 0 it is valid that max(m, n) ≤ m + n → max(m, n) in O(m + n), and m + n ≤ 2max(m, n) → m + n in O(max(m, n)).

因此 O (max( m ， n ))= O ( m + n ).

Thus O(max(m, n)) = O(m + n).

附录:如果 f 属于 O ( m + n )，则存在一个常量 D > 0，即 f ( n ， m )< D *( m + n )对于 m 和 n 足够大.因此 f ( n ， m )< 2 D * max( m ， n )和 O ( m + n )必须是 O (max( m ， n ))的子集. O (max( m ， n ))的证明是 O ( m + n )是类似的.

ADDENDUM: If f belongs O(m + n) then a constant D > 0 exists, that f(n, m) < D * (m + n) for m and n large enough. Thus f(n, m) < 2 D * max(m, n), and O(m + n) must be a subset of O(max(m, n)). The proof of O(max(m, n)) is a subset of O(m + n) is made analogously.

这篇关于比较O(n + m)和O(max(n，m))的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！