文档介绍：算法设计与分析
——分治法
分治法
主要内容:
介绍分治法的基本思想和分治算法的设计与分析。
分治法
几个典型例子:
二分查找(二分搜索)
快速排序
二叉树遍历
观察:上述问题的算法有什么共同特点?
分治法
将原问题分解成若干个相互独立的与原问题性质相同的子问题,用同样的方法解这些子问题并将这些子问题的解组合起来得到原问题的解。
说明:子问题还用相同的分治方法解,分治过程一直进行下去,直至子问题的规模充分小,可直接解为止。
分治法
分治法图示:
原问题P
子问题P1
子问题P2
子问题Pk
P1的解
P2的解
Pk的解
原问题P的解
组合
直接解或分治法解
分解
……
……
分治法
分治算法的一般步骤:
分解→直接或递归求解子问题→组合
由于分治法本身的递归特性,一般用递归实现分治算法。
递归分治算法的一般形式
过程 divideandconquer ( P )
例子:求n (n=2k, k>=1)个整数的最大值和最小值。(例子)
分治法
递归方程
分治算法的时间复杂性C(n)往往满足如下的递归方程:
其中,n: 问题的规模。
n0: 可直接解的问题规模的阈值。
a: 分解出的需要求解的子问题的个数。
n/c: 分解出的子问题的规模。
g(n): 分解规模为n的问题以及组合相应子问题的解
所需的时间。
d: 直接解规模为n0的问题所需的时间。
分治法
递归方程的求解:(第2章)
尽量利用公式
分治法
1. 归并排序(合并排序) ( P105)
基本思想:
//对序列a1, a2,…, an归并排序
if n>1 then
将a1, a2,…, an分解成a1, a2,…,an/2 和an/2+1,an/2+2…, an
两个子序列;//分解
分别对两个子序列归并排序; //递归
将两个有序子序列合并成一个有序序列; //组合
end if
分治法
1. 归并排序(合并排序) ( P105)
归并排序过程图示(P106 ) 归并排序过程
递归的归并排序算法
MERGESORT
迭代的算法:
( BOTTOMUPSORT P10)