算法算法分析

N节点二叉树种类数的渐近估阶：复变函数的奇点与幂级数的收敛半径

字数统计: 4.1k字   |   阅读时长: 17分
, ,

摘要: 复变函数的奇点与幂级数的收敛半径

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，本文我们继续讨论算法分析相关的问题。

在文章 二叉树的计数：直接方法与间接方法 中，我们通过生成函数推导了 N 节点的二叉树的种类数 $T_{N}$，公式如下：

对于 $T_{N}$ 当 $N \rightarrow\infty$ 的渐近估阶问题，使用欧拉-麦克劳林公式或斯特林公式，可以推导出以下结论：

本文我们从复变函数的角度出发来讨论 $T_{N}$ 的渐近估阶，最终给出以上公式。

$T_{N}$ 的生成函数为 $T(z) = \sum\limits_{N=0}\limits^{\infty}T_{N}z^{N}$，在前面的文章中我们知道 $T(z) = \frac{1-\sqrt{1-4z}}{2z}$。记 $G(z) = zT(z)$。

将生成函数 $G(z)$ 视为一个复变函数，分析该函数在复平面上的奇点的位置，可以得到其幂级数展开的系数的指数增长的阶。

本文我们简要介绍一下在算法分析中将生成函数视为复变函数的动机，然后简要讨论一下复变函数的奇点与其幂级数系数的关系，然后根据这些讨论，我们解决上述的卡特兰数渐近估阶问题。

引入复变函数的动机

在前面的文章中，我们对算法分析问题的讨论主要围绕着两个主题。一个是渐近分析、另一个是生成函数。

假设数据规模为 $N$ 时，某个算法的时间开销为 $c_{N}$。如果我们知道 $c_{N}$ 的公式（通常是一个和式），那么一个自然的问题就是当 $N\rightarrow\infty$ 时，对 $c_{N}$ 的增长的阶做出估计，这是渐近估阶解决的问题。

很多时候我们并不知道 $c_{N}$ 的公式，而只能得到一个递推式，引入生成函数 $C(z) = \sum\limits_{N=0}\limits^{\infty}c_{N}z^{N}$ 后，可以将递归式转化为生成函数满足的方程，解出方程得到 $C(z)$ 后，再将其展开成幂级数，取 $z^{N}$ 项的系数即可得到 $c_{N}$，这是生成函数解决的问题。

生成函数 $C(z)$ 还可以视为一个复变函数，那么这个函数也给出了复平面上的一个变换。由生成函数的定义 $C(z) = \sum\limits_{n=0}\limits^{\infty}c_{N}z^{N}$，这就给出了 $C(z)$ 在原点的幂级数展开，根据复变函数相关的定理，$C(z)$ 在原点是解析的。$C(z)$ 可能会有一些奇点，其中距离原点最近的奇点决定了 $\sum\limits_{n=0}\limits^{\infty}c_{N}z^{N}$ 的收敛圆盘，称其为主奇点。

对于一个复变函数来说，奇点提供了函数的级数展开的系数的丰富信息，其中就包括系数增长的渐近速率。因此将生成函数 $C(z)$ 视为在原点可以展开成幂级数的复变函数，然后分析该函数的奇点，对于 $c_{N}$ 增长的估阶很有帮助。

数列的上极限

首先介绍数列的上极限的概念。

$\{a_{n}\}$ 为一数列，非空集合 $E$ 的定义如下：

记 $a^{* } = \sup E$，$a_{* } = \inf E$ 分别称为 $a_{n}$ 的上极限和下极限，分别记为：

引入上极限的原因在于，一个数列可能不收敛（没有极限），但考虑数列的所有收敛子列，这些收敛子列的极限存在一个上确界，这个上确界提供了关于数列增长速率的信息。

数列的指数增长

有了数列的上极限的概念，下面定义数列的指数增长的概念，对于一个数列 $a_{n}$，如果：

也就是 $|a_{n}|^{\frac{1}{n}}$ 的上极限为 $K$ 时，则称 $a_{n}$ 是 $K^{n}$ 指数阶的，记为 $a_{n}\bowtie K^{n}$。

