渐进符号的特性
作者:Nugine时间:2020-09-08 14:07:59
$$ O(f(n))+O(g(n)) = O(\max\{f(n),g(n)\}) $$
证明
设
$$x(n) = \max\{f(n),g(n)\}$$
可得
$$ x(n)\le f(n)+g(n) \le 2x(n) $$
$$ f(n)+g(n)=\Theta(x(n)) $$
$$ f(n)+g(n)=O(x(n)) $$
因为
- $f(n)=O(f(n))$
- $g(n)=O(g(n))$
- $f(n)+g(n)=O(x(n))$
所以
$$O(f(n))+O(g(n))=O(x(n))$$
即得
$$ O(f(n))+O(g(n)) = O(\max\{f(n),g(n)\}) $$
证毕.