计算机算法设计与分析基础第五章减治法ppt课件.ppt

算法分析与设计AnalysisandDesignofComputerAlgorithms第五章减治法DecreaseandConquer 2 教学内容 减治法的一般方法及变种插入排序深度优先查找和广度优先查找生成组合对象的算法减常因子算法减可变规模算法要求掌握减治法的基本思想及在常见问题问题中的应用 概念与算法策略 算法策略减治法 利用给定规模与较小规模问题解之间的关系求解问题的方法 实现 从顶向下 规模减小 递归 从底向上 规模增大 非递归 减常量法 常量通常为1 每此迭代规模减小n n 1 减常因子法 常因子通常为2 每此迭代规模减半n n 2 减可变规模法 每次减去的规模不同 例题1 课本123页第一题 摆渡的士兵 解题 1 假设小孩与士兵在同一岸边2 考虑起始情况 即士兵 1孩子 2和后续情况 士兵 2孩子 2如图 因此可以得到n个士兵时求解的公式如下 F 1 4n 1F n F n 1 4n 1 分治法是对分解的子问题分别求解 需要对子问题的解进行合并 而减治法只对一个子问题求解 并且不需要进行解的合并 应用减治法 例如减半法 得到的算法通常具有如下递推式 分治法和减治法区别 5 1插入排序 简介插入排序的过程类似玩牌时整理手中纸牌的过程 就是对n个元素A 0 n 1 排序的一种方法 它的基本思想是 每步将一个待排序的对象按照其关键字的大小 插到前面已经排好序的序列中的适当位置 直到全部对象插入完毕为止 常用的插入排序有 直接插入排序 折半插入排序 链表插入排序和希尔排序 它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同 5 1插入排序 插入排序对n个元素A 0 n 1 排序 非降序为例 减一策略 分析过程自顶向下 规模减小 减去一个元素A n 1 对A 0 n 2 排序 非降序 原问题的解 减一规模的解 A n 1 对数组递归减一 分解到仅一个元素为止 再合并得到原问题解 插入算法 有三种方法 左右扫描称统称直接插入法左扫描 从左向右扫描有序子数组 遇到第一个 A n 1 元素为止 在该元素前插入A n 1 若未找到 则插在最后 右扫描 从右向左扫描有序子数组 遇到第一个 A n 1 元素为止 在该元素后插入A n 1 若未找到 则插在最前 常用 右扫描法 问 理由是什么 理由 子数组若有等值元素 右扫描插入时需移动的元素个数少 它插在等值元素后 前面等值元素都不用移动位置 直接插入排序举例 待排序序列 89 45 68 90 29 34 17 插入过程 89 不需比较 45 89 45 68 89 45 68 89 90 29 45 68 89 90 29 34 45 6889 90 17 29 34 45 68 89 90 插入次数 n 1 6比较次数 下划线为待插元素 思考 为什么是右扫描插入V 插入排序算法与算例 折半插入法 组合利用减一法和减半法子数组有序 用折半查找为插入元素在其中找到一个合适的位置 例题 在有序表 7 14 18 21 23 29 31 35 38 42 46 49 52 中查找值为14的记录的过程如图所示 折半查找 1 low 1 high n 设置初始查找区间2 测试查找区间 low high 是否存在 若不存在 则查找失败 否则3 取中间点mid low high 2 比较k与r mid 有以下三种情况 3 1若kr mid 则low mid 1 查找在右半区进行 转2 3 3若k r mid 则查找成功 返回记录在表中位置mid 折半查找算法描述 插入排序效率分析 插入排序效率分析输入规模 元素个数n基本操作 比较操作A j V效率类别 输入A为升序 每次插入只需比较1次 最佳效率输入A为降序 最差效率 其他 平均效率最佳效率 要插入n 1个元素 共需比较n 1次 线性效率 也可据伪码计算 最差效率对每个元素如第i个元素插入 从j i 1比较到j 0 共i次比较 即插入元素A i 要与前面的全部元素都比较一次 平均效率 比最差效率快2倍 若遇到基本有序数组 比选择排序和冒泡排序的性能略优 5 4生成组合对象的算法 1 生成排列排列问题指的是对于给定的多个元素求其中各种可能的序列 为了简单起见 这里仅仅考虑1到n之间的整数的排列问题 下面介绍三种生成方法 1 插入法 2 Johnson Trotter法 3 字典顺序法 生成组合对象算法 生成排列 生成组合对象组合对象 满足一定约束条件的集合组合数学 指出组合对象有多少个 组合数 通常呈指数级增长 如何生成 本节内容生成排列 前面讲过蛮力法 生成集合元素的全排列 可解释为 生成集合元素下标 1 2 n 的全排列 排列数 n 个减一策略 设规模减一 1 2 n 1 的全排列已解决 有 n 1 个把n插入到这 n 1 个排列中去 就解决了规模n的问题 即得 1 n 全排列 在每个 1 n 1 排列中插入n的位置有 n 1 1 n个 排列数 n 1 n n 问 这样得到的排列是唯一的吗 答 是 n 1 个排列是唯一的 在其不同位置插入一个新元素n 结果当然唯一 插入法生列排列 举例 求n 3的排列方法 在n 2的排列中插入3 在n 1的排列中插入2 过程 在1中从右到左插入2得到12 21在12中从右到左插入3得到123 132 312在21中从右到左插入3得到213 231 321于是得 123 132 312 213 231 321 Johnson Trotter法生成排列 其实有的算法并不需要知道规模n 1的排列就可以直接得到规模n的排列结果 Johnson Trotter算法就是其中一种 利用这一算法求得的排列序列还是相邻序列变化最小的一个序列集合 也就是说下一个序列与上一个序列仅仅交换了两个元素的位置 J T方法举例 在排列的每一分量上画一个箭头 求最大的移动整数k 不断移动元素 直到没有元素可移动为止 掉转所有大于k的整数方向 移动元素 如果分量k的箭头指向一个相邻的较小元素 则该分量在排列中是移动的 例n 3 从123开始 字典顺序生成排列 尽管Johnson Trotter算法非常高效 但是似乎不是那么直观 不太符合人们的思维习惯 事实上比较自然的算法称为 字典排序 lexicographicorder 算法 它是根据单词在字典中的排列顺序得到的算法 字典生成顺序举例 例n 3在 1 2 3 中按字典顺序选择 123132213231312321 5 4 2 生成幂集 生成幂集幂集n元集合A a1 a2 an 的全部子集组成的集合子集个数 2n 数学 应用举例 0 1背包问题找出n个物品中的最有价值子集 装入一个承重有限的背包中 解背包问题的蛮力法要求 生成n个物品的全部组合减一策略 用元素的下标表示 设 1 2 n 1 问题已解决 规模 1 把n插入到每一个子集 即得规模n的全部子集 与前述排列问题的减一策略的不同处 排列问题在每个 1 n 1 子集中插入元素n的位置有n个 组合问题仅1个插入位置 为什么 解释 排列问题与元素在排列中的顺序有关 组合问题与顺序无关 全部元素相同的集合就是同一个集合 生成幂集 减一算法 减一算法 实现 自底向上 规模加一 从空集开始 每次向已生成的每个子集中加入一个元素 如此继续 直到所有n个元素都加入为止 例 生成A a1 a2 a3 全部子集 减治法生成幂集 例n 3方法 在n 2的幂集中加入元素3 在n 1的幂集中加入元素2 1 n 1 1 2 1 2 加入元素2 1 2 1 2 3 1 3 2 3 1 2 3 加入元素3 降低规模的减治法可以用来求幂集 减治法的缺点也是在求解规模为n的问题时 需要得到规模为n 1的问题的解 这一过程是可以避免的 使用位串法求解集合幂集就是其中的一种解决方案 位串法生成幂集 例n 3 元素为 a1 a2 a3 方法 每一个子集与一个3位二进制串b1b2b3对应 ai属于该子集时 bi 1 否则bi 0二进制串 000 001 010 011 100 101 110 111对应子集 a3 a2 a2 a3 a1 a1 a3 a1 a2 a1 a2 a3 5 5 减常因子算法 减常因子法减治法的第2种变化 折半查找 常因子 2 注意与分治法区别这类算法效率常常是对数型 速度非常快 不要指望有很多此类算法 常因子 2的情况更是少之又少 常因子 3 每次规模减2 3 假币问题有n枚外观相同的硬币 其中有一枚假币 设假币较轻 用一架天平将这枚假币检测出来减常因子策略 多种方法 这里仅用减治策略 把n枚硬币等分为两堆 n为奇数 留下一枚硬币 把两堆放天平上 若两堆硬币重量相同 留下这枚即为假币n为偶数 较轻的一堆含假币 继续分解它 丢弃较重的那一堆 常因子 2 减半法 28 假币问题 Fake Coin 当n 1时 W n W n 2 1 W 1 0 假币问题 续 时间效率分析输入规模 硬币数n基本操作 称重 比较操作 效率类别 有最佳 最差 平均效率情况增长函数 称重次数与硬币数n的函数关系T n 1 最佳效率T n 1 n为奇数 2 最差效率解此递推式 得本算法并非最高效的算法 更高效的策略是 每次把n个硬币分为3堆 常因子 3 每次减去问题规模的2 3 称重次数约为log3n 比log2n更小 需要作1次称重将问题规模减半 5 5 2减常因子法 俄式乘法 减常因子法算例 俄式乘法 俄国农夫法 问题 两个正整数相乘 十九世纪 俄国农民广泛采用该算法 不需使用九九乘法表 文献介绍 埃及数学家早在公元前1650年就使用了该算法思想 算法策略n和m为两个正整数 计算它们的乘积 问题规模选择n 采用减治策略 可得递推式 规模减半 常因子 2 n为偶数 n为奇数 算法停止 n 1时停止 1 m m算法实现 递归法 非递归法 31 俄式乘法 两个大整数m和n乘法 32 约瑟夫斯问题 Josephus 在约瑟夫斯环中最后的幸存者是谁 偶数情况 J 2k 2J k 1奇数情况 J 2k 1 2J k 1 二进制表示 J 6 J 1102 1012 5 J 7 J 1112 1112 7 5 6 减可变规模算法 减治法的第3个主要变种 每次减小的问题规模不一样譬如 求最大公约数的欧氏算法 gcd m n gcd n mmodn 第k轮除数nk mk 1modnk 1 被除数mk nk 1取决于前一轮m和n值大小 各轮m n值比较前一轮 减小的幅度是变化的查找问题例 查找中值 中位值 选择问题 找出n元列表的第k个最小元素 第k个顺序统计量 例如 A 1 2 1 3 4 3 5 5 的第k 4个最小元素为3 记为A4 3 理解为非降序排序后的位置 A 1 1 2 3 3 4 5 5 k 1 找最小元素 A1 1 Amink n 找最大元素 A8 5 Amax中值 它比列表中一半元素值小 比另外一半元素值大 如上k 4 注意 它不是全部元素的均值 选择问题特例 查找中值 1 蛮力策略 直接基于问题本身而设计算法先对列表按非降序排序 然后选第k位置上的元素即中位值 该算法时间效率显然取决于排序算法的效率 若用合并排序等优秀算法 本算法效率类型属于O nlogn 型 2 减治策略 更高效 效率分析类似于前述的快速排序 本节略 回顾 快速排序算法中关于分区 Partition 的概念 s左边有s 1个元素值 A s s右边有n s个元素值 A s 根据中值的定义 n为奇数 s 1 n s s n 2 1 2 n为偶数s 1 1 n s s n 2 1 若s k A s 就是中值 停止条件2 若s k 分裂点在中值点右边 对s左子区递归分解 A s A k 3 若s k 分裂点在中值点左边 对s右子区递归分解 A s A k 减治法查找中值过程示例 求 已知列表A的中值 A 4 1 10 9 7 12 8 2 15 观察 中值 8解 n 9 中值元素下标k 9 2 1 5 向上取整 即中值A5 选择第1个元素为中轴p 用左右扫描法得到分裂点 并安排新顺序 p A 1 4411097128215 左右未交叉 412971281015 左右已交叉 214971281015 得到分裂点 s 3k 5 处理左子区p A 4 8214 87 9121015 左右相等为7 214789121015 得到分裂点 s 5 k 停止 中值为A5 8 减治法查找中值的算法效率 插值查找 减可变规模法应用实例算法意义 对某些查找问题 进一步提高折半查找效率 算法要求 先对输入的n元列表排序 即有序列表 问题描述 折半查找 每轮用列表中点将列表减半即规模减半 我们自然要问 就某些问题而言 是否有更好的分点将列表规模减小呢 回答是肯定的 这即是插值点 它可将包含问题解的区域缩得更小 比一半还小 从而减少问题规模的分解次数 获得更高的查找效率 插值查找法一个实例 查字典 如电子辞典的检索 问题描述 在英文字典中查找某个单词 字典格式 按字母升序格式安排单词条目 已排序 查找策略 我们并非采用折半查找法 而是依据先验知识 首先翻到尽量靠近待查单词的首字母附近 比如查找单词word 你不会翻到字典中间开始查 而是翻到字典中尽量靠后的地方开始查找 这与查baby不一样 然后 将这次翻到的位置上字母 与待查单词作比较后决定下次查找方向 比较字母值的大小 和页码增量 比较字母值的差距 多次查找后即可找到 插值查找算法图解 元素下标x 元素值A x 插值直线 构造 真实曲线 未知 因为A x t A x 所以应在 x r 区间查找A x l x 区域被丢弃 无解 为此左端点移位l x重新构造插值曲线 蓝色线 继续迭代过程 直到A x t A x 为止 输出查找结果x 元素值A x