比较O(n + m)和O(max(n,m))的复杂度

Question

我今天接受了面试.并被问及复杂性std:set_intersection.当我回答时,我提到了这一点

O(N + M)

等于:

O(MAX(N,M))

我被告知这是不正确的.我试图表现出与以下方面的对等关系是不成功的:

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

我的问题是:我真的不对吗？

Answer 1

对于所有的米,Ñ ≥0它是有效的是最大(米,Ñ)≤ 米 + Ñ →MAX(米,Ñ)在Ö(米 + Ñ),和米 + Ñ ≤2MAX(米,Ñ)→ 米 + n在O(max(m,n))中.

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

附录:如果˚F属于Ô(米 + Ñ),则常数d > 0存在,即˚F(Ñ,米)< d*(米 + Ñ为)米和Ñ足够大.因此,f(n,m)<2 D*max(m,n)和O(m + n)必须是O(max(m,n))的子集.O(max(m,n))的证明是O(m + n)的子集,类似地进行.

Answer 2

那么你完全正确的O(n + m)等于O(max(n,m)),更精确我们可以证明Θ(n + m)=Θ(max(n,m)更紧并且证明了你的句子.数学证明(对于大O和Θ)非常简单,易于理解.因为我们有mathematical proof一种方式可以说一些东西,但是更明确,更严格的方式doesn't leaves any ambiguity.

虽然你(错误地)告诉我这是不正确的,因为如果我们想要非常精确,这不是合适的 - 数学方式来表达max(m,n)的顺序与m + n相同.您使用了"等于"这个词来指代大O符号,但是大O符号的定义是什么？

它被提及Sets.说max(n + m)属于O(m + n)是最正确的方式,反之亦然m + n属于O(max(m,n)).在大O中,通常使用并表示m + n = O(max(n,m)).

引起的问题是你没有尝试引用函数的顺序,比如f是O(g)但是你试图比较集合O(f)和O(g).但是证明两个无限集是相等的不是容易(这可能会使面试官感到困惑).

我们可以说当包含相同的元素时,集合A和B是相同的(或相等)(我们不会尝试比较,而是引用它们包含的元素,因此它们必须是有限的).在谈论Big O Sets时,甚至不能轻易应用识别.

F的大O用于表示我们正在讨论包含所有大于或等于F的函数的集合.有多少函数？

Infinite since F+c is contained and c can take infinite values.

你怎么能说两个不同的集合在它们是无限的时是相同的(或相等的),那就不那么简单了.

So I understand what you are thinking that n+m and max(n,m) have same 
order but **the right way to express that** is by saying n+m is    
O(max(n,m)) and max(n,m)is O(m+n) ( O(m+n) is equal to O(max(m,n)) 
may better requires a proof).

还有一件事,我们说这些函数具有相同的顺序,这绝对是数学上正确的,但是当尝试优化算法时,你可能需要考虑一些低阶因子,那么它们可能会给你略有不同的结果,但是渐近行为被证明是一样的.

结论

正如您可以阅读维基百科(以及所有大学或每个算法书中的所有cs课程)大O /θ/Ω/ω/ο符号helps us compare functions并找到它们的增长顺序而不是功能集,这就是为什么你是告诉你错了.虽然很容易说O(n ^ 2)是O(n)的子集,但如果两个集合相同则很难比较无穷大.康托尔致力于对无限集进行分类,例如我们知道自然数是无数的,而实数是无数无数的,所以即使两者都是无穷大,实数也不仅仅是自然数.在尝试对无限集进行排序和分类时,它变得非常复杂,这将更多地是数学研究,而不是比较函数的方法.

UPDATE

事实证明你可以简单地证明O(n + m)等于O(max(n,m)):

对于属于O(n + m)的每个函数F,这意味着存在常数c和k,例如:

 F <= c(n+m) for every n>=k and m>=k

然后还站着:

 F <= c(n+m)<= 2c*max(n,m) 

所以F属于O(max(n,m)),因此O(m + n)是O的子集(max(n,m)).现在考虑F属于O(max(n,m))然后有常数c和k这样:

 F <= c*max(n+m) for every n>=k and m>=k

我们还有:

F <= c*max(n+m)<=2c(m+n) for every n>=k and m>=k

因此,根据定义,存在c'= 2c且具有相同的k:F是O(m + n),因此O(max(n,m))是O(n + m)的子集.因为我们证明O(m + n)是O(max(n,m))的子集,我们证明O(max(m,n))和O(m + n)是相等的 ,这个数学证明证明你完全没有任何疑问.

最后请注意,证明m + n为O(max(n,m))且max(n,m)为O(m + n)并不能立即证明集合相等(我们需要证明)你的说法只是证明函数有相同的顺序,但我们没有检查集合.虽然很容易看到(一般情况下)如果f是O(g)而g是O(F),那么在这种情况下你可以很容易地证明大O设置的相等性就像我们在前一段中所做的那样.

Answer 3

我们将通过严格的Big-O分析显示您确实是正确的,因为您可以选择分析中的增长参数.然而,这并不一定意味着访谈者的观点是不正确的,而是他/她对增长参数的选择不同.然而,他/她提示您的答案完全不正确是值得怀疑的:您可能只是使用两种稍微不同的方法来分析渐近复杂度std::set_intersection,这两种方法都导致了算法在线性时间内运行的普遍共识.

准备工作

让我们首先看一下std::set_intersectioncppreference 的参考(强调我的)

• http://en.cppreference.com/w/cpp/algorithm/set_intersection

参数

first1,last1- 要检查的第一个要素范围

first2,last2- 要检查的第二个要素范围

复杂

在大多数 2·(N1+N2-1)比较中,在哪里

N1 = std::distance(first1, last1)
N2 = std::distance(first2, last2)

std::distance 本身是自然线性的(最坏的情况:没有随机访问)

std::distance

...

返回first和之间的元素数last.

我们将简要回顾一下Big-O表示法的基本原理.

Big-O表示法

我们松散状态的功能或算法的定义f中是O(g(n))(挑剔,O(g(n))是一组函数,因此f ? O(...),而不是常用滥用f(n) ? O(...)).

如果函数f是在 O(g(n)),则c · g(n)是一个上限f(n),对于一些非负常数c,使得f(n) ? c · g(n) 保持,对于足够大的n(即,n ? n0对于某一常数 n0).

因此,就表明f ? O(g(n)),我们需要找到一套(非负)常量(c, n0)是满足

f(n) ? c · g(n), for all n ? n0,                                (+)

但是,我们注意到这一套并不是唯一的 ; 找到(c, n0)(+)成立的常数的问题是退化的.实际上,如果存在任何这样的常数对,则将存在无限量的不同的这样的对.

我们继续进行Big-O分析std::set_intersection,基于已知的最坏情况下算法的比较次数(我们将一个这样的比较视为基本操作).

将Big-O渐近分析应用于set_intersection实例

现在考虑两个元素范围,例如range1和range2,并假设这两个范围中包含的元素数分别为m和n.

• 注意!在分析的初始阶段,我们已经做出了选择:我们选择根据两个不同的增长参数来研究问题(或者更确切地说,关注这两个中最大的一个).正如我们将要看到的那样,这将导致与OP所述的渐近复杂性相同的渐近复杂性.然而,我们也可以选择让它k = m+n成为选择的参数:我们仍然会得出结论:std::set_intersection线性时间复杂度,而不是k(和m+n 不是 max(m, n))最大的m和n.这些只是我们在继续进行Big-O表示法/渐近分析之前自由选择设置的前提条件,并且很可能采访者倾向于选择使用k增长参数来分析复杂性而不是其中最大的两个组件.

现在,从上面我们知道,在最坏的情况下,std::set_intersection将运行2 · (m + n - 1)比较/基本操作.让

h(n, m) = 2 · (m + n - 1)

由于目标是根据Big-O(上限)找到渐近复杂度的表达式,我们可以在不失一般性的情况下假设n > m并定义

f(n) = 2 · (n + n - 1) = 4n - 2 > h(n,m)                         (*)

我们继续分析f(n)Big-O表示法的渐近复杂性.让

g(n) = n

并注意到

f(n) = 4n - 2 < 4n = 4 · g(n)

现在(选择)让c = 4和n0 = 1,我们可以陈述以下事实:

f(n) < 4 · g(n) = c · g(n), for all n ? n0,                      (**) 

鉴于此(**),我们(+)现在已经证明了这一点

f ? O(g(n)) = O(n)

此外,因为`(*)自然而然地成立

h ? O(g(n)) = O(n), assuming n > m                               (i)

成立.

如果我们改变我们的初始假设并假设m > n,相反,重新跟踪上面的分析将产生类似的结果

h ? O(g(m)) = O(m), assuming m > n                                (ii)

结论

因此,给定两个范围range1和range2持有m和n元素,我们已经表明,std::set_intersection应用这两个范围的渐近复杂度确实是

O(max(m, n))

我们选择的是最大的m,n也是我们分析增长的参数.

然而,当谈到Big-O表示法时,这并不是真正有效的注释(至少不常见).当我们使用Big-O表示法来描述某些算法或函数的渐近复杂性时,我们就某个单一的增长参数(不是其中两个)这样做.

而不是应答,所述复杂度是O(max(m, n))我们可在不丧失一般性的情况,假设n描述了在范围内的元素的数量与大多数元素给定这个假设,并且,简单地状态下比的上界的渐近复杂std::set_intersection是O(n)(线性时间).

关于面试反馈的猜测:如上所述,面试官可能只是坚定地认为Big-O符号/渐近分析应该基于k = m+n增长的参数而不是其两个组成部分中的最大部分.另一种可能,当然,是面试官简单容易混淆被问及实际的最坏情况比较数的std::set_intersection,而与大O符号和渐进复杂的事分开混合这一点.

最后的评论

最后请注意,对最坏情况复杂性的分析std::set_intersect并不完全代表通常研究的非有序集合交集问题:前者适用于已经排序的范围(参见set_intersection下面Boost的引用:起源std::set_intersection),而在后者,我们研究非有序集合的交集计算.

• 促进: set_intersection

描述

set_intersection构造一个分类范围是所述的交叉点排序范围rng1和rng2.返回值是输出范围的结尾.

作为后者的一个例子,IntersectionPython的集方法适用于非有序集合,并且被施加到说集s和t,它具有平均情况和最坏情况的复杂性O(min(len(s), len(t))和O(len(s) * len(t))分别.这种实现中平均和最差情况之间的巨大差异源于这样一个事实,即基于散列的解决方案通常在实践中运行良好,但对于某些应用,理论上可能具有非常差的最坏情况性能.

有关后一问题的其他详细信息,请参阅例如

• 两个未分类的集合或列表的交集@ SE-CSTheory