第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\)慢?。确实，我们也可以表示为\(\Omicron(n^5)\)、\(\Omicron(n^6)\)。
实际上，对于任何常数\(c \ge 3\)，\(\Omicron(n^c)\)都可以表示。
\(\Omega\)符号
描述函数的渐近下界（lower bound）。也就是说，函数的增长速度至少和某个速率一样快，基于\(\Omicron\)符号。
例如，\(7n^3+100n^2-20n+6\)。其中的最高阶项的增长速度至少和\(n^3\)一样快，所以是\(\Omega(n^3)\)。同样也可以是\(\Omega(n^2)\)和\(\Omega(n)\)。
实际上，对于任何常数\(c \le 3\)，\(\Omicron(n^c)\)都可以表示。
\(\Theta\)符号
描述函数的渐近紧确界（tight bound）。
例如，\(7n^3+100n^2-20n+6\)。渐近上界\(\Omicron(n^3)\)，渐近下界\(\Omega(n^3)\)，夹逼得渐近紧确界为\(\Theta(n^3)\)。
3.2 渐近符号：形式化定义
\(\Omicron\)符号
对于给定的函数\(g(n)\)，
\(f(n)\in \Omicron(g(n))\)，一般书写为\(f(n)= \Omicron(g(n))\)，计算可转化为\(0 \le f(n) \le cg(n)\)
\(\Omega\)符号
对于给定的函数\(g(n)\)，
\(f(n)\in \Omega(g(n))\)，一般书写为\(f(n)= \Omega(g(n))\)，计算可转化为\(0 \le cg(n) \le f(n)\)
\(\Theta\)符号
对于给定的函数\(g(n)\)，
\(f(n)\in \Theta(g(n))\)，一般书写为\(f(n)= \Theta(g(n))\)，计算可转化为\(c_1g(n) \le f(n) \le c_2g(n)\)
定理：对于任意两个函数\(f(n)\)和\(g(n)\)，当且仅当\(f(n)=\Omicron(g(n))\)且\(f(n)=\Omega(g(n))\)时，有\(f(n)=\Theta(g(n))\)
\(\omicron\)符号
对于给定的函数\(g(n)\)，
\(\omega\)符号
对于给定的函数\(g(n)\)，