比较 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)

我的问题是：我真的错了吗？

- Leonid Volnitsky

---

我的理解和你的一样。在O符号中，Min(m+n)基本上是一个可以忽略的常数。但我没有参考来证明它。 - 0w3n

这似乎符合您的观点：http://cs.stackexchange.com/a/11704 - Gray

这个也可以：https://dev59.com/dXjZa4cB1Zd3GeqPaSNx#19458485 - Gray

你比面试官更具备知识，这就是全部。他们期望得到一个答案，而你给出了另一个答案，所以他们认为你错了。 - Yuval Filmus

Answer 1

对于所有的m，n ≥ 0，都成立max(m, n) ≤ m + n → max(m, n)在O(m + n)中，且m + n ≤ 2max(m, n) → m + n在O(max(m, n))中。

因此，O(max(m, n)) = O(m + n)。

补充说明：如果f属于O(m + n)，那么存在一个常数D > 0，使得对于足够大的m和n，f(n, m) < D * (m + n)。因此，f(n, m) < 2 D * max(m, n)，并且O(m + n)必须是O(max(m, n))的子集。证明O(max(m, n))是O(m + n)的子集是类似的。

- clemens

---

你能稍微修改一下吗？你使用的“≤”和“=>”让我有些困惑。谢谢。 - Gray

不，A => B 意味着 B 从 A 中得出，而 a ≥ b 意味着 a 数值上大于等于 _b_。 - clemens

@macmoonshine，你的推理“因此O(max(m, n)) = O(m + n)”是不正确的，你上面证明的唯一一件事情是F1=max(n,m)属于集合(m+n)=Set1，而F2=m+n属于集合O(max(m,n))=Set2。所以你证明了F1属于Set1，F2属于Set2。O(max(m, n)) = O(m + n)意味着Set1等于Set2，这意味着每个函数属于Set1也属于Set2，反之亦然。因此，你的推理-三段论并没有证明集合相等，这才是目标！ - coder

附录通过展示每个集合都是另一个集合的子集来证明这些集合相等。您不理解什么，或者您认为附录中缺少什么？顺便问一下：「不正确」和「错误」之间有什么区别？ - clemens

@coder：我只是问了一下，因为“不正确”和“错误”的用法。我不确定我是否理解你的意思。 - clemens

Answer 2

您说得很对，O(n+m)等于O(max(n,m))，更精确的是我们可以证明Θ(n+m)=Θ(max(n,m))，这更紧密地证明了您的观点。数学证明（适用于大O和Θ）非常简单易懂，符合常识。因此，既然我们有一份“数学证明”，它是一种以更加明确定义和严格的方式表达某些内容的方式，不会留下任何歧义。

虽然您被（错误地）告知这是不正确的，因为如果我们想要非常准确，这不是表达max(m,n)顺序与m+n相同的适当数学方式。您使用了“等于”这个词，指的是大O符号，但是大O符号的定义是什么？

引用： 它是指“集合”。说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是相同的（或相等的）时，意味着它们包含相同的元素（我们不尝试进行比较，而是引用它们包含的元素，因此它们必须是有限的）。即使在谈论大O集合时，即使进行识别也不容易应用。

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).

我还有一件事要说，我们说这些函数的阶数相同是绝对正确的数学概念，但是在尝试优化算法时，你可能需要考虑一些低阶因素，然后它们可能会给出略微不同的结果，但渐近行为被证明是相同的。

结论

正如您可以在wikipedia（以及每个大学的所有cs课程或每本算法书中）中阅读到的那样，Big O/θ/Ω/ω/ο符号帮助我们比较函数并找到它们的增长顺序，而不是用于函数集。这就是为什么你被告知你是错误的原因。虽然说O(n^2)是O(n)的子集很容易，但是比较无限集合来判断两个集合是否相等非常困难。 Cantor已经开始对无限集进行分类，例如，我们知道自然数是可数无限的，而实数是不可数无限的，因此实数多于自然数，即使两者都是无限的。当尝试对无限集进行排序和分类时，变得非常复杂，这将更像数学研究而不是比较函数的方法。

---

更新

事实证明，你可以简单地证明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 集合相等，就像我们在前一段中所做的那样。

- coder

Answer 3

我们将通过严格的大O分析来展示您是正确的，在您的分析中给定一种可能的增长参数选择。然而，这并不一定意味着面试官的观点是错误的，而是他/她选择的增长参数不同。他/她指出您的答案完全错误，然而，这是值得质疑的：您可能只是使用了两种稍微不同的方法来分析 std::set_intersection 的渐近复杂度，两种方法都导致了算法以线性时间运行的共识。

---

准备工作

让我们先看一下cppreference上std::set_intersection的参考文献（强调是我的）。

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

Parameters

first1, last1 - the first range of elements to examine

first2, last2 - the second range of elements to examine

Complexity

At most 2·(N1+N2-1) comparisons, where

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

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

std::distance

...

返回first和last之间的元素数量。

我们将简要回顾大O符号的基础知识。

---

大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)使得(+)成立的问题是退化的。事实上，如果存在任何这样的常数对，将存在无限数量的不同常数对。

我们将根据算法已知的最坏情况比较次数（我们将考虑这样的比较为一个基本操作），继续对std::set_intersection进行大O分析。

---

将大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) 的渐近复杂度，使用大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的实际比较次数的最坏情况和Big-O符号以及渐近复杂度的分离问题，并对此进行了混淆查询。

---

最后的话

需要注意的是，对于常见的非有序集合交集问题，std::set_intersect的最坏情况复杂度分析并不具有代表性：前者适用于已经排序的范围（请参见Boost的set_intersection引用下面的内容：即std::set_intersection的起源），而在后者中，我们研究的是非有序集合的交集计算。

• Boost：set_intersection

描述

set_intersection构造一个已排序范围，该范围是rng1和rng2的交集。返回值是输出范围的末尾。

作为后者的一个例子，Python的Intersection集合方法适用于非有序集合，并应用于例如集合s和t，它的平均情况和最坏情况的复杂度分别为O(min(len(s), len(t)))和O(len(s) * len(t))。这种实现中平均情况和最坏情况之间的巨大差异源于哈希解决方案通常在实践中工作得非常好，但对于某些应用程序，在理论上可能具有非常差的最坏情况性能。

关于后一问题的更多细节，请参见两个未排序集合或列表的交集 @ SE-CSTheory。

- dfrib