算法设计中证明O(f)+O(g)=O(f+g)

Question

算法设计中 证明O(f)+ O(g)= O(f+g)

Answer 1

证明：令 F[N]=O[f],则存在自然数N1,C1,使得对任意的自然数N>=N1,有：F（N）<=C1f[N];
同理令：G[N]=O[g],则存在自然数N2,C2,使得对任意的自然数N>=N2,有：G（N）<=C2g[N];
令C3=max{C1,C2},N3=max{N1,N2},则对所有的N>=N3,有
F[N]<=C1f(N)<=C3f(N);
G[N]<=C2f(N)<=C3g(N);
故有：
O(f)+O(g)=F(N)+G(N)<=C3f(N)+C3g(N)=C3(f(N)+g(N))=O(f+g);
因此有：O(f)+ O(g)= O(f+g)