假设n=2k，比较次数至多为W(n) W(n)=2W(n/2)+n1
归并两个n/2大小数组的比较次数为n1
7
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该 算法采用经典的分治（divide-and-conquer）策略（分治法将问题分 (divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分 的阶段得到的各答案"修补"在一起，即分而治之)。
k 1
ak aid(n / bi ) i0
a k alogb n nlogb a
Case1 d(n)=c
T (n)
a k
c
ak 1 a1
O(ak
)
O(nlogb a
)
ak kc O(log n)
a1 a1
26
Case2 d(n)=cn
T(n)
ak
k 1
ai
i0
cn bi
ak
cnk1 ( a )i i0 b
18
平均时间复杂度
T(n)为对数组的各种输入平均做的比较次数 将输入按照A[p]在排好序后的位置分别为1, 2, …, n进行分类. 假设每类输入出现的概率相等
A[p]处位置1，划分后子问题规模分别为0和n-1
… A[p]处位置n，划分后子问题规模分别为n-1和0
n 种输入的平均复杂度为
T(n) 1 [(T(0) T(n 1)) (T(1) T(n 2)) ... n
8.3 递推方程的求解与应用
Hanoi 塔问题 递推方程的定义 二分归并排序算法的分析 快速排序算法的分析 递归树 分治算法分析的一般公式
1
Hanoi塔问题
Hanoi塔问题： 从A柱将这些圆盘移到C柱上去. 如果把一个圆盘从 一个柱子移到另一个柱子称作 1 次移动，在移动和放置 时允许使用B柱，但不允许大圆盘放到小圆盘的上面. 问 把所有的圆盘的从A移到C总计需要多少次移动？
14
15
划分过程
Partition(A,p,r) 1. x A[p] 2. i p 3. j r+1 4. while true do 5. repeat j j 1 6. until A[ j ]<x //*右边第1个比A[p]小的A[j] 7. repeat i i +1 8. until A[ i ]>x //*左边第1个比A[p]大的A[i] 9. if i < j 10. then A[ i ] A[ j ] //*交换A[j]与A[i] 11. else return j
8
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归 去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆 分子序列的过程，递归深度为log2n。 再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序 列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序 的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
1578
2346
10
求解递推方程
W (n) 2W ( 2k1 ) 2k 1 2[2W (2k2 ) 2k1 1] 2k 1 22W (2k2 ) 2k 2 2k 1 22[2W (2k3 ) 2k2 1] 2k 2 2k 1 23W (2k3 ) 2k 22 2k 2 2k 1 ... 2kW (1) k 2k (2k1 2k2 ... 2 1) k2k 2k 1 n log n n 1
11
归纳法验证解
n=1代入上述公式得 W(1)=1 log11+1=0，
符合初始条件.
假设对于任何小于n的正整数t，W(t)都是正确的， 将结果代入原递推方程的右边得
2W(n/2)+n1 =2(2k1 log2k12k1+1)+2k1 =2k(k1)2k+2+2k1=k2k2k+1 = nlognn+1=W(n)
O(n)
ab
d(n) cn : T (n) O(n log n) a b
O(nlogb a ) a b
25
迭代
T(n) a2T(n / b2 ) ad(n / b) d(n)
...
akT(n / bk ) ak1d(n / bk1) ak2(n / bk2 ) ... ad(n / b) d(n)
T (n)
2
n1
T (i) O(n),
n i1
T (1) 0
n2
求解方法：迭代法
6
二分归并排序算法
算法Mergesort(A,s,t) //*排序数组A[s..t] 1. m(t-s)/2 2. AMergesort(A,s,m) //*排序前半数组 3. BMergesort(A,s+1,t) //*排序后半数组 4. Merge(A,B) //*将排好序的A,B归并
nlogb a cn (a / b)k 1 a/b1
n cnk O(n log n)
O(n)
a k
cn
(a / b)k 1 a/b1
ak
c
ak a/
bk b1
O(nlogb a
)
ab ab ab
12
快速排序算法
算法 Quicksort(A,p,r) //*排序数组A[p..r]
输入：数组A[p..r]
输出：排好序的数组A
1. if p < r
2. then qPartition(A, p, r) //*以A[p]为准划分A
3.
A[p]A[q]
//*A[p]与A[q]交换
4.
Quicksort(A,p,q-1) //*对子数组递归排序
5.
Quicksort(A,q+1,r)
13
分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。 先从右往左找一个小于6的数，再从左往右找一个大于6的数，然 后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最 右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚 开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让 哨兵j指向序列的最右边（即j=10），指向数字8。
移动n个盘子的总次数为T(n) ，得到递推方程 T(n) = 2T(n1) +1. T(1)=1.
可以求得 T(n)=2n 1 1秒钟移动1次，64个盘子大约需要5000亿年
4
T (n) 2T (n 1) 1
2[2T (n 2) 1] 1 (T (n 1)被 含T (n 2)的 项 替 换)
printf("\t%c->%c\n",a,c);
move(n-1,b,a,c);
//n-1个移动过来之后b变开始盘，b通过a移动到c }
}
main()
{
int n;
printf("请输入要移动的块数：");
scanf("%d",&n);
move(n,'a','b','c');
}
3
算法设计与分析
算法 Hanoi (A,C,n) //*把n个盘子从A移到C 1. Hanoi (A,B,n-1) 2. move (A,C) //*把1个盘子从A移到C 3. Hanoi (B,C,n-1)
n-1 n-2 n-4 n-2k1
24
分治算法的常用递推公式
T (n) aT(n / b) d(n) n bk T (1) 1
其中a为子问题个数，n/b为子问题规模，d(n)为分解成 子问题或组合解的代价
方程的解为：
O(nlogb a ) a 1 d(n) c : T(n)
O(logn) a 1
32
c
n
1
1
1 n
...
1 3
21
用积分近似
n
1
1
1 n
...
1 3
n1 2
1 x
dx
ln
x
n1 2
ln(n 1) ln 2 O(logn)
T(n) O(nlogn)
.
22
递归树
W (n) 2W ( n/2 ) n 1 , n 2k W (1) 0
W(n)
n1 W(n/2) W(n/2)
2n 1
（等比级数求和）
5
递推方程的定义
定义10.5 设序列a0, a1, …, an, …, 简记为{an}, 一 个把an与某些个ai（i<n）联系起来的等式叫做关 于序列{an}的递推方程.
实例：
Fibonacci数列： fn=fn-1+fn-2, 初值 f0=1, f1=1 阶乘数列{an}，an=n!：an=nan-1, a1=1
nT(n) (n 1)T(n 1) 2T(n 1) O(n)
nT(n) (n 1)T(n 1) O(n)
20
迭代
T (n) T (n 1) c n1 n n1
c为 某 个 常 数
T(n 2) c c1)]
n1 n
16
#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
int i, j, t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
2
汉诺塔程序
#include<stdio.h>