第27页 SUMS AND RECURRENCES
36° (仰望星空 脚踏实地)
读过 具体数学(英文版第2版)
- 章节名:SUMS AND RECURRENCES
- 页码:第27页
2.2节介绍了($summation factor$)这个trick,主要是用来求类似($a_nT_n = b_nT_{n-1} + c_n$)这种递推形式的非递归形式通项公式。 在公式左右同时乘以($summation factor$),($s_n$):
\begin{align} s_na_nT_n = s_nb_nT_{n-1} + s_nc_n \end{align}为了能够将($s_na_nT_n$)和($s_nb_nT_{n-1}$)看作一个数组的前后两项,进而化简,需要选择($s_n$), st
\begin{align} s_nb_n = s_{n-1}a_{n-1} \end{align}这样令($S_n = s_na_nT_n$),原式就可以转化为:
\begin{align} S_n = S_{n-1} + s_nc_n \end{align}然后解得:
\begin{align} & S_n = s_0a_0T_0 + \sum _{ k=1 }^{ n }{s_kc_k} = s_1b_1T_0 + \sum _{ k=1 }^{ n }{ s_kc_k} \\ & T_n = \frac{1}{s_na_n}( s_1b_1T_0 + \sum _{ k=1 }^{ n }{s_ kc_k}) \end{align}问题只剩下如何求($s_n$),根据上面第二个公式:
\begin{align} & s_nb_n = s_{n-1}a_{n-1} &(1)\\ & s_n = \frac {s_{n-1}a_{n-1}}{b_n} &(2)\\ & s_n = \frac {a_{n-1}a_{n-2}...a_{1}}{b_{n}b_{n-1}...b_{2}} &(3) \end{align}上面是原作者给出的推理过程,但是我觉得式(3)存疑,因为并下标在某些场景下还可以继续转化,更合理的式子应该是:
\begin{align} s_n = \frac {a_{n-1}a_{n-2}...a_{1}}{b_{n}b_{n-1}...b_{2}} s_1 = \frac {a_{n-1}a_{n-2}...a_{0}}{b_{n}b_{n-1}...b_{1}} s_0 \end{align}在应用的时候,根据($a_n$)和($b_n$)的特点来决定转化到哪一步,但无论是到($s_1$)还是到($s_0$),($s_n$)的最后一项都为1. 比如对于汉诺塔的问题: ($T_n = 2T_{n-1} + 1$),这时候($a_n = 1, b_n = 2$). 由于($a_0 > 0$),所以可以转化到($s_0$),即:
\begin{align} s_n = \frac {a_{n-1}a_{n-2}...a_{0}}{b_{n}b_{n-1}...b_{1}} s_0 = 2 ^ {-n} \end{align}而对于快排的平均复杂度计算的公式(($C_n = n+1 + \frac {2}{n} \sum_{k=0}^{n-1}{C_k}$)化简后): ($nC_n = (n+1)Cn-1 + 2n$),这时候($a_n = n, b_n = n + 1$). 由于($a_0 = 0$),所以只能转化到($s_1$),即:
\begin{align} s_n = \frac {a_{n-1}a_{n-2}...a_{1}}{b_{n}b_{n-1}...b_{2}} s_1 = \frac {(n-1)(n-2)...1}{(n+1)n...3} = \frac {2}{(n+1)n} \end{align}
36°对本书的所有笔记 · · · · · ·
-
第16页 Recurrent Problems
关于repertoire method讲的有些小混乱,可以参见国外网友的总结,我觉得非常详实了: http://p...
-
第19页 Exercise
14. 这道题想了半天,最后的递推关系还是想错了。 我的理解是,新增的三维空间是新增的面和之...
-
第27页 SUMS AND RECURRENCES
-
第30页 Manipulation of sums
2.3 The chapter firstly introduces three laws of manipulation of sums : \begin{align} \...
-
第40页 multiple sums
作者给了一个二重求和的范式,利用之前的Commutative Law,进行适当的转换,可以节省结算步骤...
说明 · · · · · ·
表示其中内容是对原文的摘抄