【组合数学】递推方程 ( 递推方程示例 2 汉诺塔 | 递推方程示例 3 插入排序 )

文章目录

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

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

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

Hanoi 问题 :

递推方程为 : T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1 T(n)=2T(n−1)+1

初值 : T ( 1 ) = 1 T(1) = 1 T(1)=1

解 : T ( n ) = 2 n − 1 T(n) = 2^n - 1 T(n)=2n−1

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

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

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

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

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

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

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

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。