算法的复杂性

b

<H3>递归方程组解的渐进阶的求法——母函数法</H3><>关于<I>T</I>(<I>n</I>)的递归方程的解的母函数通常设为：</P><><img src="http://algorithm.myrice.com/algorithm/complexity/images/img78.gif"> (6.24)</P><>当(6.24)右端由于<I>T</I>(<I>n</I>)增长太快而仅在<I>x</I>=0处收敛时可另设</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img79.gif"> (6.25)</P><P>如果我们可以利用递归方程建立<I>A</I>(<I>x</I>)的一个定解方程并将其解出，那么，把<I>A</I>(<I>x</I>)展开成幂级数，则<I>x</I><SUP>n</SUP>或<I>x</I><SUP>n</SUP>/<I>n</I>!项的系数便是所求的递归方程的解。其渐近阶可接着进行估计。</P><P>下面举两个例子加以说明。</P><P><B>例1 </B>考虑线性变系数二阶齐次递归方程</P><P>(<I>n</I>-1)<I>T</I>(<I>n</I>)=(<I>n</I>-2)<I>T</I>(<I>n</I>-1)+2<I>T</I>(<I>n</I>-2) ，<I>n</I>≥2 (6.26)</P><P>和初始条件<I>T</I>(0)=0，<I>T</I>(1)=1。根据初始条件及(6.26)，可计算<I>T</I>(2)=0，<I>T</I>(3)=<I>T</I>(1)=1。</P><P>设{<I>T</I>(<I>n</I>)}的母函数为：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img80.gif"></P><P>由于<I>T</I> (0)=<I>T</I> (2)=0，<I>T</I>(1)= 1，有 ：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img81.gif"></P><P>令 <I>B</I>(<I>x</I>)= <I>A </I>(<I>x</I>)/<I>x</I>，即：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img83.gif"></P><P>那么：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img85.gif"></P><P>利用(6.26)并代入T (3)= 1，得</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img86.gif"></P><P>即</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img87.gif"></P><P>两边同时沿[0,<I>x</I>]积分，并注意到<I>B</I>(0)=1，有：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img88.gif"></P>

b

<>把<I>B</I>(<I>x</I>)展开成幂级数，得</P>
<><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img89.gif"></P>
<>从而</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img90.gif"></P>
<P>最后得</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img91.gif"></P>
<P><B>例2 </B>考虑线性变系数一阶非齐次递归方程</P>
<P><I>D</I>(<I>n</I>)=<I>nD</I>(<I>n</I>-1)+(-1)<SUP>n</SUP>  <I>n</I>≥1 (6.27)</P>
<P>及初始条件<I>D</I> (0)= 1</P>
<P>很明显<I>D</I>(<I>n</I>)随<I>n</I>的增大而急剧增长。如果仍采用(6.24)形式的函数，则(6.24)的右端可能仅在<I>x</I>=0处收敛，所以这里的母函数设为：</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img92.gif"></P>
<P>用<I>x</I><SUP>n</SUP>/<I>n</I>!乘以(6.27)的两端，然后从1到∞求和得：</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img93.gif"></P>
<P>化简并用母函数表达，有：</P>
<P><I>A</I>(<I>x</I>) -1= <I>xA</I>(<I>x</I>)+<I>e</I><SUP>-x</SUP>-1</P>
<P>或</P>
<P>(1-<I>x</I>)<I>A</I>(<I>x</I>)=<I>e</I><SUP>-x</SUP></P>
<P>从而</P>
<P><I>A</I>(<I>x</I>)=<I>e</I><SUP>-x</SUP>/(1-<I>x</I>)</P>
<P>展成幂级数，则：</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img94.gif"></P>
<P>故</P>
<P><IMG src="http://algorithm.myrice.com/algorithm/complexity/images/img95.gif"></P><!-- #EndEditable -->