问题求解（二） Open Topic II 笔记

Posted on 2023-04-14 In Course Note , Problem Solving

选题为 6-1, 讲解在 Stanford Lecture - Don Knuth: The Analysis of Algorithms 中的算法分析.

演示文稿: 详见 Slide.

问题引入

算法分析初探：

对于以下寻找最大值的算法(假设元素互不相同)

# Given a[1..n]
m = a[n]
k = n-1
while k != 0 : 
    if a[k] > m :
        m = a[k] # (*)
    k = k - 1

尝试分析 (*) 句的执行次数.

数据特征

要分析一个语句的执行次数, 我们可以从它的最小值、最大值、平均值、方差入手.

(*) 的执行次数的最小值是 \(0\) (当 \(a[n]\) 即为最大值), 最大值是 \(n-1\) (当序列降序), 平均值和方差呢?

平均值可以用 TC 中提及的指示性随机变量得到, \(X_i\) 表示在 \(k=i\) 时发生替换的次数, 等价于 \(a[i]\) 是 \(a[i..n]\) 中的最大值, 那么有 \(E[X_i]=1/(n-i+1)\), 进一步有

\[ E(X)=\sum_{i=1}^{n-i}\dfrac{1}{n-i+1}=H_n-1. \]

其中 \(H_n\) 是调和数.

那么方差呢? 这时我们就需要一些其它的方法了. 我们尝试直接考虑 (*) 的概率分布, 即求 \(p_{n, k}\), 意为在 \(n\) 个数时执行次数为 \(k(0\le k\le n-1)\) 的概率.

斯特林数

斯特林数介绍

首先来介绍第一类斯特林数(斯特林轮换数), 在 TC 作业里第二类斯特林数(斯特林子集数). 第一类斯特林数和它类似.

斯特林轮换数: 将 \(n\) 个两两不同的元素划分为 \(k\) 个互不区分的非空轮换(圆排列)的方案数, 记为 \(\begin{bmatrix}n \\ k\end{bmatrix}\).

有递推公式为

\[ \begin{bmatrix} n \\ k \end{bmatrix} =(n-1) \begin{bmatrix} n-1 \\ k \end{bmatrix} + \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}, (n\ge 1, k\ge 1). \]

初始条件为 \(\begin{bmatrix}n \\ 0\end{bmatrix} = [n=0]\).

证明: 考虑第 \(n\) 个元素, 有两种可能:

被加入原先某一个元素的后面, 有 \(n-1\) 种可能. 没有形成新轮换, 所以乘上 \(\begin{bmatrix}n-1 \\ k\end{bmatrix}\),
独占一个轮换, 那么先前 \(n-1\) 个元素需要填另外 \(k-1\) 个轮换, 所以是 \(\begin{bmatrix}n-1 \\ k-1\end{bmatrix}\).

斯特林轮换数和原问题的关系

\[ p_{n, k}=\dfrac{1}{n!}\begin{bmatrix}n \\ k+1\end{bmatrix}, (0\le k\le n-1). \]

理解方法:

要使得 (*) 执行 \(k\) 次, 那么原序列必然能分成非空的 \(k+1\) 部分, 每一部分的最右边的元素是该部分的最大元素, 而且各部分之间, 最大元素(每一部分的最右边元素)递减. 于是我们发现: 每一部分内元素可以随便排列, 但是最后要"移动"使得最大元在最右边, 等价于一个圆排列; 由于各部分之间要求最大元素递减, 相当于使得这 \(k+1\) 个圆排列(轮换)不加以区分, 符合第一类斯特林数的定义. 最后除以 \(n!\) 就是概率.

斯特林轮换数的生成函数

考虑对于每一个 \(n\) 值, 斯特林轮换数的生成函数为 \(S_n(z)\).

于是 \(S_0(z)=1, S_1(z)=z\), 且当 \(n\ge 2\),

\[ \begin{aligned} S_n(z) &= \sum_{k\ge 0} \begin{bmatrix}n \\ k\end{bmatrix}z^k \\ &=\sum_{k\ge 1} \left((n-1)\begin{bmatrix}n-1 \\ k\end{bmatrix}+\begin{bmatrix}n-1 \\ k-1\end{bmatrix}\right)z^k \\ &=(n-1)\sum_{k\ge 1}\begin{bmatrix}n-1 \\ k\end{bmatrix}z^k+z\sum_{t\ge 0}\begin{bmatrix}n-1 \\ t\end{bmatrix}z^t \\ &=(n-1+z)S_{n-1}(z). \end{aligned} \]

归纳可得 \(S_n(z)=z(z+1)\cdots(z+n-1)=z^{\overline{n}}\).

概率生成函数

引入

回到原问题, 我们看一看以下这个生成函数, 固定 \(n\) 有

\[ P_n(z)=\sum_{k\ge 0}p_{n, k}z^k \]

它称为概率生成函数, 我们研究它的性质来研究均值和方差.

概率生成函数的基本特征

对于随机变量 \(X\) 的概率生成函数

\[ G(z)=\sum_{k\ge 0}p_kz^k. \]

有 \(\displaystyle G(1)=\sum_{k\ge 0}p_k=1\). (概率生成函数的必要条件)

求导有

