算法导论——函数的增长

上次提到的增长量级简单的说明了算法的效率，而且还使用了一个符号$\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$增大时，前一项与后一项之比越来越趋于黄金分割。