增长量级

概述

增长量级 描述运行时间随输入规模增长的速率，忽略常数因子和低阶项。它使我们能够比较不同算法在输入规模增大时的相对效率，是算法分析的核心抽象。

定义

增长量级

函数 $g(n)$ 是 $f(n)$ 的增长量级，记为 $f(n)=\Theta (g(n))$，当且仅当存在正常数 $c_1,c_2,n_0$，使得对所有 $n\ge n_0$，有 $0\le c_{1}g(n)\le f(n)\le c_{2}g(n)$。增长量级忽略了常数因子和低阶项。

核心性质

• 忽略常数因子：$6n^2$ 和 $n^2$ 具有相同的增长量级 $\Theta (n^2)$。
• 忽略低阶项：$n^2+3n+100$ 的增长量级为 $\Theta (n^2)$。
• 常见增长量级（从慢到快）：$\Theta (1)<\Theta (\lg n)<\Theta (n)<\Theta (n\lg n)<\Theta (n^2)<\Theta (n^3)<\Theta (2^n)<\Theta (n!)$。
• 增长量级使算法比较变得简单：当 $n$ 足够大时，较低增长量级的算法总是优于较高增长量级的算法。

章节扩展

第2章：入门

• 2.2 算法分析：引入增长量级的概念，说明为何关注渐近行为而非精确运行时间。对比插入排序 $\Theta (n^2)$ 与归并排序 $\Theta (n\lg n)$ 的增长量级差异。

第1章：算法在计算中的角色

• 1.2 算法作为一种技术：通过具体数值说明不同增长量级在实际应用中的巨大差异，强调高效算法的重要性。

参见

• 运行时间
• 时间复杂度
• 最坏情况分析