证明三个函数的大O符号关系及相关推导疑问解答

证明1：$f(n) = n^3 + 20n + 1 = O(n^3)$ #

首先得明确大O符号的核心定义：如果存在常数$C > 0$和$n_0 \geq 1$，使得对于所有$n \geq n_0$，都有$f(n) \leq C \cdot g(n)$，那么我们就说$f(n) = O(g(n))$。

你已经推导出了$1 + \frac{20}{n^2} + \frac{1}{n^3} \leq C$，这里你可能搞反了趋势——当n趋于无穷大时，$\frac{20}{n^{2}$和$\frac{1}{n}3}$都是趋近于0的，所以整个左边是趋近于1，而不是无穷大哦！

那我们直接找一个能覆盖所有情况的$C$就行：当$n \geq 1$时，$\frac{20}{n^2} \leq 20$，$\frac{1}{n^3} \leq 1$，所以左边的最大值就是$1+20+1=22$。那我们取$C=22$，$n_0=1$，这样对于所有$n \geq 1$，$n^3 +20n +1 \leq 22n^3$，完全符合大O的定义，所以这个证明成立。

证明2：$l(n) = n^3 + 20n + 1 \neq O(n^2)$ #

这里用反证法最直观。假设$l(n)=O(n^2)$，根据定义，存在$C>0$和$n_0 \geq1$，当$n \geq n_0$时，$n^3 +20n +1 \leq Cn^2$。

我们把不等式两边都除以$n^2$（n是正整数，除法没问题），得到$n + \frac{20}{n} + \frac{1}{n^2} \leq C$。但你看，当n越来越大时，左边的$n$会无限增长，不管$C$取多大的常数，只要n超过$C$，左边就会大于$C$，这和我们的假设矛盾。所以假设不成立，$l(n) \neq O(n^2)$。

证明3：$h(n) = n\sqrt{n} = O(n^2)$ #

先把$h(n)$的形式整理一下：$n\sqrt{n} = n^{1 + 0.5} = n^{1.5}$。现在我们找符合条件的$C$和$n_0$。

根据大O定义，需要$n^{1.5} \leq Cn^{2$，两边除以$n}{1.5}$（n≥1，正数除法不改变不等号方向），得到$1 \leq Cn^{0.5}$，也就是$C \geq \frac{1}{\sqrt{n}}$。

当$n \geq1$时，$\frac{1}{\sqrt{n}} \leq1$，所以我们取$C=1$，$n_0=1$，这样对于所有$n \geq1$，$n^{1.5} \leq1 \cdot n^{2$（因为$n}2 -n^{1.5}=n{1.5}(\sqrt{n}-1) \geq0$，当n≥1时$\sqrt{n}≥1$），完全满足大O的定义，所以$h(n)=O(n^2)$成立。

内容的提问来源于stack exchange，提问作者Ski Mask