本文共 5068 字，大约阅读时间需要 16 分钟。

0x01 证明$O(f)+O(g)=O(f+g)$

令$F(n)=O(f)$，则存在自然数$n_1$、正数$c_1$，使得任意自然数$n\ge n_1$，有：

• $F(n)\le c_{1}f(n)$

同理，令$G(n)=O(g)$，存在自然数$n_2$，正数$c_2$，使得对任意自然数$n\ge n_2$，有：

• $G(n)\le c_{2}g(n)$

令$c_3=max(c_1,c_2)$，$n_3=max(n_1,n_2)$，则对所有的$n\ge n_3$，有：

• $F(n)\le c_{1}f(n)\le c_{3}f(n)$
• $G(n)\le c_{2}g(n)\le c_{3}g(n)$

故：

• $O(f)+O(g)=F(n)+G(n)\le c_{3}f(n)+c_{3}g(n)=c_3(f(n)+g(n))$

即得证。

0x02 证明$\theta (f)+\theta (g)=\theta (f+g)$

令$F(n)=\theta (f)$，则存在自然数$n_1$和正数$c_1$、$c_2$，使得任意自然数$n\ge n_1$，有：

• $c_{1}f(n)\le F(n)\le c_{2}f(n)$

同理，令$G(n)=\theta (g)$，存在自然数$n_2$和正数$c_3$、$c_4$，使得对任意自然数$n\ge n_2$，有：

• $c_{3}g(n)\le G(n)\le c_{4}g(n)$

得：

• $c_{1}f(n)+c_{3}g(n)\le F(n)+G(n)\le c_{2}f(n)+c_{4}g(n)$

存在$c_1=c_3$、$c_2=c_4$，使得：

• $c_1(f(n)+g(n))\le F(n)+G(n)\le c_2(f(n)+g(n))$

即得证。

0x03 证明$max(\theta (f),\theta (g))=\theta (f+g)$

网上看到的一些类似证明，我觉得都不是很合理，可能本人智商欠费的原因QAQ

令$F(n)=\theta (f)$，则存在自然数$n_1$和正数$c_1$、$c_2$，使得任意自然数$n\ge n_1$，有：

• $c_{1}f(n)\le F(n)\le c_{2}f(n)$

同理，令$G(n)=\theta (g)$，存在自然数$n_2$和正数$c_3$、$c_4$，使得对任意自然数$n\ge n_2$，有：

• $c_{3}g(n)\le G(n)\le c_{4}g(n)$

得：

• $c_{1}f(n)+c_{3}g(n)\le F(n)+G(n)\le c_{2}f(n)+c_{4}g(n)$

存在$c_1=c_3$、$c_2=c_4$，使得：

• $c_1(f(n)+g(n))\le F(n)+G(n)\le c_2(f(n)+g(n))$

显然的

• $c_1^{\prime }(f(n)+g(n))\le max(F(n),G(n))\le F(n)+G(n)\le c_2(f(n)+g(n))$

这里$c_1^{\prime }$取$\frac{1}{2}{c}_1$即可。

0x04 证明$\theta (f)\cdot \theta (g)=\theta (f\cdot g)$

令$F(n)=\theta (f)$，则存在自然数$n_1$和正数$c_1$、$c_2$，使得任意自然数$n\ge n_1$，有：

• $c_{1}f(n)\le F(n)\le c_{2}f(n)$

同理，令$G(n)=\theta (g)$，存在自然数$n_2$和正数$c_3$、$c_4$，使得对任意自然数$n\ge n_2$，有：

• $c_{3}g(n)\le G(n)\le c_{4}g(n)$

得：

• $c_{1}f(n)\cdot c_{3}g(n)\le F(n)\cdot G(n)\le c_{2}f(n)\cdot c_{4}g(n)$

即得证。

0x05 证明$\theta (max(f(n),g(n)))=\theta (f+g)$

令$F(n)=\theta (f)$，则存在自然数$n_1$和正数$c_1$、$c_2$，使得任意自然数$n\ge n_1$，有：

• $c_{1}f(n)\le F(n)\le c_{2}f(n)$

同理，令$G(n)=\theta (g)$，存在自然数$n_2$和正数$c_3$、$c_4$，使得对任意自然数$n\ge n_2$，有：

• $c_{3}g(n)\le G(n)\le c_{4}g(n)$

得：

• $c_{1}f(n)+c_{3}g(n)\le F(n)+G(n)\le c_{2}f(n)+c_{4}g(n)$

存在$c_1=c_3$、$c_2=c_4$，使得：

• $c_1(f(n)+g(n))\le F(n)+G(n)\le c_2(f(n)+g(n))$

显然的

• $c_1^{\prime }(f(n)+g(n))\le \theta (max(f(n),g(n)))\le F(n)+G(n)\le c_2(f(n)+g(n))$

这里$c_1^{\prime }$取$\frac{1}{2}{c}_1$即可。

转载地址：https://coordinate.blog.csdn.net/article/details/79425139 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！