证明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 ₀.

在这个定义中应用的绝对值确实是一个理论问题,因为在实践中只有函数用于big-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.

...根据big-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)}足够大ñ.

因为对于正数(参见假设)max{f(n), g(n)} < f(n)+g(n),这意味着以下情况肯定是正确的(我们增加了不平等的右手):

|s(n)| ? P(f(n) + g(n))足够大的n.

...根据big-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)})

请注意,这不是关于函数的相等性,而是关于big-O表达式的等价.

实际上,您可以将big-O表达式视为一组函数,即那些具有相应的大O复杂度的函数集.那么以上证明:

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

这意味着两个O套都是一样的.

必要的假设

我们需要(实际)假设f(n)和g(n)对于足够大的n总是正的.它们在some的某些子集上可能是负的和/或未定义的,但必须有一个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总是负的.但同样,消极的复杂性也没有实际意义.

需要明确的是:在some的某些子集上,这些大O函数可能是负的,甚至是未定义的.只要存在n以上它们总是产生非负数,它们就符合假设.

在subset的子集上产生负面结果和/或未定义的允许函数的示例:

n
log(n)
n³
sqrt(n)

违反假设的函数示例:

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