提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

示例 组合 数学 方程 插入排序 汉诺塔 递推
2023-06-13 09:17:48 时间

文章目录

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

Hanoi 问题 :

  • 递推方程为 :
T(n) =2 T(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) = \cfrac{n(n-1)}{2}

相关文章