< ><B>第三步</B>，写出(6.19)即(6.18)的通解</P><><img src="http://algorithm.myrice.com/algorithm/complexity/images/img64.gif"> (6.22)</P><>其中{<I>T</I><SUB>i</SUB>(<I>n</I>)，i=0,1,2,…,<I>n</I>}是(6.20)的基础解系，<I>g</I>(<I>n</I>)是(6.19)的一个特解。然后由(6.18)的初始条件</P><P><I>T</I>(<I>i</I>)=<I>T</I><SUB>i</SUB> ，i=1,2,…,<I>k</I>-1</P><P>来确定(6.22)中的待定的组合常数{<I>a</I><SUB>i</SUB>}，即依靠线性方程组</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img65.gif"></P><P>或</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img66.gif"></P><P>解出{<I>a</I><SUB>i</SUB>}，并代回(6.22)。其中<I>β</I><SUB>j</SUB>=<I>T</I><SUB>j</SUB>-<I>g</I>(<I>j</I>)，<I>j</I>=0,1,2,…,<I>k</I>-1。</P><P><B>第四步</B>，估计(6.22)的渐近阶，即为所要求。</P><P>下面用两个例子加以说明。</P><P><B>例l</B> 考虑递归方程</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img67.gif"></P><P>它的相应特征方程为：</P><P><I>C</I>(<I>t</I>)=<I>t</I><SUP>2</SUP>-<I>t</I>-1=0</P><P>解之得两个单根<img src="http://algorithm.myrice.com/algorithm/complexity/images/img68.gif">和<img src="http://algorithm.myrice.com/algorithm/complexity/images/img69.gif">。相应的(6.20)的基础解系为{<I>r</I><SUB>0</SUB><SUP>n</SUP>，<I>r</I><SUB>1</SUB><SUP>n</SUP>}。相应的(6.19)的一个特解为<I>F</I>*(<I>n</I>)=-8，因而相应的(6.19)的通解为：</P><P><I>F</I>(<I>n</I>)=<I>a</I><SUB>0</SUB><I>r</I><SUB>0</SUB><SUP>n </SUP>+<I>a</I><SUB>1</SUB><I>r</I><SUB>1</SUB><SUP>n</SUP>- 8</P><P>令其满足初始条件，得二阶线性方程组：</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img70.gif"></P><P>或</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img71.gif"></P><P>或</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img72.gif"></P><P>解之得<img src="http://algorithm.myrice.com/algorithm/complexity/images/img73.gif">，<img src="http://algorithm.myrice.com/algorithm/complexity/images/img74.gif">，从而</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img82.gif"></P><P>于是</P><P><img src="http://algorithm.myrice.com/algorithm/complexity/images/img84.gif">。</P><P><B>例2</B> 考虑递归方程 </P><P><I>T</I>(<I>n</I>)=4<I>T</I>(<I>n</I>-1)-4<I>T</I>(<I>n</I>-2)+2<SUP>n</SUP><I>n</I> (6.23)</P><P>和初始条件<I>T</I>(0)=0，<I>T</I>(1)=4/3。</P><P>它对应的特征方程(6.21)为</P><P><I>C</I>(<I>t</I>)=<I>t</I><SUP>2</SUP>-4<I>t</I>+4=0</P><P>有一个两重根<I>r</I> =2。故相应的(6.20)的基础解系为{2<SUP>n</SUP>，2<SUP>n</SUP>n}。由于<I>f</I>(<I>n</I>)=2<SUP>n</SUP>n，利用表6-1，相应的(6.19)的一个特解为</P><P><I>T</I>*(<I>n</I>)=<I>n</I><SUP>2</SUP>(<I>p</I><SUB>0</SUB>+<I>p</I><SUB>1</SUB><I>n</I>)2<SUP>n</SUP>，</P><P>代人(6.23)，定出<I>p</I><SUB>0</SUB>=1/2，<I>p</I><SUB>1</SUB>=1/6。因此相应的(6.19)的通解为：</P><P><I>T</I>(<I>n</I>)=<I>a</I><SUB>0</SUB>2<SUP>n</SUP>+<I>a</I><SUB>1</SUB><I>n</I>2<SUP>n</SUP>+<I>n</I><SUP>2</SUP>(1/2+<I>n</I>/6)2<SUP>n</SUP>，</P><P>令其满足初始条件得<I>a</I><SUB>0</SUB>=<I>a</I><SUB>1</SUB>=0，从而</P><P><I>T</I>(<I>n</I>)=<I>n</I><SUP>2</SUP>(1/2+<I>n</I>/6)2<SUP>n</SUP></P><P>于是<I>T</I>(<I>n</I>)=<I>θ</I>(<I>n</I><SUP>3</SUP>2<SUP>n</SUP>)。</P><!-- #EndEditable -->- <SCRIPT src="../../lib/footer.js">
- <script>
|
楼主