比较 O(n+m) 和 O(max(n,m)) 的复杂度
Comparing complexity of O(n+m) and O(max(n,m))
我今天参加了工作面试。并被问及 std:set_intersection 的复杂性。我在回答的时候提到了
O(n+m)
等于：
O(最大(n,m))
有人告诉我这是不正确的。我没有成功地尝试显示等价于：
O(0.5*(n+m)) ≤ O(max(n,m)) ≤ O(n+m)
我的问题是：我真的错了吗？
对于所有 m, n ≥ 0 max(m, n) ≤ m + n → 最大值(m , n) 在 O(m + n) , 并且 m + n ≤ 2max(m, n) → m + n 在 O(max(m, n)).
因此O(max(m,n))=O(m + n).
ADDENDUM：如果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) 类比。
关于 O(n+m) 等于 O(max(n,m))，你完全正确，我们可以更精确地证明 Θ(n+m)=Θ(max(n,m) ) 更紧凑，可以证明你的句子。数学证明（对于 big-O 和 Θ）非常简单且易于用常识理解。所以既然我们有一个 mathematical proof 这是一种表达方式但以更明确和严格的方式 doesn't leaves any ambiguity。
尽管您被（错误地）告知这是不正确的，因为如果我们想要非常精确，这不是合适的 - 表达 max(m,n) 阶数的数学方法与 m+n 相同。您使用 "is equal" 来指代大 O 表示法，但大 O 表示法的定义是什么？
It is referred to Sets. Saying max(n+m) belongs to O(m+n) is the
most correct way and vice versa m+n belongs to O(max(m,n)). In big O
notation is commonly used and accepted to say m+n = O(max(n,m)).
造成的问题是你没有尝试引用一个函数的顺序，比如f是O(g)，而是你试图比较集合O(f)和O(g)。但是证明了两个无穷大集合相等并不容易（这可能会使面试官感到困惑）。
当包含相同元素时，我们可以说集合 A 和 B 相同（或相等）（我们不尝试比较而是引用它们包含的元素，因此它们必须 有限).在谈论大 O 集时，甚至连识别都不能轻易应用。
Big O of F is used to notate that we are talking about the Set that
contains all functions with order greater or equal than F. How many
functions are there??
Infinite since F+c is contained and c can take infinite values.
How could you say two different Sets are identical(or equal) when they are
infinite ,well it is not that simple.
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).
还有一件事，我们说过这些函数具有相同的阶数，这在数学上是绝对正确的，但是在尝试优化算法时，您可能需要考虑一些低阶因子，那么它们可能会给您带来轻微的影响结果不同，但渐近行为被证明是相同的。
CONCLUSION
正如您在 wikipedia（以及每所大学或每本算法书中的所有 cs 课程）中所读到的那样，大 O/θ/Ω/ω/ο 符号 helps us compare functions 并找到它们的顺序增长而不是函数集，这就是为什么你被告知你错了。虽然很容易说 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) 并不能立即证明集合是equal （我们需要证明）正如你所说，它只是证明函数具有相同的顺序，但我们没有检查集合。虽然很容易看出（在一般情况下）如果 f 是 O(g) 并且 g 是 O(F) 那么你可以很容易地 在这种情况下证明大 O 设置相等性 就像我们在上一段中所做的那样。
我们将通过严格的 Big-O 分析证明您确实是正确的，在您的分析中给定一个可能的增长参数选择。然而，这并不一定意味着面试官的观点不正确，而是his/her增长参数的选择不同。 His/her 提示您的答案是完全错误的，但是，这是值得怀疑的：您可能只是使用了两种略有不同的方法来分析 std::set_intersection 的渐近复杂性，这两种方法都导致了算法 运行s 线性时间。
准备工作
让我们首先查看 cppreference 中 std::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
...
Returns the number of elements between first and last.
我们将继续简要回顾大 O 表示法的基础。
大 O 表示法
我们松散地陈述函数或算法的定义 f 在 O(g(n)) 中（挑剔的是，O(g(n)) 是一组 函数 ，因此 f ∈ O(...)，而不是通常被误用的 f(n) ∈ O(...))。
If a function f is in O(g(n)), then c · g(n) is an upper
bound on f(n), for some non-negative constant c such that f(n) ≤ c · g(n)
holds, for sufficiently large n (i.e. , n ≥ n0 for some constant
n0).
因此，为了证明f ∈ O(g(n))，我们需要找到一组满足
的（非负）常数(c, n0)
f(n) ≤ c · g(n), for all n ≥ n0, (+)
但是，我们注意到这个集合不是唯一的；找到使 (+) 成立的常数 (c, n0) 的问题是 退化 。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
我们继续 std::set_intersection 的 Big-O 分析，基于已知的最坏情况下的算法比较次数（我们将考虑一个这样的比较 基本操作).
将 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 notation/asymptotic 分析之前自由选择设置的先决条件，并且面试官很可能倾向于选择使用 k 作为参数来分析复杂性增长而不是其两个组成部分中最大的一个。
现在，从上面我们知道，在最坏的情况下，std::set_intersection 将进行 运行 2 · (m + n - 1) comparisons/basic 操作。让
h(n, m) = 2 · (m + n - 1)
由于目标是根据 Big-O（上限）找到渐近复杂度的表达式，我们可以在不失一般性的情况下假设 n > m，并定义
f(n) = 2 · (n + n - 1) = 4n - 2 > h(n,m) (*)
我们继续用大 O 符号分析 f(n) 的渐近复杂度。让
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 元素，我们已经证明 [=21= 的渐近复杂性] 应用两个这两个范围确实是
O(max(m, n))
我们选择 m 和 n 中最大的一个作为我们分析的增长参数。
然而，在谈到 Big-O 符号时，这并不是真正有效的注释（至少不常见）。当我们使用 Big-O 表示法来描述某些算法或函数的渐近复杂性时，我们是针对某个单一的增长参数（而不是其中两个）这样做的。
而不是回答复杂度是 O(max(m, n))，我们可以在不失一般性的情况下假设 n 描述范围 中元素数量最多的元素 ，并根据该假设，简单地说明 std::set_intersection 的渐近复杂度的上限是 O(n)（线性时间）。
关于面试反馈的推测：如上所述，面试官可能只是坚定地认为 Big-O notation/asymptotic 分析应该基于 k = m+n 作为增长参数而不是其两个组成部分中最大的一个。自然地，另一种可能性可能是面试官只是混淆地询问了 std::set_intersection 的实际 比较 的最坏情况，同时将其与 Big-O 的单独问题混合在一起符号和渐近复杂度。
最后的评论
最后请注意，std::set_intersect 的最坏情况复杂度分析完全不能代表通常研究的无序集交集问题：前者适用于已经排序的范围（请参阅引用自Boost的set_intersection下：std::set_intersection的由来），而后者我们研究的是无序集合交集的计算
Description
set_intersection constructs a sorted range that is the intersection
of the sorted ranges rng1 and rng2. The return value is the
end of the output range.
作为后者的例子，Python的Intersectionset方法适用于无序集合，适用于集合s和t , it has an average case and a worst-case complexity of O(min(len(s), len(t)) and O(len(s) * len(t)), 分别。此实现中平均情况和最坏情况之间的巨大差异源于以下事实：基于哈希的解决方案通常在实践中运行良好，但对于某些应用程序，理论上可能具有非常差的最坏情况性能。
有关后一个问题的更多详细信息，请参阅
我今天参加了工作面试。并被问及 std:set_intersection 的复杂性。我在回答的时候提到了
O(n+m)
等于：
O(最大(n,m))
有人告诉我这是不正确的。我没有成功地尝试显示等价于：
O(0.5*(n+m)) ≤ O(max(n,m)) ≤ O(n+m)
我的问题是：我真的错了吗？
对于所有 m, n ≥ 0 max(m, n) ≤ m + n → 最大值(m , n) 在 O(m + n) , 并且 m + n ≤ 2max(m, n) → m + n 在 O(max(m, n)).
因此O(max(m,n))=O(m + n).
ADDENDUM：如果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) 类比。
关于 O(n+m) 等于 O(max(n,m))，你完全正确，我们可以更精确地证明 Θ(n+m)=Θ(max(n,m) ) 更紧凑，可以证明你的句子。数学证明（对于 big-O 和 Θ）非常简单且易于用常识理解。所以既然我们有一个 mathematical proof 这是一种表达方式但以更明确和严格的方式 doesn't leaves any ambiguity。
尽管您被（错误地）告知这是不正确的，因为如果我们想要非常精确，这不是合适的 - 表达 max(m,n) 阶数的数学方法与 m+n 相同。您使用 "is equal" 来指代大 O 表示法，但大 O 表示法的定义是什么？
It is referred to
Sets. Saying max(n+m) belongs to O(m+n) is the most correct way and vice versa m+n belongs to O(max(m,n)). In big O notation is commonly used and accepted to say m+n = O(max(n,m)).
造成的问题是你没有尝试引用一个函数的顺序，比如f是O(g)，而是你试图比较集合O(f)和O(g)。但是证明了两个无穷大集合相等并不容易（这可能会使面试官感到困惑）。
当包含相同元素时，我们可以说集合 A 和 B 相同（或相等）（我们不尝试比较而是引用它们包含的元素，因此它们必须 有限).在谈论大 O 集时，甚至连识别都不能轻易应用。
Big O of F is used to notate that we are talking about the Set that contains all functions with order greater or equal than F. How many functions are there??
Infinite since F+c is contained and c can take infinite values.
How could you say two different Sets are identical(or equal) when they are infinite ,well it is not that simple.
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).
还有一件事，我们说过这些函数具有相同的阶数，这在数学上是绝对正确的，但是在尝试优化算法时，您可能需要考虑一些低阶因子，那么它们可能会给您带来轻微的影响结果不同，但渐近行为被证明是相同的。
CONCLUSION
正如您在 wikipedia（以及每所大学或每本算法书中的所有 cs 课程）中所读到的那样，大 O/θ/Ω/ω/ο 符号 helps us compare functions 并找到它们的顺序增长而不是函数集，这就是为什么你被告知你错了。虽然很容易说 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) 并不能立即证明集合是equal （我们需要证明）正如你所说，它只是证明函数具有相同的顺序，但我们没有检查集合。虽然很容易看出（在一般情况下）如果 f 是 O(g) 并且 g 是 O(F) 那么你可以很容易地 在这种情况下证明大 O 设置相等性 就像我们在上一段中所做的那样。
我们将通过严格的 Big-O 分析证明您确实是正确的，在您的分析中给定一个可能的增长参数选择。然而，这并不一定意味着面试官的观点不正确，而是his/her增长参数的选择不同。 His/her 提示您的答案是完全错误的，但是，这是值得怀疑的：您可能只是使用了两种略有不同的方法来分析 std::set_intersection 的渐近复杂性，这两种方法都导致了算法 运行s 线性时间。
准备工作
让我们首先查看 cppreference 中 std::set_intersection 的引用（强调我的）
Parameters
first1,last1- the first range of elements to examine
first2,last2- the second range of elements to examineComplexity
At most
2·(N1+N2-1)comparisons, whereN1 = std::distance(first1, last1) N2 = std::distance(first2, last2)
std::distance本身是线性的（最坏情况：没有随机访问）
std::distance...
Returns the number of elements between
firstandlast.
我们将继续简要回顾大 O 表示法的基础。
大 O 表示法
我们松散地陈述函数或算法的定义 f 在 O(g(n)) 中（挑剔的是，O(g(n)) 是一组 函数 ，因此 f ∈ O(...)，而不是通常被误用的 f(n) ∈ O(...))。
If a function
fis inO(g(n)), thenc · g(n)is an upper bound onf(n), for some non-negative constantcsuch thatf(n) ≤ c · g(n)holds, for sufficiently largen(i.e. ,n ≥ n0for some constantn0).
因此，为了证明f ∈ O(g(n))，我们需要找到一组满足
(c, n0)
f(n) ≤ c · g(n), for all n ≥ n0, (+)
但是，我们注意到这个集合不是唯一的；找到使 (+) 成立的常数 (c, n0) 的问题是 退化 。事实上，如果存在任何这样的常数对，就会存在无数个不同的这样的常数对。
我们继续 std::set_intersection 的 Big-O 分析，基于已知的最坏情况下的算法比较次数（我们将考虑一个这样的比较 基本操作).
将 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 notation/asymptotic 分析之前自由选择设置的先决条件，并且面试官很可能倾向于选择使用k作为参数来分析复杂性增长而不是其两个组成部分中最大的一个。
现在，从上面我们知道，在最坏的情况下，std::set_intersection 将进行 运行 2 · (m + n - 1) comparisons/basic 操作。让
h(n, m) = 2 · (m + n - 1)
由于目标是根据 Big-O（上限）找到渐近复杂度的表达式，我们可以在不失一般性的情况下假设 n > m，并定义
f(n) = 2 · (n + n - 1) = 4n - 2 > h(n,m) (*)
我们继续用大 O 符号分析 f(n) 的渐近复杂度。让
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 元素，我们已经证明 [=21= 的渐近复杂性] 应用两个这两个范围确实是
O(max(m, n))
我们选择 m 和 n 中最大的一个作为我们分析的增长参数。
然而，在谈到 Big-O 符号时，这并不是真正有效的注释（至少不常见）。当我们使用 Big-O 表示法来描述某些算法或函数的渐近复杂性时，我们是针对某个单一的增长参数（而不是其中两个）这样做的。
而不是回答复杂度是 O(max(m, n))，我们可以在不失一般性的情况下假设 n 描述范围 中元素数量最多的元素 ，并根据该假设，简单地说明 std::set_intersection 的渐近复杂度的上限是 O(n)（线性时间）。
关于面试反馈的推测：如上所述，面试官可能只是坚定地认为 Big-O notation/asymptotic 分析应该基于 k = m+n 作为增长参数而不是其两个组成部分中最大的一个。自然地，另一种可能性可能是面试官只是混淆地询问了 std::set_intersection 的实际 比较 的最坏情况，同时将其与 Big-O 的单独问题混合在一起符号和渐近复杂度。
最后的评论
最后请注意，std::set_intersect 的最坏情况复杂度分析完全不能代表通常研究的无序集交集问题：前者适用于已经排序的范围（请参阅引用自Boost的set_intersection下：std::set_intersection的由来），而后者我们研究的是无序集合交集的计算
Description
set_intersectionconstructs a sorted range that is the intersection of the sorted rangesrng1andrng2. The return value is the end of the output range.
作为后者的例子，Python的Intersectionset方法适用于无序集合，适用于集合s和t , it has an average case and a worst-case complexity of O(min(len(s), len(t)) and O(len(s) * len(t)), 分别。此实现中平均情况和最坏情况之间的巨大差异源于以下事实：基于哈希的解决方案通常在实践中运行良好，但对于某些应用程序，理论上可能具有非常差的最坏情况性能。
有关后一个问题的更多详细信息，请参阅