思考与提高

最高阶项决定一切

我们发现最高阶项决定一切, 从而将一个函数转化为关于$\Theta$渐近形式, 这在直觉上是对的.

像上面这样, 在本书中我们多次提到 最高阶项决定一切, 大部分情况下它是正确的. 但需要更严谨的表述. “最高阶项决定一切” 这种表述很显然是基于多项式, 事实上它在多项式条件下确实是对的.

也就是说: 对于实系数多项式, 其渐近行为由最高次项决定. 严格的定理如下:

定理

设 $$f(n)=a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0,a_k\ne 0$$ 则当 $n\to \infty$ 时, $$f(n)\sim a_k{n}^k\text{即}\underset{n\to \infty }{\lim }\frac{f(n)}{a_k{n}^k}=1$$

证明

$$\frac{f(n)}{a_k{n}^k}=\frac{a_k{n}^k+a_{k-1}{n}^{k-1}+\cdots +a_0}{a_k{n}^k}=1+\frac{a_{k-1}}{a_k}\cdot \frac{1}{n}+\frac{a_{k-2}}{a_k}\cdot \frac{1}{n^2}+\cdots +\frac{a_0}{a_k}\cdot \frac{1}{n^k}$$

当 $n\to \infty$, 所有 $\frac{1}{n^j}\to 0$（$j\ge 1$）, 所以:

$$\underset{n\to \infty }{\lim }\frac{f(n)}{a_k{n}^k}=1$$

即 $f(n)\sim a_k{n}^k$

由此可得:

• $f(n)=\Theta (n^k)$
• $f(n)=O(n^k)$
• $f(n)=\Omega (n^k)$

该证明相当简单, 且与直觉相符, 是一种显而易见的证明.

但数学中的函数并不只有这些, 我们还有一些常见的函数, 例如指数函数, 沿用上述证明，进一步推广也是有效的. 也就是说对于指数函数, 我们同样有最高阶项决定一切这样的表述.

然而有一些函数不满足我们上面的这个表述, 常见的是非加性结构: $T(n)=2T(n/2)+n$, 这种结构不能靠上面的方法直接证明, 相反，我们需要下一章将学到的主定理等工具. 这里暂时不做讨论. 另外振荡或交替项也很难探讨, 如 $f(n)=n+(-1{)}^{n}n$, 它们不收敛, 在极限讨论的时候，主导行为也相当复杂. 另外, 对数函数和 $e^n$ 这些不同函数混合的情况，也要进行单独考虑.

主导项

事实上, 在渐近分析中，真正重要的是 主导项（dominant term），即随着 $n\to \infty$，其占比趋于 1 的项。

若函数可写为和式： $$f(n)=f_1(n)+f_2(n)+\cdots +f_m(n)$$ 且存在某个 $f_i(n)$，使得对所有 $j\ne i$， $$\underset{n\to \infty }{\lim }\frac{f_j(n)}{f_i(n)}=0$$ 则称 $f_i(n)$ 为主导项，且 $$f(n)\sim f_i(n),\text{即 }f(n)=(1+o(1))f_i(n)$$

这就是 “主导项决定渐近行为” 的一般原则。

在渐近分析中，“最高次项决定一切” 是一个常见但需要谨慎理解的说法。它在许多情况下是成立的，尤其对于多项式函数或具有主导项的函数，但在更一般的情形下需要附加条件。

Warning

该章节仍在编写, 欢迎在 GitHub仓库 提交PR贡献内容.