14. 求和与渐进分析初步

我们都清楚等差数列的求和公式：

以及等比数列的求和公式（$q\ne 0$）：

当 $n\to \mathrm{\infty }$ 且 $|q|<1$ 时几何级数的和

这是一些十分基础且常用的求和公式，本节将详细研究一下这些和式。

我们称上述这些等式右边的不涉及求和号的表达式为 闭型，其不仅简明，而且容易计算。使用归纳法验证上述的公式是十分简单的，但问题在于我们不清楚这些式子是如何得来的。下面简单介绍一些基础的推导方法：

1. 扰动法

顾名思义，就是通过观察和式的内在规律，对和式做一些操作使得能轻易求出闭型。具体做什么要根据所求和式决定，16. 母函数 将介绍更多例子。以等比数列求和为例，考虑令

等式两边同乘 $-q$ 有

两式相加得

从而得到上式。

2. 逐项求导

将一些常用、已知的和式及其闭型求导可以得到更多和式的闭型。例如我们欲求 ${\displaystyle \sum _{i=1}^{n-1}i{x}^i}$ 的闭型，注意到 $(x^i{)}^{\prime }=i{x}^{i-1}$，对上面提到的等比数列求和公式左右求导，容易得到

进一步地，若 $|x|<1$，级数

3. 猜测闭型的样子

例如，我们想要求出自然数平方和 ${\displaystyle \sum _{x=1}^n{x}^2}$ 的闭型，但这个式子不适合使用扰动法，也无法使用逐项求导。但我们通过对自然数和的闭式进行观察，猜测这个我们要求的式子的闭型可能是一个三次多项式，因此考虑直接令

并通过取 $x=0,1,2,3$ 或更多的值，建立关于 $A,B,C,D$ 的线性方程组，解出系数的值。具体计算过程不表，最终我们会得到

这里的思想在于，如果我们认为求解的式子结果是一个多项式，且推测出了该多项式的最高幂次，就可以通过直接设出该多项式代值得出方程组求解系数。然而，有可能我们的猜想从一开始就是错的，因此当我们得到结果之后，务必要使用归纳法等方法证明结果是对的。

然而并不是所有求和式子都能找到闭型，例如所谓的 调和数（Harmonic Number）

当 $n\to \mathrm{\infty }$ 时，上式称作 调和级数。

我们通过一个经典问题来直观感受一下调和级数：

不过尽管没有办法给出该和式的闭型，我们仍然能够构造一些式子来估计它的上下界。

我们首先称一个函数 $f$ 是 单调递增（或称严格递增）的，当且仅当对任意 $x<y$ 有 $f(x)<f(y)$；$f$ 是 弱递增（或称 单调不减）的，当且仅当对任意 $x<y$ 有 $f(x)\le f(y)$，同理可以定义单调递减函数与弱递减函数。

对于单调函数，我们可以通过对函数积分来粗略估计和式中这一系列离散和的上下界。具体而言：

设 $f$ 是函数，$S={\displaystyle \sum _{i=a}^{b}f(i)}$，$I={\displaystyle {\int }_a^{b}f(x)\mathrm{d}x}$。若 $f$ 是 弱递增 函数，则

$$I+f(a)\le S\le I+f(b)$$

对应地，若 $f$ 是 弱递减 函数，则

$$I+f(b)\le S\le I+f(a)$$

不过由于调和级数非常常见，数学家给出了更加精确的近似：

式中 $\gamma$ 称作 欧拉常数，约为 $0.577215664$，$ϵ(n)$ 为余项函数，对任意 $n$ 满足 $ϵ(n)\in (0,1)$，且随 $n$ 增大逐渐趋近于 $0$。

有时我们需要计算多重求和号包裹的式子，一般而言，我们希望先算出内层式子的闭型，再一层一层逐步算出整个式子的闭型。如果内部式子没有明显闭型，我们希望能够调换求和顺序，一般也就能解决一大部分多重求和问题了。调换求和顺序的依据是 Fubini 定理，其内容为：

Fubini 定理^[1]：
设函数 $f(x,y)$ 是定义在 ${\mathbb{R}}^p\times {\mathbb{R}}^q$ 上的可积函数，其中 $x\in {\mathbb{R}}^p$，$y\in {\mathbb{R}}^q$，则重积分

$${\int }_{{\mathbb{R}}^p\times {\mathbb{R}}^q}f(x,y)\mathrm{d}x\mathrm{d}y$$

