第二讲-分治专题讲座PPT学习课件.ppt

算法设计与分析 第二讲分治 目的分治法的思想分治算法的设计方法将递归算法改写成迭代算法的一般方法重点分治法的抽象控制策略针对问题的抽象控制策略实现难点将递归算法改写成迭代算法的一般方法和实现 2 1基本策略 一 求解大规模问题的复杂性 二 化整为零 分而治之 Pn p1n1 p2n2 pknk s0 s1 sk S 分解 分治 合并 三 分治法的抽象控制策略 设 原问题输入为a n 简记为 1 n 子问题输入为a p a q 1 p q n 简记为 p q 已知 SOLUTION intdivide int int intsmall int int SOLUTIONconquer int int SOLUTIONcombine SOLUTION SOLUTION SOLUTIONDandC p q divideandconquer if small p q returnconquer p q else m divide p q returncombine DandC p m DandC m 1 q 分治法的抽象控制算法 已知n个按非降次序排列的元素a n 查找元素x是否在表中出现 若找到 返回其下标值 否则 返回一负数 2 2二分检索 一 问题 二 分治的思路 原问题 n a 0 a n 1 x 数据分组 a 0 a k 2 a k 1 a k a n 1 三个子问题 k 1 a 0 a k 2 x 1 a k 1 x n k a k a n 1 x intBinSearch1 p q x intk p q 2 if qa k returnBinSearch1 k 1 q x 三 递归算法 四 计算复杂度 1 二元比较树 以有序表的中间元素为根节点的二分树 左子树上所有元素不比父节点元素值大 右子树上所有元素不比父节点元素值小 圆形接点称为内节点 对应成功检索的数据元素 二分检索树的深度 二元比较树的深度 方形接点称为外节点 对应不成功检索的数据子集 定理2 2若n在区域 2k 1 2k 中 则对于一次成功的检索 BinSearch1至多作k次比较 而对于一次不成功的检索 或者作k 1次比较或者作k次比较 成功检索最好情况 不成功检索最好情况 成功检索最坏情况 不成功检索最坏情况 2 时间复杂度 平均情况分析 内部路径长度之和 I 5 2 7 1 3 6 8 4 9 外部路径长度之和 E E I 2n 成功检索的平均比较次数 S n I n 1 不成功检索的平均比较次数 U n E n 1 因为 U n O logn 所以 S n O logn 由此可得 S n 1 1 n U n 1 成功检索不成功检索最好最坏平均最好最坏平均O 1 O logn O logn O logn O logn O logn 二分检索的时间复杂度结论 定理2 3设a n 含有n n 1 个不同元素 排序为a 1 a n 又设用以比较为基础去判断是否x a n 的任何算法在最坏情况下所需的最小比较次数为FIND n 那么 FIND n 说明 任何以比较为基础的检索算法 最坏情况下的比较次数都不可能低于O logn 因此 二分检索是最优的最坏情况算法 3 以比较为基础检索的时间下界 思考题 1 请证明E I 2n2 请证明S n I n 1 2 3找最大和最小元素 在n个不同元素的集合a n 中同时找出它的最大和最小元素 一 问题 比较次数 2 n 1 将语句1的体改写成if a i max max a i elseif a i min min a i 直接搜索的改进方法 三 实现分治的递归算法 集合只有一个元素时 max min a i 集合只有两个元素时if a i a j max a j min a i else max a i min a j 集合中有更多元素时分治 将原集合分解成两个子集 分别求两个子集的最大和最小元素 再合并结果 递归算法 typedefstruct ElemTypemax min SOLUTION SOLUTIONMaxMin i j SOLUTIONs s1 s2 if i j s max s min a i returns if i j 1 if a i s2 max s max s1 max s max s2 max s1 min s2 min s min s1 min s min s2 min returns 时间复杂度 当n是2的幂时 即对于某个正整数k n 2k 有 令t n 表示MaxMin需要的元素比较次数 存在下列递推关系 t n 2t n 2 2 2 2t n 4 2 2 4t n 4 4 2 2k 1t 2 2k 1 2k 2 3n 2 2 当元素的比较开销与整数比较开销相当时 将前两条if语句合并为 if i j 1 对应一元素和两元素的情况 if a i a j s max a j s min a i else s max a i s min a j returns MaxMin需要的比较次数 存在下列递推关系 思考题请分析c n 递推关系式中为什么是加3而不是加2 给定一个含n个元素的集合a n 按一定次序 本课程假定均为非降次序 将其分类 排序 2 4分类 一 问题 二 插入分类 基本思想 InsertSort intn for j 1 j 0 插入分类算法 三 归并分类 基本思想 归并分类递归算法 MergeSort l h if l h m l h 2 MergeSort l m MergeSort m 1 h Merge l m h 已分类子集的归并过程 Merge low mid high ElemTypeb n l low h mid 1 k l while lmid while h high b k a h 转储剩余部分 elsewhile l mid b k a l a low high b low high 将b数组转储到a 已分类子集的归并算法 时间复杂度 缺点与改进 结合插入分类与归并分类各自的优点 四 快速分类 设计思路 实现部分分类的划分过程举例 实现部分分类的划分算法 Partition p q r a p j p 1 k q while 1 while j r k if j k t a j a j a k a k t j k elsebreak a p a k a k r returnk 快速分类算法 QuickSort p q if p q j Partition p q QuickSort p j 1 QuickSort j 1 q 时间复杂度 最坏情况 CW n n n 1 3 2 O n2 假设n个元素各不相同 划分元素随机选取 取第k 1 k n 个元素是等概率的 计算时间C n 取决于Partition的元素比较次数 平均情况 经推导可得 CA n 2 n 1 loge n 1 O nlogn 结论 快速分类算法的最坏情况时间为O n2 平均情况为O nlogn 五 几种分类算法的时间复杂度比较 结论 以比较为基础的分类算法在最坏情况下的时间下界为O nlogn 是最坏情况下的最优算法 一 问题 2 5选择 给定一个含n个元素的集合a n 找出其中第k小的元素 并将其转储到a k 三 基于分治思想的选择算法 基本思路 用partition算法实现分治 selection p q k intj j partition p q if k j return if k j selection p j 1 k elseselection j 1 q k 分治算法 思考题 1 过程MergeSort的时间复杂度是以什么计算操作频数度量的 最好情况 最坏情况 平均时间复杂度是多少 2 用C语言实现merge过程时 数组b定义为局部变量时 最小存储量需求为多少 可否定义为外部数组 最小存储量需求为多少 一 递归算法的特点 2 6消除递归 符合人的递推求解问题的自然思维习惯算法的结构简单 代码精炼 可读性好效率低 递归的基本思路 分治 输出s abc 的递归过程 voidreverse char s externElemTypestack 2 n 1 top 0 L1 if s 0 stack top s stack top L2 s s 1 gotoL1 L2 putchar s 接下来处理返回语句if top 0 return 栈为空else addr stack top 恢复地址s stack top 恢复参数if addr L2 gotoL2 改写的迭代算法 voidreverse char s inttop 0 while s 0 top s while top 0 putchar s s top 优化后的迭代算法 例2 写一个求数组a n 中的最大元素的递归算法并将其改写成迭代算法 分治的思路 思考题 为什么k不作为局部变量在L1之后入栈 可否象i j一样处理 intmax inti intj k n 1 for j n 2 j i j if a j a k k j returnk 优化后的迭代算法 例3 将分治算法的抽象递归过程改写为迭代过程 SOLUTIONDandC p q divideandconquer intm SOLUTIONs1 s2 s if small p q s conquer p q else m divide p q s1 DandC p m s2 DandC m 1 q s combine s1 s2 returns 抽象控制递归算法 SOLUTIONDandC p q externElemTypestack 5 n 1 top 0 intm SOLUTIONs1 s2 L1 if small p q s conquer p q else m divide p q stack top p stack top q stack top m stack top L2 p p q m gotoL1 L2 s1 stack top stack top p stack top q stack top m stack top L3 p m 1 q q gotoL1 L3 s2 stack top s