算法导论——函数的增长
上次提到的增长量级简单的说明了算法的效率，而且还使用了一个符号\(\Theta\)。这次给出这个符号更精确的定义。在数学上，运行时间随着数据量增长的规律可以看为一个函数，因此这篇文章主要从更全局泛化的谈谈函数的增长。
当输入规模足够大，使得只有运行时间的增长量级有关时，我们需要研究算法的渐近效率。这里的渐近效率指的是当输入规模无限增加时，在极限中，算法的运行时间如何随着输入规模的变大而增加。下面首先定义几种监禁记号。
渐近记号
一般来说，对于运行时间函数的定义域是\(\mathbb N = \{0,1,2,....\}\)，也就是自然数。但是渐近记号也可以活用到实数域，或者限制到自然数的一个子集。对于上次插入排序的分析，我们知道它的运行时间可以被总结为\(an^2 +bn + c\)，我们将它记为\(\Theta(n^2)\)。渐近记号除了用于表示运行时间，也可以用来分析运行空间，甚至是与算法无关的函数的分析。
虽然之前关注的情况是最坏情况的输入，但是分析时我们希望能用渐近记号来描述任何输入，下面介绍几种不同渐近记号的定义。
\(\Theta\)记号
对于一个给定函数\(g(n)\)，那么\(\Theta(g(n))\)表示的是以下函数的集合： \[ \Theta(g(n)) = \{f(n):存在正常量c_1,c_2,n_0,使得对所有n\ge n_0,有0\leq c_1g(n)\leq f(n) \leq c_2 g(n)\} \] 这里可以看到，我们通过函数\(g(n)\)和两个常数\(c_1,c_2\)，给了函数\(f(n)\)一个上界和一个下界。由于\(\Theta(n)\)是一个集合，因此更严格的写法是：\(f(n) \in \Theta(g(n))\)，但是我们简单记成\(f(n) = \Theta(g(n))\)，这样更简便。对于所有\(n \ge n_0\)，函数\(f(n)\)在一个常量因子内等于\(g(n)\)。我们称\(g(n)\)是\(f(n)\)的一个渐近紧确界。
\(\Theta(g(n))\)的定义要求每个成员\(f(n)\in \Theta(g(n))\)都渐近非负，这意味着\(g(n)\)也需渐近非负。这个假设对其他的渐近记号也是一样成立。 ### \(O\)记号 ### \(\Theta\)记号渐近地给出一个函数的上界和下界，当只有一个渐近上界时，我们使用\(O\)记号。\(O(g(n))\)表示的是以下函数的集合： \[ O(g(n)) = \{f(n):存在正常量c,n_0,使得对所有n\ge n_0,有0 \leq f(n) \leq c g(n)\} \]
由于\(O\)记号的定义，下面这个式子也是正确的：\(n = O(n^2)\)，因为\(O(n^2)\)给出的是上界，但是并不要求是多么确切的上界。
使用\(O\)记号的好处是，它用来表示最坏情况下的运行时间时，对任何输入都是正确的。比如之前的插入排序，我们说了，最坏情况下运行时间为\(\Theta(n^2)\)，但这并不意味着对于所有输入都满足，因为在最好的情况下运行时间为\(\Theta(n)\)，如果使用\(O\)来描述则可以拓展到任意输入，因为不管最坏的情况就是给了一个上界。 ### \(\Omega\)记号 ###
不用说，\(\Omega\)记号给出的就是渐近下届： \[ \Omega(g(n)) = \{f(n):存在正常量c,n_0,使得对所有n\ge n_0,有0\leq cg(n)\leq f(n) \} \]
\(\Omega\)记号就适用于最优情况，例如插入排序，我们可以指出它的运行时间为\(\Omega(n)\)，但是说它最坏情况下运行时间为\(\Omega(n^2)\)也是正确的。显然\(\Omega\)记号的实际应用是最少的。
等式与不等式中的渐近记号
使用渐近记号是非常有用的。我们以后可能会使用类似下式的“奇怪”写法： \[ 2n^2 + 3n + 1 = 2n^2 + \Theta(n) \] 这样的写法是没有问题。我们可以使用渐近记号消除一个等式中无关紧要的细节。例如之前的归并排序，我们可以将最坏情况的运行时间写成递归式： \[ T(n) = 2T(\frac{n}{2})+ \Theta(n) \] (一个归并排序被分解成两个序列的归并排序，在加上一个\(\Theta(n)\)的合并消耗)
后者用渐近记号表示的函数成为匿名函数。一个表达式中匿名函数的数目可以理解为等于渐近记号出现的次数。比如在表达式\(\sum_{i=1}^nO(i)\)中，只有一个匿名函数\(O(i)\)，而不同于下式： \[ O(1)+O(2)+...+O(n) \] 实际上后者并没有什么清晰的解释(对于前者我的理解是就像插入排序最坏的情况一样，只有一个匿名函数，最后运行时间是\(nO(n) = O(n^2)\))。
有时候渐近记号也出现在等式的左边： \[ 2n^2 + \Theta(n) = \Theta(n^2) \] 总之在等式链中渐近记号的使用是非常灵活的，而这也让我们能更关注于最需要关心的部分。 ### \(o\)记号 ### 之前说的\(O\)记号，表示的渐近上界，它有可能是一个紧确的，也可能不是，例如\(2n = O(n^2)\)就不是紧确的，而\(2n^2 = O(n^2)\)则是紧确的。因此这里再引入一个新的渐近记号\(o\)，表示的是非渐近紧确上界。我们定义\(o(g(n))\)如下： \[ o(g(n)) = \{f(n): 对任意常量c>0,存在常量n_0>0,使得对于所有n\ge n_0,有0\leq f(n) < cg(n) \} \] 举个例子：\(2n = o(n^2)\)是正确的，但是\(2n^2 = o(n^2)\)就是错误的了。 直观上来说，对于渐近记号\(o\)，当\(n\)趋于无穷时，函数\(f(n)\)相对于\(g(n)\)就微不足道了，即： \[ \lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = 0 \] 实际上我们在数学中经常看到用\(o\)来表示高阶无穷小，也符合上述的等式，但是在这里，我们依然限定函数是渐近非负的。
###\(\omega\)记号 ### \(\omega\)记号与\(\Omega\)记号的关系类似于\(o\)记号与\(O\)记号的关系。\(\omega\)表示一个非渐近紧确的下界： \[ \omega(g(n)) = \{f(n): 对任意常量c>0,存在常量n_0>0,使得对于所有n\ge n_0,有0\leq cg(n) < f(n) \} \]
举个例子：\(n^2 = \omega(n)\)是正确的，但是\(2n = \omega(n)\)是错误的。同样，直观上讲，对于渐近记号\(\omega\)，当\(n\)趋于无穷时，函数\(g(n)\)相对于函数\(f(n)\)就微不足道了： \[ \lim_{n\rightarrow \infty} \frac{f(n)}{g(n)} = \infty \]
对于两个函数\(f,g\)的渐近比较和两个实数\(a,b\)的比较之间可以做一个类比： \[ f(n) = O(g(n)) \rightarrow a\leq b\\ f(n) = o(g(n)) \rightarrow a < b\\ f(n) = \Omega(g(n)) \rightarrow a\ge b\\ f(n) = \omega(g(n)) \rightarrow a > b\\ f(n) = \Theta(g(n)) \rightarrow a = b \]
但是需要注意的是，任意两个实数\(a,b\)一定满足于\(a>b,a < b,a =b\)三种情况的一种，但是不是任意的函数之间都可以做渐近比较，例如我们不能渐近比较\(n^2\)与\(n^{1+\sin n}\)。
其他
除了渐近记号，这一章还介绍了一些其他的概念，单调性，向上向下取整，模运算等等。对于这些基本的知识这篇文章就不多提了，仅写一些平时不容易被注意到知识点。
阶乘
实际上阶乘是一个很简单的概念，定义如下： \[ n!=n\cdot(n-1)\cdot...\cdot 1 \]
我在这里要介绍的是阶乘有一个斯特林近似公式： \[ n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\left(1 + \Theta(\frac{1}{n})\right) \]
它给出了一个更紧致的上界和下届。实际上我们很容易得到： \[ n!=o(n^n)\\ n!=\omega(2^n)\\ \] 而通过斯特林公式可以进一步证明： \[ \text{lg}(n!) = \Theta(n\text{lg}n) \] 对于所有\(n\ge 1\)，也有： \[ n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{a_n} \] 其中\(\frac{1}{12n+1}< a_n < \frac{1}{12n}\)。
多重函数
我们使用记号\(f^{(i)}(n)\)来表示函数\(f(n)\)多次作用于一个初值\(n\)上：对于非负数\(i\): \[ f^{(i)}(n) = \{ \begin{array} n & i=0\\ f(f^{(i-1)}(n)) & i>0 \end{array} \] 例如\(f(n) = 2n\)，则\(f^{(i)}(n) = 2^in\)。 ### 多重对数函数 ###
我们使用\(\text{lg}^*\)来表示多重对数。假设\(\lg^{(i)}\)定义如上，那么多重对数函数定义为： \[ \text{lg}^* = \min\{i\ge 0:\text{lg}^{(i)}n\leq 1\} \] 多重对数函数增长非常缓慢： \[ \text{lg}^*2 = 1\\ \text{lg}^*4 = 2\\ \text{lg}^*16 = 3\\ \text{lg}^*65536=4\\ \text{lg}^*2^{65536}=5 \] 实际中，我们很难遇到\(n>5\)的规模。
斐波那契数
我们一直知道斐波那契数列是以指数形式增长的，这里从另一个更新奇的角度说明这个问题。 \[ F_0=0\\ F_1 = 1\\ F_i = F_{i-1} + F_{i-2},i\ge 2 \]
实际上斐波那契数列与黄金分割率\(\phi\)以及其共轭数\(\hat\phi\)有关，他们是下面方程的两个根： \[ x^2 = x+1 \] 并且： \[ \phi = \frac{1+\sqrt 5}{2},\hat\phi = \frac{1-\sqrt 5}{2} \] 我们有： \[ F_i = \frac{\phi^i - \hat\phi^i}{\sqrt 5} \] 由于后一项随着\(i\)增大可忽略不计，因此从上式可以看出，斐波那契数是指数形式增长的。有趣的是当\(n\)增大时，前一项与后一项之比越来越趋于黄金分割。