《算法设计与分析》第05章.ppt

算法设计与分析 DeSignandAnalysisofAlgorithmsInC 十一五 国家级规划教材 陈慧南编著 电子工业出版社 第2部分算法设计策略 第5章分治法 5 1分治法的基本思想5 2求最大最小元5 3二分搜索5 4排序问题5 5选择问题5 6斯特拉森矩阵乘法 5 1一般方法 5 1 1分治法的基本思想 分治法顾名思义就是分而治之 一个问题能够用分治法求解的要素是 第一 问题能够按照某种方式分解成若干个规模较小 相互独立且与原问题类型相同的子问题 第二 子问题足够小时可以直接求解 第三 能够将子问题的解组合成原问题的解 由于分治法要求分解成同类子问题 并允许不断分解 使问题规模逐步减小 最终可用已知的方法求解足够小的问题 因此 分治法求解很自然导致一个递归算法 程序5 1 分治法SolutionTypeDandC ProblemTypeP ProblemTypeP1 P2 Pk if Small P returnS P else Divide P P1 P2 Pk ReturnCombine DandC P1 DandC P2 DandC Pk 程序5 2 一分为二的分治法SolutionTypeDandC intleft intright if Small left right returnS left right else intm Divide left right ReturnCombine DandC left m DandC m 1 right 5 1 2算法分析 采用分治法求解问题通常得到一个递归算法 如果较大的问题被分解成同样大小的几部分 那么分析相应算法的执行时间 往往可得到如下的递推关系式 T n aT n b cnk T 1 c 定理5 1设a b c和k为常数 T n aT n b cnk T 1 c 则 设r bk a 下面分三种情况计算 1 若r1 则所以 例如 1 T n 2T n 2 na 2 b 2 k 1 a bk所以T n nlog n 2 T n 4T n 4 n2a 4 b 4 k 2 abk所以T n n4 5 1 3数据结构 程序5 3 可排序表类templatestructE 可排序表中元素的类型operatorK const returnkey 重载类型转换运算符Kkey 关键字可以比较大小Ddata 其他数据 templateclassSortableList 可排序表类 public SortableList intmSize 构造函数 maxSize mSize l newT maxSize n 0 SortableList delete l 析构函数 private T l 定义动态一维数组intmaxSize 线性表的最大表长intn 线性表的实际长度 5 2求最大最小元 问题在一个元素集合中寻找最大元素和最小元素的问题 5 2 1分治法求解 程序5 4 求最大最小元templatevoidSortableList MaxMin T Tn 2 n 1 5 2 1分治法求解 程序5 4 求最大最小元templatevoidSortableList MaxMin T Wn 2 n 1 递减有序 Bn n 1 递增有序 程序5 5 分治法求最大最小元templatevoidSortableList MaxMin inti intj T else intm i j 2 MaxMin i m max min MaxMin m 1 j max1 min1 if maxmin1 min min1 5 2 2时间分析 定理5 2设有n个元素的表 假定n是2的幂 即n 2k k是正整数 程序5 5在最好 平均和最坏情况下的比较次数都为3n 2 2 n 2k T n 2T n 2 2T n 3n 2 2 5 3二分搜索 问题在有序表 已按关键字值非减排序 中搜索给定元素的问题 5 3 1分治法求解 intSortableList BSearch constT x intleft intright const后置条件 在范围为 left right 的表中搜索与x有相同关键字值的元素 如果存在该元素 则函数返回该元素在表中的位置 否则函数返回 1 表示搜索失败 二分搜索 1 二分搜索的基本思想二分搜索的基本思想是 首先将待查值x与有序表l 0 到l n 1 的中的下标为mid上的元素进行比较 若相等 则查找成功 否则 若xl mid 则在l mid 1 到l n 1 中继续查找 每通过一次关键字的比较 搜索区间的长度就缩小一次 如此不断进行下去 直到找到值等于x的元素 若当前的查找区间为空 表示查找失败 从上述查找思想可知 每进行一次关键字比较 都将原区间一分为二 故称为二分搜索 如果把要搜索区间的长度缩小一半 就称为对半搜索 程序5 6 二分搜索算法框架templateintSortableList BSearch constT 5 3 2对半搜索 对半搜索对半搜索是一种二分搜索 设当前搜索的子表为 aleft aleft 1 aright 令m left right 2 例如 假设给定有序表中关键字为8 17 25 44 68 77 98 100 115 125 将查找K 17和K 120的情况描述为以下形式 程序5 7 对半搜索递归算法templateintSortableList BSearch constT 二分查找的性能分析 为了分析二分查找的性能 可以用二叉树来描述二分查找过程 把当前查找区间的中点作为根结点 左子区间和右子区间分别作为根的左子树和右子树 左子区间和右子区间再按类似的方法 由此得到的二叉树称为二分查找的判定树 例如 对关键字序列8 17 25 44 68 77 98 100 115 125 的判定树下图 二分查找的性能分析 查找成功 最好 Ws 1 最坏 Ws logn 1 O logn 查找失败 Wf logn 1 logn 搜索成功的平均时间复杂度 从上图可知 查找根结点68 需一次查找 查找17和100 各需二次查找 查找8 25 77 115各需三次查找 查找44 98 125各需四次查找 于是 可以得到结论 二叉树第K层结点的查找次数各为k次 根结点为第1层 而第k层结点数最多为2k 1个 假设该二叉树的深度为h 则二分查找的成功的平均查找次数为 假设每个结点的查找概率相等 ASL 1 n 1 n 1 2 2 3 22 h 2h 1 1 n 设s 20 2 21 3 22 h 1 2h 2 h 2h 1则2s 21 2 22 h 2 2h 2 h 1 2h 1 h 2hs 2s s h 2h 20 21 22 2h 2 2h 1 h 2h 2h 1 ASL 1 n log2 n 1 2h 1 1 n 1 n log2 n 1 n 1 n n 1 nlog2 n 1 1 1 1 n log2 n 1 1 当n很大时 ASL log2 n 1 1可以作为二分查找成功时的平均查找长度 它的时间复杂度为 log2n 根据二叉树的性质 最大的结点数n 2h 1 h log2 n 1 于是可以得到平均查找次数 ASL s nASL 1 n h2h 2h 1 5 3 4搜索算法的时间下界 定理5 6在一个有n个元素的集合中 通过关键字值之间的比较 搜索指定关键字值的元素 任意这样的算法在最坏情况下至少需要作 logn 1次比较 5 4排序问题 问题排序是将一个元素序列调整为按指定关键字值的递增 或递减 次序排列的有序序列 合并两个有序表 合并算法排序也属于分治方法 合并 Merge 就是将两个或多个有序表合并成一个有序表 例如下图所示的两个有序表经合并运算后得到一个有序表 我们在此只用到两个有序表的合并 称为二路合并 Two waymerge 5 4 1合并排序 合并排序 Mergesort 就是利用这种合并过程进行排序 即先将n个数据看成n个长度为l的表 将相邻的表成对合并 得到长度为2的n 2个有序表 进一步再将相邻表成对合并 得到长度为4的n 4个有序表 如此重复做下去 直至所有数据均合并到一个长度为n的有序表为止 即完成排序 上述每一次的合并过程称为一趟 Pass 整个排序过程叫二路合并排序 下图是二路合并排序过程的一个例子 合并排序 7151310420198 7 15 10 13 4 20 8 19 715 1310 420 198 7101315 481920 4781013151920 合并两个有序序列 程序5 9 合并两个有序序列 Merge函数 templatevoidSortableList Merge intleft intmid intright T temp newT right left 1 inti left j mid 1 k 0 while i mid 分治法求解将待排序的元素序列一分为二分 得到两个长度基本相等的子序列 如同对半搜索的做法 然后对两个子序列分别排序 如果子序列较长 还可继续细分 直到子序列的长度不超过1为止 当分解所得的子序列已排列有序 可以采用上面介绍的将两个有序子序列 合并成一个有序子序列的方法 实现将子问题的解组合成原问题解 这是分治法不可缺少的一步 对于二路合并 如果数据个数n是2的整数次方 则所需的趟数为logn 例如n 8 logn 3 故共需三趟合并过程 如果n不是2的整数次方 则在每趟合并时表的数目不一定总是偶数个 若表的数目为奇数 就剩下一个表要 轮空 直接进入下一趟 这样 下一趟合并时此表的长度与其它的表将不相同 因此我们设计的合并过程 并不要求待合并的两个表长度必须相同 程序5 10 两路合并排序templatevoidSortableList MergeSort intleft intright if left right intmid left right 2 MergeSort left mid MergeSort mid 1 right Merge left mid right templatevoidSortableList MergeSort MergeSort 0 n 1 性能分析 合并排序递归算法的时间复杂度为 nlogn 定理5 1设a b c和k为常数 T n aT n b cnk T 1 c 则 使用递归树可以形象地看到递推式的迭代过程 例2 13T n 2T n 2 n的递归树 递归路径 n 1 2 n 1 2 2n 1 2 kn 1 1 2 kn 1 即n 2k 1 即2k n k log2n logn所以T n n logn 1 nlogn 5 4 2快速排序 快速排序采用一种特殊的分划操作对排序问题进行分解 其分解方法是 在待排序的序列 K0 K1 Kn 1 中选择一个元素作为分划元素 也称为主元 pivot 不妨假定选择K 为主元 经过一趟特殊的分划处理将原序列中的元素重新排列 使得以主元为轴心 将序列分成左右两个子序列 主元左测子序列中所有元素都不大于主元 主元右测子序列中所有元素都不小于主元 15713104201988713104151920 1 主元最后的位置就是它最终的合适位置 进一步的运算过程中此数据即不必再动 2 以后的排序运算只需在划分成的两部分里进行 两部分之间不会再有数据互换 3 第一次划分以后 再用相同的算法对划成的部分进行类似的运算 即从每部分中任选一个数据将其划分成更小的两部分 依此递归地做下去 直至每个小部分中的数据个数均不超过一个为止 排序过程即结束 15713104201988713104151920 分划操作 程序5 11 分划函数templateintSortableList Partition intleft intright 前置条件 left rightinti left j right 1 do doi while l i l left if i j Swap i j while i j Swap left j returnj 快速排序算法 程序5 12 快速排序templatevoidSortableList QuickSort QuickSort 0 n 1 templatevoidSortableList QuickSort intleft intright if left right intj Partition left right QuickSort left j 1 QuickSort j 1 right 若快速排序出现最坏的情形 每次能划分成两个子区间 但其中一个是空 因此 快速排序的最坏时间复杂度为O n2 快速排序所占用的辅助空间为栈的深度 故最好的空间复杂度为O logn 最坏的空间复杂度为O n2 若快速排序出现最好的情形 左 右子区间的长度大致相等 快速排序的最好时间复杂度应为O nlog2n 时间分析 理论上已经证明 快速排序的平均时间复杂度也为O nlogn 平均情况时间 5 4 3排序算法的时间下界 定理5 7任何一个通过关键字值比较对n个元素进行排序的算法 在最坏情况下 至少需作 n 4 logn次比较 5 5选择问题 问题选择问题 selectproblem 是指在n个元素的集合中 选出某个元素值大小在集合中处于第k位的元素 即所谓的求第k小元素问题 kth smallest 5 5 1分治法求解 设原表长度为n 假定经过一趟分划 分成两个左右子表 其中左子表是主元及其左边元素的子表 设其长度为p 右子表是主元右边元素的子表 那么 若k p 则主元就是第k小元素 否则若kp 则第k小元素必定在右子表中 需求解的子问题成为在右子表中求第k p小元素 15713104201988713104151920 5 5 2随机选择主元 随机选主元算法假定表中元素各不相同 并且随机选择主元 即在下标区间 left right 中随机选择一个下标r 以该下标处的元素为主元 程序5 13 Select函数templateResultCodeSortableList Select1 T 定理5 8程序5 13的Select算法的平均时间A n O n 算法的最坏情况时间复杂度O n2 5 5 3线性时间选择算法 改进的选择算法采用二次取中法 medianofmediansrule 确定主元 程序5 14 线性时间选择算法ResultCodeSortableList Select T templateintSortableList Select intk intleft intright intr intn right left 1 if n r InsertSort left right returnleft k 1 for inti 1 i n r i InsertSort left i 1 r left i r 1 Swap left i 1 left i 1 r Ceil r 2 1 intj Select Ceil n r 2 left left n r 1 r Swap left j j Partition left right if k j left 1 returnj elseif k j left 1 returnSelect k left j 1 r elsereturnSelect k j left 1 j 1 right r 5 5 4时间分析 以二次取中的中间值mm为主元 经过一趟分划 左 右两个子表的大小均至多为 n n r 2 r 2 设T n 为当表长为n时执行程序5 14所需的时间 T n 由三部分时间组成 T n T n 5 T 3n 4 cn用归纳法容易证明 T n 20cn n 1是线性时间的 5 5 5允许重复元素的选择算法 由于允许包含相同元素 左子表中除了小于mm的元素外 还包含与mm相同值的元素 因此 左子表的大小至多可达n n r 2 r 2 1 2 n r 2 r 2 n 1 2 n r 2 r 2 容易用归纳法证明对于所有n 90 T n T n 9 T 7n 8 cn 72cn n 90 5 6斯特拉森矩阵乘法 问题矩阵相乘 矩阵乘积的Strassen算法C AB cij n n 求C AB即对n2个元素cij进行计算 故要作n3次乘法 相当时间内没有人怀疑过是否可以用少于n3次乘法来完成 其实不然 先以n 2的矩阵乘积为例 对于矩阵 则有 共需作8次乘法和4次加法 分治法求解大矩阵 C11 A11B11 A12B21C12 A11B12 A12B22C21 A21B11 A22B21C22 A21B12 A22B22 一个四阶方阵可以看作由4个二阶方阵组成 分治法求解大矩阵 C11 A11B11 A12B21C12 A11B12 A12B22C21 A21B11 A22B21C22 A21B12 A22B22 一个n阶方阵可以看作由4个n 2阶的方阵组成 二个n阶方阵的乘积 转化为八个n 2阶方阵的乘积和4个n 2阶方阵的加法 T n n3 定理5 1设a b c和k为常数 T n aT n b cnk T 1 c 则 5 6 2斯特拉森分治法 P A11 A22 B11 B22 Q A21 A22 B11R A11 B12 B22 S A21 B21 B11 T A11 A12 B22U A21 A11 B11 B12 V A12 A22 B21 B22 C11 P S T VC12 R TC21 Q SC22 P R Q U T n nlog7 n2 81 2 2矩阵的最少乘法次数是7 目前最好的矩阵乘法的时间上界是 O n2 376 我们研究两个n位二进制数相乘的问题 用普通的方法运算 将乘数的每一位 由低位至高位 逐个去乘被乘数 每乘一次将乘积与原来的积相加 然后乘数和乘积移位一步 如此下去直至乘数的最高位运算完即得出结果 这样运算共需n2次一位乘一位运算 n n 1 次一位加一位运算和n次移位 假设两个一位数相乘 两个一位数相加和任何数移位一步所需运算时间均为O 1 即均为常数