可以分解为任意积分次序的累次积分，即

$${\int }_{{\mathbb{R}}^p\times {\mathbb{R}}^q}f(x,y)\mathrm{d}x\mathrm{d}y={\int }_{{\mathbb{R}}^p}\mathrm{d}x{\int }_{{\mathbb{R}}^q}f(x,y)\mathrm{d}y={\int }_{{\mathbb{R}}^q}\mathrm{d}y{\int }_{{\mathbb{R}}^p}f(x,y)\mathrm{d}x$$

对离散的求和而言，若求和式子

$$\sum _{i\in I}\sum _{j\in J_i}{a}_{i,j}$$

满足 $a_{i,j}$ 非负或求和式绝对收敛，则该求和式可以任意调换求和顺序，即

$$\sum _{i\in I}\sum _{j\in J_i}{a}_{i,j}=\sum _{j\in J}\sum _{i\in I_j}{a}_{i,j}$$

大概了解了和式的处理方法后，我们进一步考虑连乘式，连乘的处理相当简单，对其取对数就能将连乘化为加和。形式化的说，设 $P=\prod _{i=1}^{n}f(i)$，两边取对得到 $\ln P=\sum _{i=1}^n\ln f(i)$，求出和式的闭型或近似后再取指即可。

我们以 $n!$ 为例，阶乘在组合数学中十分常见。对其取对数后得到的 $\sum _{i=1}^n\ln i$ 同样没有闭式。套用上面的过程得到的粗略上下限此处不表。我们直接给出目前 $n!$ 的一个十分精确且重要的估计：

斯特林公式：对任意 $n\ge 1$

$$n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n{e}^{ϵ(n)}$$

式中 ${\displaystyle \frac{1}{12n+1}}\le ϵ(n)\le {\displaystyle \frac{1}{12n}}$

上面给出的对调和数与阶乘的近似式子表达形式有点繁琐。我们清楚对调和数而言，式中对最终结果影响最大的项为 $\ln n$，其余项对结果的影响微乎其微。同理，斯特林公式中的 $ϵ(n)$ 一般很小，对式子的影响同样可以忽略。因此，我们考虑用一种简洁的方式来表述这一事实：

我们称函数 $f$ 与函数 $g$ 渐进相等，当且仅当

$$\underset{x\to \mathrm{\infty }}{lim}\frac{f(x)}{g(x)}=1$$

记作 $f\sim g$。

这样我们可以记 $H_n\sim \ln n$，更精确一点，我们可以记为 $H_n-\gamma \sim \ln n$，但后者不能记作 $H_n\sim \gamma +\ln n$，因为依据上面的定义，$H_n\sim \ln n+c$，其中 $c$ 为任意常数。类似地，我们记 $n!\sim \sqrt{2\pi n}({\displaystyle \frac{n}{e}}{)}^n$。

渐进相等主要关注两个函数中对函数增长影响最大的项。当两个函数渐进相等，表明两个函数以相同的速率增长。渐进相等关系与相等关系都是 等价关系。

我们接下来介绍一些其它的渐进符号，这些渐进符号在分析不同算法的理论运行速度上是很有用的。

我们称函数 $f$ 渐进小于函数 $g$，当且仅当

$$\underset{x\to \mathrm{\infty }}{lim}\frac{f(x)}{g(x)}=0$$

记作 $f=\mathcal{o}(g)$。

渐进小于关系是一个严格偏序关系，其表明对于满足 $f=o(g)$ 的函数 $f$ 增长速度是 严格小于 函数 $g$ 的，通常用于比较两个函数或算法时使用。

小 $\mathcal{o}$ 具有如下性质：

• 若 $a\le b$，则 $x^a=\mathcal{o}(x^b)$。
• 对任意 $ϵ>0$，$\ln x=\mathcal{o}(x^{ϵ})$，即对数的增长一定比幂函数缓慢。
• 对任意 $a,b\in \mathbb{R},a>1$，$x^b=\mathcal{o}(a^x)$，即多项式的增长一定比指数函数慢。

与较为严格的渐进小于相对，渐进增长阶 描述了一个函数的 增长上界，为了方便理解，我们记

若

$$\underset{x\to \mathrm{\infty }}{lim}sup\frac{|f(x)|}{g(x)}<\mathrm{\infty }$$

式中 $sup$ 意指 上极限。此时我们记 $f=\mathcal{O}(g)$。

