《CM》2.2 Sums And Recurrences

2.2 Sums And Recurrences 和与递归

注意到和与递归有着很密切的联系,和\sum_{k=0}^n a_k等价于递归式\begin{array}{l}S_0=a_0; \\ S_n=S_{n-1}+a_n, \text{for }n > 0. \end{array}这样我们就可以用求递归式的方法来求和。如可以用repertoire method求解递归式:\begin{array}{l}R_0=\alpha; \\ R_n=R_{n-1}+\beta+\gamma n, \text{for }n > 0.\end{array}这样我们就求出了这种形式的和

\sum_{k=0}^n (a+bk)

同样,如果和是比较好求的,那么求解递归式也可以通过求解对应的和来求解。如以下形式的递归式:

a_nT_n=b_nT_{n-1}+c_n

可以用一种叫做summation factor method的方法来求解这种递归式。

summation factor method的目标是,把递归式化成可以写成和的形式,像这样:

S_n=S_{n-1}+f(n)

这样的递归式就可以等价于和\sum_{k=0}^n f(n),从而通过求解这个和来求解递归式。为了化成如上形式,summation factor method的做法是,在递归式左右两边同时乘以一个summation factor s_n,并且使得

s_nb_n=s_{n-1}a_{n-1}

这样,递归式就可以变成s_na_nT_n=s_{n-1}a_{n-1}T_{n-1}+s_nc_n,令S_n=s_na_nT_n,就把递归式化成了目标形式:

S_n=S_{n-1}+s_nc_n

这样,可求得

S_n=s_0a_0T_0+\sum_{k=1}^n s_nc_n=s_1b_1T_0+\sum_{k=1}^n s_nc_n

于是,原递归式的解即为

T_n=\frac{s_1b_1T_0+\sum_{k=1}^n s_nc_n}{a_nb_n}

那么,怎么找这个summation factor s_n呢?由s_nb_n=s_{n-1}a_{n-1}可知

s_n\begin{array}[t]{l}=\frac{a_{n-1}s_{n-1}}{b_n} \\ =\frac{a_{n-1}a_{n-2}s_{n-2}}{b_nb_{n-1}} \\ \vdots \\ =\frac{a_{n-1}a_{n-2}\dots a_1s_1}{b_nb_{n-1}\dots b_2} \end{array}

其中,s_1是常数。另外要注意的是,summation factor method只能在所有a和b都不为0的时候运用。(b显然不能为0,有某一a_k为0时,s_n为0,递归式就化成0=0的形式了)

最后来看一个具体的例子,求解著名的快排算法的平均比较次数问题,该问题满足如下递归式:

\begin{array}{l}C_0=0; \\ C_n=n+1+\frac{2}{n}\sum_{k=0}^{n-1} C_k, \text{for }n > 0.\end{array}

先对该递归式适当变形,转化成可用summation factor method求解的形式。两边同时乘以n得

nC_n=n^2+n+2\sum_{k=0}^{n-1}C_k, \text{for }n > 0;

用n-1替换n得

(n-1)C_{n-1}=(n-1)^2+(n-1)+2\sum_{k=0}^{n-2}C_k, \text{for }n-1 > 0.

两式相减得

nC_n-(n-1)C_{n-1}=2n+2C_{n-1}, \text{for }n > 1.

这样,递归式就化简成:

\begin{array}{l} C_0=0; \\ nC_n=(n+1)C_{n-1}+2n, \text{for }n > 0.\end{array}

s_n=\frac{2}{(n+1)n}可求得

C_n=2(n+1)\sum_{k=1}^n \frac{1}{k+1}

再进行下一步之前,先介绍一个很重要的数,叫做调和数(harmonic number),记作H_n

H_n=\sum_{k=1}^n \frac{1}{k}.

回到C_n,该解中的和

\sum_{\substack{1 \leq k \leq n}}\frac{1}{k+1} \begin{array}[t]{l} =\sum_{\substack{1 \leq k-1 \leq n}}\frac{1}{k} \\ =\sum_{\substack{2 \leq k \leq n+1}}\frac{1}{k} \\ =H_n-\frac{n}{n+1}.\end{array}

于是,我们可以求得解为

C_n=2(n+1)H_n-2n.

(由于H_n是个很重要的式子,我们把它看成是一个和阶乘一样的这类式子,所以我们也把该解看成是closed form)



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*