$a_{n}\bowtie K^{n}$ 同时限制了 $a_{n}$ 的上界和下界，对任意 $\epsilon > 0$，有：

  • 存在无穷多个 $n$ 使得 $|a_{n}| > (K - \epsilon)^{n}$ 成立。
  • 除了有限个 $n$ 之外，有 $|a_{n}| < (K + \epsilon)^{n}$ 成立（$|a_{n}|$几乎处处小于 $(K+\epsilon)^{n}$）。

以上两条等价于 $\limsup |a_{n}|^{\frac{1}{n}} = K$。

$a_{n}\bowtie K^{n}$ 可以写成 $a_{n} = K^{n}\theta(n)$，其中 $\theta(n)$ 满足以下条件，称其为次指数因子：

上式的上极限同样限制了 $\theta(n)$ 的上界和下界：$\theta(n)$ 的模几乎处处以有限指数形式增长的（以 $(1+\epsilon)^{n}$ 的形式），并且无限次地以衰减的指数形式（以 $(1 - \epsilon)^{n}$ 的形式）为下界。

下面这些都是典型的次指数因子，可以验证它们的 $\frac{1}{n}$ 次幂的上极限均为 1：

解析性的幂级数定义

定义在复平面上某个域 $\Omega$ 的函数 $f(z)$，如果对 $z_{0}$ 的某个邻域内，$f(z)$ 可以表示为一个收敛的幂级数：

则称 $f(z)$ 在点 $z_{0} \in \Omega$ 处是解析的。

此外，解析性还可以通过复可微，也就是柯西黎曼方程来定义，参考复变函数相关的书。

幂级数的收敛圆盘

考虑幂级数 $\sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$，定义 $R$ 为使得 $f_{n}x^{n}$ 有界的 $x > 0$ 的最大者。那么对于 $|z| < R$，有：

其中 M 为常数，$0 < k = |\frac{z}{R}|^{n} < 1$，因此 $|z| < R$ 时：

而上式右端是收敛的，因此 $\sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$ 收敛，记其和函数为 $f(z)$。

对于 $|z| > R$，$f_{n}z^{n}$ 无界，因此 $\sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$ 发散。

因此对于幂级数 $\sum\limits_{n=0}\limits^{\infty}f_{n}(z - z_{0})^{n}$，总有一个以 $z_{0}$ 为圆心的圆盘，在圆盘内部，该幂级数收敛，在圆盘外部，该幂级数发散。称该圆盘为幂级数的收敛圆盘，称其半径为幂级数的收敛半径，记为 $R_{conv}(f; z_{0})$。

下面我们要说明，一个幂级数的收敛半径包含了其系数增长速度的基本信息。

解析延拓与奇点

$f(z)$ 为一个在由一条简单闭曲线 $\gamma$ 所围成的区域 $\Omega$ 的内部有定义的解析函数，并设 $z_{0}$ 为 $\gamma$ 边界上的一点。如果存在某个包含 $z_{0}$ 的开集 $\Omega^{*}$ 上的解析函数 $f^{*}(z)$，使得 $\Omega \cap \Omega^{*}$ 上有 $f^{*}(z) = f(z)$，则称 $f$ 在 $z_{0}$ 点可以解析延拓。

如果 $f(z)$ 不能解析延拓到区域边界 $\gamma$ 上的某个点 $z_{0}$，称 $z_{0}$ 为 $f$ 的奇点。

收敛的幂级数在收敛圆盘内解析，也就是在收敛圆盘内没有奇点，但在收敛圆盘的边界上至少有一个奇点，由以下定理说明：

定理（边界奇点）

若 $f(z)$ 在原点解析，因此可以在原点邻域内展开为幂级数 $f(z) = \sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$，该幂级数具有收敛半径 $R$，则 $f(z)$ 在收敛圆盘边界 $|z| = R$ 上必有一个奇点。

如果幂级数的系数 $f_{n}$ 非负，上述定理还可以改进，即 Pringsheim 定理。这个定理非常重要，因为具有非负系数 $f_{n}$ 的幂级数刚好包含了全部的计数生成函数。

定理（Pringsheim）

若 $f(z)$ 在原点解析，因此可以在原点邻域内展开为幂级数 $f(z) = \sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$，该幂级数具有收敛半径 $R$，若系数 $f_{n}$ 均非负，$z = R$ 为 $f$ 的奇点。

