algorithm - 证明 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，这是我能想到的唯一方法。

Answer 1

让

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))。QED。

Answer 2

我想我可能更像是一个建构主义者，我会这样解决问题：

根据 Big-O 的定义，存在正 c ₁、c ₂、N ₁和 N ₂使得

f ₁ (n) <= c ₁ g ₁ (n) 对于所有 n > N ₁

和

f ₂ (n) <= c ₂ g ₂ (n) 对于所有 n > N ₂

让：

N' = max(N ₁ ,N ₂ )
c' = c ₁ + c ₂
g'(n) = max(g ₁ (n),g ₂ (n))

然后对于所有 n > 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)

因此，f ₁ (n) + f ₂ (n) 为 O(g'(n)) = O(max(g ₁ (n),g ₂ (n)))

Answer 3

您甚至不需要定义——只需将两边除以增长较快的函数，取无穷大的极限，增长较慢的函数将接近零（即它是微不足道的）。