IDEA激活码
文章目录
- 一、递推方程示例 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)
