证明 O(max{ f (n),g(n)}) = O( f (n)+g(n))

Question

我发现了这个关于算法分析的规则：

O(max{f(n),g(n)}) = O(f(n)+g(n)) 

如何证明这一点？

我知道：

max{f(n),g(n)} <= f(n)+g(n) <= 2 * max{f(n),g(n)}

因此：

max{f(n),g(n)} is O(f(n)+g(n))
max{f(n),g(n)} is O(max{f(n),g(n)})
f(n)+g(n)      is O(max{f(n),g(n)})

但是然后

如果 a 是 O(b) 并且 b 是 O(a) 那么 O(a) = O(b) ？

Answer 1

为了证明 O(max{f(n),g(n)}) = O(f(n)+g(n))，我们可以使用 big-O 的正式定义：

f(x) = O(g(x)) 当且仅当存在正实数 M 和实数 x₀ 使得
|f(x)| ≤ M|g(x)| 对于所有 x ≥ x₀。

这个定义中应用的绝对值实际上是一个理论问题，因为在实践中，只有函数用在大 O 表示法中，对于足够大的 x 总是给出正值。指定负的大 O 复杂度是没有意义的。因此，我不会在本答案的其余部分中使用该绝对值，而是假设函数产生正值。

为了掌握 big-O 的概念，可能值得阅读这篇关于 Big-O 误解的短文。

证明如果 s(n) 是 O(f(n)+g(n)) 那么 s(n) 是 O(max{f(n), g(n)})

使用上面的定义，我们可以说某个函数s(n):

s(n) is O(f(n)+g(n))

当且仅当存在 M 使得

|s(n)| ≤ M(f(n) + g(n))

对于足够大的n，相当于：

|s(n)| ≤ M·max{f(n), g(n)} + M·min{f(n), g(n)}

足够大n。

对于相同的 M，以下也将成立 - 这里我们依赖于假设 f(n) 和 g(n) 对于大 n 都是正数：

|s(n)| ≤ 2M·max{f(n), g(n)}

足够大n。

如果我们现在选择P为2M，那么我们可以说我们有一个P，其中：

|s(n)| ≤ P·max{f(n), g(n)}

足够大n。

...根据大O的定义意味着

s(n) is O(max{f(n), g(n)})

∎

证明如果 s(n) 是 O(max{f(n), g(n)}) 那么 s(n) 是 O(f(n)+g(n))

s(n) is O(max{f(n), g(n)})

当且仅当存在P使得

|s(n)| ≤ P·max{f(n), g(n)}

足够大n。

因为对于正数（参见假设）

max{f(n), g(n)} < f(n)+g(n)

，这意味着以下内容肯定是正确的（我们增加了不等式的右手）：

|s(n)| ≤ P(f(n) + g(n))

足够大n。

...根据大O的定义意味着

s(n) is O(f(n)+g(n))

∎

结论

上面证明，如果任何函数是 O(f(n)+g(n)) 那么它也一定是 O(max{f(n),g(n)})，反之亦然。这相当于说两个大 O 复杂性是相同的：

O(f(n)+g(n)) = O(max{f(n),g(n)})

请注意，这不是关于函数的等价性，而是关于大 O 表达式的等价性。

事实上，您可以将 big-O 表达式视为函数集，即具有相应 big-O 复杂度的函数集。那么上面就证明了：

s(n) ∈ O(f(n)+g(n)) ⇔ s(n) ∈ O(max{f(n),g(n)})

这意味着两个 O 集是相同的。

必要的假设

我们需要（实际）假设，对于足够大的 n，f(n) 和 g(n) 始终为正。它们在 ℝ 的某些子集上可以为负值和/或未定义，但必须有一个 n，其上方的 f(n) 和 g(n) 始终会产生非负结果。如果情况并非如此，那么可以用一个简单的反例来证明前提是错误的：

g(n) = n
f(n) = -n

前提

O(max{f(n),g(n)}) = O(f(n)+g(n))

则变为：

O(n) = O(0)

这显然是错误的。这是因为 f(n) 违反了假设，并且对于大 n 始终为负。但同样，负复杂度没有实际意义。

需要明确的是：这些大O函数在ℝ的某些子集上可能是负数，甚至是未定义的。只要有一个 n 在其之上，它们总是产生一个非负数，它们就符合假设。

产生负结果和/或在 ℝ:

的子集上未定义的允许函数的示例

n
log(n)
n³
sqrt(n)

违反假设的函数示例：

sin(n)
cos(n)
tg(n)
-n

Answer 2

这个答案假设 f(n), g(n) >=0 对于所有 n >= 0。我使用这些假设是因为没有算法（据我所知）在任何情况下都可以有负空间或时间使用。

你无法知道 f(n) 和 g(n) 是什么，因此你不能选择其中任何一个作为上限。

因此，剩下的唯一保证比 f(n) 和 g(n) 都大的选项是

f(n)+g(n)

。

Answer 3

如果我们假设 f(n) & g(n) >= 0 对于 n 的所有值，那么它们的总和将大于其中任何一个。如果没有这个假设，这种关系就不会成立。我们可以从逻辑上尝试几个例子。

Max(f(n) = 1 & g(n) = 3)  < ((f(n) + g(n) = 4)
Max(f(n) = 5 & g(n) = 0)  = ((f(n) + g(n) = 5)
Max(f(n) = 0 & g(n) = 8)  = ((f(n) + g(n) = 8)
So f(n) + g(n) will always upperbound O(Max(f(n),g(n)))
i.e. O(Max(f(n),g(n))) = O(f(n) + g(n))

我们还可以通过以下事实轻松证明：Max(f(n),g(n)) < ((f(n) + g(n)) <= 2*Max(f(n),g(n))：我们总是取两个中的最大值。 有两种情况

1：两个值不同：在这种情况下，总和将小于 最大的两倍。

Max(f(n) = 4 & g(n) = 1)  < ((f(n) + g(n) = 5) < 2*Max(f(n) = 4 & g(n) = 1)
Max(f(n) = 3 & g(n) = 0)  = ((f(n) + g(n) = 3) < 2*Max(f(n) = 3 & g(n) = 0)

1：两个值相同：在这种情况下，总和将恰好是最大值的两倍。

Max(f(n) = 1 & g(n) = 1)  < ((f(n) + g(n) = 2) = 2*Max(f(n) = 1 & g(n) = 1)
Max(f(n) = 0 & g(n) = 0)  = ((f(n) + g(n) = 0) = 2*Max(f(n) = 0 & g(n) = 0)

因此

i.e. Max(f(n),g(n))  < ((f(n) + g(n)) <= 2*Max(f(n),g(n))