证明大O求和规则？ [英] Proving Big-O Sum Rule?

问题描述

我不确定如何正式证明大O规则的款项，即：

I am unsure how to formally prove the Big O Rule of Sums, i.e.:

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

到目前为止，我应该在我的努力下：

So far, I have supposed the following in my effort:

让我们有两个常量 C1 和 C2 ，使得 C2＆GT; C1 。通过大O的定义：

Let there be two constants c1 and c2 such that c2 > c1. By Big O definition:

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

谁能指教我应该如何进行？是否合理引进的变量数值替换在这一步，证明关系？不知道先按g 或 F ，这是我能想到接近的唯一途径。

Can anyone advise how I should proceed? Is it reasonable to introduce numerical substitutions for the variables at this step to prove the relationship? Not knowing g or f, that is the only way I can think to approach.

任何帮助将是很大的AP preciated。

Any help would be greatly appreciated.

推荐答案

让

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

GMIN是O（GMAX）。现在，使用的定义：

gmin is O(gmax). Now, using the definition:

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

添加GMAX（N），以每面为：

Adding gmax(n) to each side gives:

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（最大（G1，G2））。

So we have g1+g2 is O(max(g1, g2)).

由于F1 + F2是O（G1 + G2），大O的传递特性为我们提供了F1 + F2是O（MAX（G1，G2））。 QED。

Since f1+f2 is O(g1+g2), the transitive property of big-O gives us f1+f2 is O(max(g1, g2)). QED.

这篇关于证明大O求和规则？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！