证明线性级、多项式级、指数级、阶乘级的大小关系

本文用分析学语言严格证明线性级、多项式级、指数级、阶乘级的大小关系。本文所说的大小关系均指各个数量级增长速率的大小关系。

首先用数学语言来描述各个数量级： $(n\in \mathbb{N}^*,\ n\to\infty)$

线性级： $n$
多项式级： $n^k, \ \ k\in\left (1, +\infty\right)$
指数级： $q^n, \ \ q\in\left (1, +\infty\right)$
阶乘级： $n! = \prod_{i=1}^n i$

对于形如 $\displaystyle \frac{C}{n^a}\ (\ a>0,\ C\in\mathbb{R})$ 的式子，当 $n\to\infty$ ，该式趋于0是显然的：

(1) $\begin{equation*}\displaystyle \forall \epsilon>0, \exists N=\left[\left(\frac{C}{\epsilon}\right)^{\frac{1}{a}}\right], \forall n>N: \ \lvert \frac{C}{n^a}\rvert < \epsilon \end{equation*}$

1. 线性级和多项式级

由(1)式得

(2) $\begin{equation*}\displaystyle \frac{n}{n^k} = \frac{1}{n^{k-1}}\to 0\ \ (n\to\infty)\end{equation*}$

故线性级小于多项式级。

2. 多项式级和指数级

设 $h=q-1>0$ ，则

(3) $\begin{equation*}\displaystyle q^n=(h+1)^n=\sum_{i=0}^n \binom{n}{i} h^i>\frac{n\cdot (n-1)}{2}\cdot h^2\end{equation*}$

由(1), (3)式和夹逼定理得

(4) $\begin{equation*}\displaystyle 0<\frac{n}{q^n}<\frac{n}{\frac{n\cdot (n-1)}{2}\cdot h^2}=\frac{2}{(q-1)^2}\cdot \frac{1}{(n-1)}\to 0\ \ (n\to\infty)\end{equation*}$

(5) $\begin{equation*} \lim_{n\to\infty} \frac{n}{q^n}=0\end{equation*}$

由(5)式得

(6) $\begin{equation*}\displaystyle \frac{n^k}{q^n}=\left( \frac{n}{(\sqrt[k]{q})^n} \right)^k\to 0\ \ (n\to\infty)\end{equation*}$

故多项式级小于指数级。

3. 指数级和阶乘级

由(1)式和夹逼定理得

(7) $\begin{equation*} 0<\frac{q^n}{n!}=\frac{q^q}{q!}\cdot \prod_{i=q+1}^n \frac{q}{i}<\frac{q^q}{q!}\cdot \frac{q}{n}=\frac{q^{q+1}}{q!}\cdot \frac{1}{n}\to 0\ \ (n\to\infty)\end{equation*}$

(8) $\begin{equation*} \lim_{n\to\infty}\frac{q^n}{n!}=0\end{equation*}$

故指数级小于阶乘级。

结语：综上，有大小关系：线性级<多项式级<指数级<阶乘级。

xhdeng's blog