algorithm - 证明大O和规则？

我不确定如何正式证明和的大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，这是我唯一能想到的方法。

最佳答案

让

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

gmin是o（gmax）。现在，使用定义：

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），big-o的传递性质给出了f1+f2是o（max（g1，g2））。量化宽松政策。