有了 Pringsheim 定理，对于计数生成函数来说，只需要沿着正实轴方向研究解析性即可。

收敛半径界

有了前面的铺垫，下面我们来介绍本文的核心定理，该定理揭示了生成函数的距离原点最近的奇点的位置与系数的指数增长率的关系。

定理（指数增长公式、收敛半径界）

设 $f(z)$ 在原点解析，定义 $R$ 为距离原点最近的奇点的模：

则 $f_{n} = [z^{n}]f(z)$ 满足：

证明

由于 $f(z)$ 在原点处解析，因此在原点的邻域内 $f(z)$ 可以展开为幂级数 $f(z) = \sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$。其收敛半径为 $R_{conv}(f; 0)$。

由于幂级数在其收敛圆盘内均解析，因此 $R \geq R_{conv}(f; 0)$。

另一方面，又边界奇点定理，有 $R \leq R_{conv}(f; 0)$。

因此 $R = R_{conv}(f; 0)$。

由收敛半径的定义有，对任意 $\epsilon > 0$，$f_{n}(R - \epsilon)^{n}\rightarrow 0$，特别地，对于充分大的 $n$ 有 $|f_{n}|(R - \epsilon)^{n} < 1$，因此 $|f_{n}|^{\frac{1}{n}} < \frac{1}{R - \epsilon}$ 几乎处处成立。

另一方面，对任意 $\epsilon > 0$，$|f_{n}|(R + \epsilon)^{n}$ 不可能是一个有界的数列，否则 $\sum\limits_{n=0}\limits^{\infty}|f_{n}|(R+\frac{\epsilon}{2})^{n}$ 就将是一个收敛的级数。因此 $|f_{n}|^{\frac{1}{n}} > \frac{1}{R+\epsilon}$ 有无限多次成立。

以上两条正是 $f_{n}\bowtie (\frac{1}{R})^{n}$ 的定义。

$\Box$

因此对于生成函数 $f(z)$ 来说，如果记其系数的渐近增长为 $f_{n} = [z^{n}]f(z) = K^{n}\theta(n)$，其中 $K^{n}$ 为指数增长因子，$\theta(n)$ 为次指数增长因子。则以上定理给出了 $K = \frac{1}{R}$，这隐含了 $f_{n}$ 的一个比较松的上界 $f_{n} = O((\frac{1}{R} + \epsilon)^{n})$。

例如对于 $G(z) = zT(z) = \frac{1-\sqrt{1-4z}}{2}$，由于 $G(z)$ 含有 $(1 - 4z)^{\frac{1}{2}}$，而二项级数 $(1 + u)^{\frac{1}{2}}$ 对于 $|u| < 1$ 收敛，因此 $G(z)$ 对于 $|z| < \frac{1}{4}$ 收敛，这样根据上述收敛半径界定理，对任意 $\epsilon$ 有：

这是一个对生成函数 $G(z)$ 的系数的比较弱的上界估计。

要完整知道 $[z^{n}]f(z)$ 的渐近增长，我们还需要知道次指数因子 $\theta(n)$，而这与奇点的性质有关，对奇点性质的分析需要更深入的复变函数的知识，例如我们知道对于绝大部分情况，复变函数在奇点处可以洛朗展开，因此可以通过洛朗级数来分析奇点的性质，进而给出生成函数的系数的渐近行为。以后遇到相关例子的时候，再回来看这一块。

收敛半径逼近

将生成函数 $f(z)$ 作为复变函数去考察，除了可以推导出由收敛半径界给出的比较松的上界，还可以导出渐近等价性。

对于 $f_{n}$ 和 $g_{n}$，如果 $\lim\limits_{n\rightarrow\infty}\frac{f_{n}}{g_{n}} = 1$，称 $f_{n}$ 与 $g_{n}$ 在 $n\rightarrow\infty$ 时渐近等价。

定理（收敛半径逼近）

设 $f(z)$ 的收敛半径 $R > 1$，$f(1) \neq 0$，则对任意的实数 $\alpha \notin \{0, -1, -2, \cdots\}$，成立以下渐近等价性：

