10

こんにちは私は次のことを証明するのに少し苦労しています。

f(n) + g(n) is O(max(f(n),g(n)))

これは論理的に理にかなっており、これを見ると正しいと言えますが、証明を思い付くのに苦労しています。

これが私がこれまでに持っているものです：

c * (max(f(n),g(n))) > f(n) + g(n) for n > N

しかし、f（n）とg（n）が何であるかわからないため、定義に合うようにacとNを選択する方法がわかりません。

どんな助けでも大歓迎です。

4

1 に答える 1

14 
f(n) + g(n) <= 2* max{f(n),g(n)} 
(for each n>0, assume f(n),g(n) are none-negative functions)

したがって、のためN=1に、すべてのためにn>N： 、そして私たちはf(n) + g(n) <= 2*max{f(n),g(n)}にある大きなOの定義によって言うことができますf(n) + g(n)O(max{f(n),g(n)})

したがって、基本的に、N=1, c=2定義上、正式な証明に使用します。

于 2012-10-09T00:34:04.743 に答える