第3章 描述运行时间

本章研究算法的渐近（asymptotic）效率。我们关心的是，当输入规模足够大时，算法运行时间与随着输入规模的增大发生怎样的变化，即研究\(T(n)\)随着\(n\)的增大发生怎样的变化。

3.1 \(\Omicron\)符号，\(\Omega\)符号，\(\Theta\)符号

\(\Omicron\)符号

描述函数的渐近上界（upper bound）。换句话说，它表示一个函数的增长速度并不超过一定速率的速度，基于最高阶项。

例如，\(7n^3+100n^2-20n+6\)。它的最高项是\(7n^3\)，所以我们说这个函数的增长率是\(n^3\)。因为这个函数的增长率不大于\(n^3\)，所以我们表示为\(\Omicron(n^3)\)。你可能会好奇，我们也可以将其表示为\(\Omicron(n^4)\)。为什么？因为其增长率确实比\(n^4\)慢