证明

由于 $f(z) = \sum\limits_{n=0}\limits^{\infty}f_{n}z^{n}$ 的收敛半径 $R > 1$，因此 $\sum\limits_{n=0}\limits^{\infty}f_{n}$ 收敛到 $f(1)$。

另一方面，设 $1 < r < R$，由收敛半径界定理，有：

由幂级数的性质，两个幂级数相乘所得的幂级数，其系数等于原始的两个幂级数系数的卷积，于是有：

记其中第 $j$ 项为 $t_{j}$：

于是 $[z^{n}]\frac{f(z)}{(1 - z)^{\alpha}} = \binom{n+\alpha - 1}{n}\sum\limits_{j=0}\limits^{n}t_{j}$。

进一步考察 $t_{j}$，当 $n\rightarrow\infty$ 时，有 $\lim\limits_{n\rightarrow\infty}t_{j} = f_{j}$，因此有：

定理中的后一个渐近等价性由 $\Gamma$ 函数与广义二项式系数的关系可得。

$\Box$

推论 (收敛半径逼近)

设 $f(z)$ 的收敛半径 $R > \rho$，$f(\rho) \neq 0$，则对任意的实数 $\alpha \notin \{0, -1, -2, \cdots\}$，成立以下渐近等价性：

证明

大致思路是令 $g(z) = f(\frac{z}{\rho})$，于是有 $[z^{n}]g(z) = \rho^{-n}[z^{n}]g(\rho z) = \rho^{-n}[z^{n}]f(z)$，然后结合收敛半径逼近定理进一步推导即可。

$\Box$

分析结果：卡特兰数的渐近估阶

回到最初的问题，考虑 $G(z) = zT(z) = \frac{1-\sqrt{1-4z}}{2}$。

由于 $\sqrt{z}$ 在 $z = 0$ 处的多值性，因此在 $z = 0$ 处不解析。因此对于 $G(z)$ 来说，$z = \frac{1}{4}$ 就是 $G(z)$ 在复平面上唯一一个奇点。

而对 $T(z) = \frac{G(z)}{z}$ 来说，它在 $z = 0$ 处可以解析延拓到 $T(0) = 1$，因此 $\frac{1}{4}$ 仍然是 $T(z)$ 的唯一奇点，因此幂级数 $T(z) = \sum\limits_{n=0}\limits^{\infty}T_{n}z^{n}$ 的收敛半径为 $R = \frac{1}{4}$。

一方面，由收敛半径界定理，$T_{n} \bowtie (\frac{1}{R})^{n} = 4^{n}$，因此 $T_{n} = 4^{n}\theta(n)$，其中 $\theta(n)$ 为次指数因子。这个结论也可以写为 $T_{n} = O((4 + \epsilon)^{n})$，这是一个比较松的上界。

另一方面，忽略 $G(z)$ 的常数项，取 $f(z) = -\frac{1}{2}$，$\alpha = -\frac{1}{2}$，$\rho = \frac{1}{4}$，于是由收敛半径逼近定理的推论有：

将 $\Gamma(-\frac{1}{2}) = -2\sqrt{\pi}$ 代入，整理后得 $[z^{n}]G(z) \sim \frac{4^{n-1}}{n\sqrt{\pi n}}$，于是：

总结

本文我们以二叉树种类数 $T_{N}$ 的渐近估阶为例。初步体验了复变函数在解决数列的渐近估阶问题中的威力。

首先我们基于数列的上极限，定义了数列的指数增长。然后介绍了对复变函数解析性的幂级数定义，进一步基于解析延拓给出奇点的概念。

有了奇点的概念，就可以引出幂级数的收敛圆盘的半径，基于这个半径，我们可以推导出幂级数的系数的渐近行为。

本文给出了两个由收敛半径给出系数的渐近行为的相关定理，一个与上界有关、一个与渐近等价性有关。这两个定理是本文的核心内容，我们给出了简要的证明。

应用上述两个定理，我们就可以轻易给出 $T_{N}$ 的渐近估计：$T_{N} \sim \frac{4^{N}}{N\sqrt{\pi N}}$，这与使用欧拉-麦克劳林公式的结果一样。

Share