证明Big-O和求和规则？

Question

我不确定如何正式证明大O求和规则，即：

f1(n) + f2(n) is O(max(g1(n)),g2(n))

迄今为止，在我的努力中，我假设以下内容：

有两个常量c1和c2，使得c2 > c1。按照大O表示法的定义：

f1(n) <= c1g1(n) and f2(n) <= c2g2(n)

我该怎么做？在这一步引入数值替换变量来证明关系是否合理？由于不知道g或f，这是我能想到的唯一方法。

- Rome_Leader

---

搜索引擎上肯定有大量的解决方案，这个链接是其中之一吗？http://forums.codeguru.com/showthread.php?378861-quot-Sum-of-Rules-quot-for-Big-Oh-PROOF - Rup

我已经查看了Google和那个帖子，但它似乎更像是对语义的攻击，而不是有用的东西。我没有找到任何有用的信息。下面建议的限制方法对我来说很有道理，所以我会尝试一下。 - Rome_Leader

我不确定这是否真的是这里讨论的主题，但已经有一个答案了，所以显然有一些人对此感兴趣。 - jerry

Answer 1

Let

gmax = max(g1, g2), and gmin = min(g1, g2). 

是O()。现在，使用定义：

gmin(n) <= c*gmax(n) for n > some k

将gmax(n)添加到每一侧，得到：

gmin(n) + gmax(n) <= c*gmax(n) + gmax(n) for n > some k
gmin(n) + gmax(n) <= (c+1)*gmax(n)       for n > some k
g1(n) + g2(n) <= c'*gmax(n)              for n > some k

因此，我们有g1+g2为O(max(g1，g2))。

由于f1+f2为O(g1+g2)，大O的传递性告诉我们f1+f2为O(max(g1，g2))。证毕。

- Imre Kerr

Answer 2

我想我可能更倾向于建构主义者，我会这样解决问题：

根据大O符号的定义，存在正数c1、c2、N1和N2，使得：

f1(n) <= c1g1(n)，对于所有n > N1

并且

f2(n) <= c2g2(n)，对于所有n > N2

令：

N' = max(N1, N2) c' = c1 + c2 g'(n) = max(g1(n), g2(n))

那么对于所有n > N'，我们有：

Therefore, f₁(n) + f₂(n) is O(g'(n)) = O(max(g₁(n),g₂(n)))。

其中，f₁(n) <= c₁g₁(n) <= c₁g'(n)，f₂(n) <= c₂g₂(n) <= c₂g'(n)，且 f₁(n) + f₂(n) <= c₁g'(n) + c₂g'(n) = c'g'(n)。

- jerry

Answer 3

你甚至不需要定义 - 只需将两边除以增长更快的函数，取极限到无穷大，较慢增长的函数将趋于零（即其可以忽略不计）。

- user529758

---

哦，那很有道理！我没有考虑到添加限制，但这确实是非常合理的！谢谢！ 编辑：实际上，这是否可行，因为它不是严格意义上的等式，而是集合的一个元素，因此没有“两个方面”？ - Rome_Leader