一、递推方程示例 2 汉诺塔

Hanoi 问题 :

• 递推方程为 : $T(n)=2T(n-1)+1$
• 初值 : $T(1)=1$
• 解 : $T(n)=2^n-1$

该递推方程表示 , 将 $n$ 个盘子的移动次数 $T(n)$ , 与 $n-1$ 个盘子的移动次数 $T(n-1)$ 之间的关系 ;

解法参考 : 【组合数学】递推方程 ( 特特解示例 ) 一、特解示例 1 ( 汉诺塔 )

二、递推方程示例 3 插入排序

$W(n)$ 表示在最坏的情况下插入排序的次数 ;

前面的 $n-1$ 个数已经排好了 , 其在最坏的情况下插入排序次数是 $W(n-1)$ 次 ,

第 $n$ 个数字要插入到这 $n-1$ 个数字中 , 最坏的情况是 要插入的数字要与所有的已排序好的 $n-1$ 个数字进行比较 , 对比次数是 $n-1$ 次 ,

因此递推方程可以写成 : $W(n)=W(n-1)+n-1$

递推方程初值 : $W(1)=0$ , 如果只有一个数字 , 不用进行排序 , 对比次数是 $0$ ;

最终解为 : $W(n)=O(n^2)$ , 精确值为 $W(n)=\frac{n(n-1)}{2}$

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109212687