\[ G'(z)=\sum_{k\ge 1}kp_kz^{k-1}. \]

有 \(\displaystyle G'(1)=\sum_{k\ge 1}kp_k=E(X)\). (均值)

再求导有

\[ G''(z)=\sum_{k\ge 2}k(k-1)p_kz^{k-2}. \]

有 \(\displaystyle G''(1)=\sum_{k\ge 2}(k^2-k)p_k\).

那么 \(\displaystyle G''(1)+G'(1)=\sum_{k\ge 1}k^2p_k=E(X^2)\).

于是 \(\displaystyle G''(1)+G'(1)-[G'(1)]^2=E(X^2)-E^2(X)=D(X)\). (方差)

所以我们成功用 \(G'(1), G''(1)\) 得到了 \(X\) 的期望和方差, 总结是:

\[ \begin{aligned} E(X) &= G'(1), \\ D(X) &= G''(1)+G'(1)-[G'(1)]^2. \end{aligned} \]

概率生成函数卷积的均值和方差

设 \(X\) 的生成函数为 \(G(z)\), \(Y\) 的生成函数为 \(H(z)\), 令它们的卷积 \(F=G*H\)

若 \(X\) 和 \(Y\) 独立, 那么 \(F(z)=(G*H)(z)\) 是 \(X+Y\) 的生成函数.
若 \(X\) 和 \(Y\) 不一定独立, 那么 \(F(z)\) 不一定表示 \(X+Y\) 的生成函数, 但这不影响 \(F\) 的均值和方差的计算, 它的均值和方差的公式不依赖于 \(X\) 和 \(Y\) 的独立性.

首先验证 \(F\) 是概率生成函数. 显然 \(F\) 各项非负, 且 \(F(1)=G(1)H(1)=1\), 故 \(F\) 是概率生成函数. 假设是 \(Z\) 的生成函数.

然后试着求求 \(Z\) 的均值. 先求导

\[ F'(z)=G'(z)H(z)+G(z)H'(z). \]

故 \(E(Z)=F'(1)=G'(1)H(1)+G(1)H'(1)=G'(1)+H'(1)=E(X)+E(Y)\). \(Z\) 的均值是 \(X\) 和 \(Y\) 的均值的和.

然后试着求求 \(Z\) 的方差. 再求导

\[ F''(z)=G''(z)H(z)+2G'(z)H'(z)+G(z)H''(z) \]

故

\[ \begin{aligned} D(Z) &= F''(1)+F'(1)-[F'(1)]^2 \\ &= G''(1)+2G'(1)H'(1)+H''(1)+G'(1)+H'(1)-[G'(1)+H'(1)]^2 \\ &= \lbrace G''(1)+G'(1)-[G'(1)]^2\rbrace + \lbrace H''(1)+H'(1)-[H'(1)]^2\rbrace \\ &=D(X)+D(Y). \end{aligned} \]

\(Z\) 的方差是 \(X\) 和 \(Y\) 的方差的和.

解决问题

最后我们回到原题, 我们要求随机变量 \(X_n\) 对应的生成函数

\[ P_n(z)=\sum_{k\ge 0}p_{n, k}z^k \]

的均值和方差.

首先做点变形, 利用斯特林轮换数的生成函数有

\[ \begin{aligned} P_n(z) &=\sum_{k\ge 0}p_{n, k}z^k \\ &=\sum_{k\ge 0} \left(\dfrac{1}{n!}\begin{bmatrix}n \\ k+1\end{bmatrix}\right)z^k \\ &=\dfrac{1}{n!\cdot z}\sum_{i\ge 0}\begin{bmatrix}n \\ i\end{bmatrix}z^i \\ &=\dfrac{1}{n!\cdot z} [z(z+1)\cdots(z+n-1)] \\ &=\dfrac{1}{n!}(z+1)(z+2)\cdots (z+n-1) \end{aligned} \]

为了求 \(P_n(z)\) 的均值和方差, 我们把它分成 \(n-1\) 个概率生成函数的乘积:

\[ \begin{gather*} P_n=A_2*A_3*\cdots*A_{n} \\ A_i(z)=\dfrac{z+i-1}{i}. \end{gather*} \] 容易验证 \(A_i(1)=1\), 故此处 \(A_i\) 均是概率生成函数. 然后来求求 \(A_i(z)\) 的均值和方差. 易得 \(A_i'(z)=1/i, A_i''(z)=0\), 故

\[ \begin{aligned} E(A_i)&=A_i'(z)=\dfrac{1}{i} \\ D(A_i)&=A_i''(z)+A_i'(z)-[A_i'(z)]^2=\dfrac{1}{i}-\dfrac{1}{i^2} \end{aligned} \]

那么,

\[ \begin{gather*} E(X_n)=\sum_{i=2}^n\dfrac{1}{i}=H_n-1 \\ D(X_n)=\sum_{i=2}^n(\dfrac{1}{i}-\dfrac{1}{i^2})=H_n-H_n^{(2)} \end{gather*} \]

其中 \(H_n\) 为调和数 \(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}\), \(H_n^{(2)}\) 为二阶调和数 \(1+\dfrac{1}{2^2}+\dfrac{1}{3^2}+\cdots+\dfrac{1}{n^2}\).

应用与总结

应用

于是我们得到了 (*) 的执行次数的数据如下

最小值	最大值	均值	方差
\(0\)	\(n-1\)	\(H_n-1\)	\(H_n-H_n^{(2)}\)

得到这些数据有什么用? 由于 \(H_n=\Theta(\lg n)\), 我们得知了在平均情况下只有 \(\lg n\) 次最大值替换, 这样我们可能可以在该支路运行高复杂度的算法(如插入数据库等)但不改变平均情况复杂度. 对原序列进行随机打乱可以使得无针对性输入.

总结

Knuth 介绍了很多算法分析里的常用方法, 包括定量分析, 计数技巧, 生成函数等等. 这些工具可帮助我们完成算法分析.