大 $\mathcal{O}$ 符号是分析算法运行效率时最常用的符号。使用大 $\mathcal{O}$ 符号意味着，我们不关心 $f$ 与 $g$ 中的低阶项、常数因子，也不关心 $f$ 是否在某个时刻事实上大于 $g$，我们只关心 $f$ 的变化趋势的上界是否在 $g$ 的常数倍之下，如下图所示：

这也是为什么我们在上面的定义中引入了上极限，因为 ${\displaystyle \frac{f(x)}{g(x)}}$ 的极限在无穷大处可能不存在，但我们仍然可以使用大 $\mathcal{O}$ 符号来描述 $f$ 的增长趋势。

事实上，大 $\mathcal{O}$ 符号的正式定义是这样的：

对函数 $f$ 与 $g$，若存在常数 $c$ 与 $x_0$，使得对任意 $x\ge x_0$，有

$$|f(x)|\le cg(x)$$

那么 $f=\mathcal{O}(g)$。

若 $f=\mathcal{o}(g)$ 或 $f\sim g$，则 $f=\mathcal{O}(g)$。对应地，该命题的逆命题是错误的，若 $f=\mathcal{o}(g)$，那么 $g\ne \mathcal{O}(f)$。

大 $\mathcal{O}$ 符号有如下两条在分析算法运行的时间复杂度时至关重要的性质：

• 对任意 $n$ 次多项式 $P_n(x)$，$P_n(x)=\mathcal{O}(x^n)$。
• 对任意常函数 $f(x)=C$，$f(x)=\mathcal{O}(1)$。

与渐进小于与描述增长上界的渐进增长阶类似，我们也有描述渐进大于与增长下界的符号：

我们称函数 $f$ 渐进大于函数 $g$，当且仅当 $g=\mathcal{o}(f)$，记作 $f=\omega (g)$。

若 $g=\mathcal{O}(f)$，记 $f=\mathrm{\Omega }(g)$。

当一个函数的渐进上下界相同时，即

若 $f=\mathcal{O}(g)$ 且 $g=\mathcal{O}(f)$，记作 $f=\mathrm{\Theta }(g)$。

显然 $\mathrm{\Theta }$ 也是等价关系，但 $\mathrm{\Theta }$ 不等同于渐进相等 $\sim$。大 $\mathrm{\Theta }$ 忽略了低阶项与常数项对函数增长的影响，其可以被简单理解为，若 $f=\mathrm{\Theta }(g)$，则 $f$ 与 $g$ 的增长速度恰好处在同一个量级。

渐进符号十分好用，但也很容易因为乱用这些渐进符号犯下错误，尤其是大 $\mathcal{O}$ 符号，例如：

• $f=\mathcal{O}(g)$ 中的等号不是相等的意思，这个式子也不是一个等式，$\mathcal{O}(g)$ 也不是一个有具体含义的量，这个式子也不能拆开。我们在后续的数据结构课程中常常见到“程序运行的时间复杂度为 $\mathcal{O}(\cdots )$”的说法是一种方便的简称，严格的说法应该是“程序的运行时间 $f$ 满足 $f=\mathcal{O}(\cdots )$”。
• 前面提过，$\mathcal{O}(1)$ 不是具有确切含义的一个量，因此也不能相加，因此我们不能认为 $\sum _{i=1}^{n}i=\sum _{i=1}^n\mathcal{O}(1)=\mathcal{O}(n)$，依据本文最开始我们知道 $\sum _{i=1}^{n}i=\mathrm{\Theta }(n^2)$。
• 指数函数中的底数对于函数的增长率影响是巨大的，因此不能随意更改指数，例如 $4^x=\mathcal{O}(2^x)$ 就是不对的。
• 渐进关系在部分复合函数中无法保留，例如 $f\sim g$ 不意味着 $2^f=\mathrm{\Theta }(2^g)$，但确实有一些复合函数可以保留甚至加强这种渐进关系，例如若 $f=\mathrm{\Theta }(g)$，则 $\ln f\sim \ln g$。

最后需要指出的是，虽然一个算法可能拥有更好的渐进时间复杂度，并不意味着实际运行中该算法运行速度会更快。例如，时间复杂度为 $\mathcal{O}(n^{2.55})$ 的矩阵乘法算法只有在矩阵特别特别大时才有可能比简单的 $\mathcal{O}(n^3)$ 复杂度算法运行速度更快；再或者，指数复杂度的算法在极小的数据范围下运行速度也可能不会比某阶数极高的多项式复杂度算法慢多少。