减治法
- 格式：ppt
- 大小：407.00 KB
- 文档页数：25
下载文档原格式
合集下载
5-第五章 减治法
2.比较v和 A[x]
确定查找范围
5.6.3 二叉查找树的查找和插入
• 二叉查找树：左子树的值小于根顶点，右 子树大于根顶点。
小结
5．4 生成组台对象的算法
• 组合问题 1、计数 2、结构
组合问题
5．4．1 生成排列
用减一思想生成{1,2,…,n}所有排列。
Johnson-trotter算法
• 字典序---增序排队
5．4．2 生成子集
1、挤压序： 所 2、是否存在—种生成比特串的最小变化算法，使得每
一个比特串和它的直接前趋之间仅仅相差一 个比特 位。
n / 2 ，它要求找出这样一个元素，该元素比列表中的—半元素大，又比另—半元素
小。这个中间的值被称为中值，它在数理统计中是—个非常重要的量。
• 类似快速排序的分区做法
• 例
15 15
效率分析： 1）平均效率 2）最差效率
5.6.2 插值查找
插值查找用于有序数组，“插值”代替了折 半查找中的中间值 1.计算
• 最坏输入是一个严格递减的数组，这种输 入的比较次数是
• 最好的情况下（升序），在外部循环的每 次送代中，比较操作只执行一次
• 平均
5.2深度优先查找和广度忧先查找
• 什么叫图的遍历 从图的任意点出发沿着一些边访问图中的 所有顶点,且使每个顶点仅被访问一次,这就 叫图的遍历. • 我们来看一下图的遍历的两种方法: 1.深度优先搜索 2.广度优先搜索
第一种算法是深度优先查找的一个简单应用：执行一次DFS遍 历，并记住顶点变成死端(即退出遍历栈)的顺序。将该次序反过来 就得到了拓扑排序的一个解。
第二种算法基于减(减一)治技术的一个直 接实现：不断地做这样—件事，在余下的有向 图中求出一个源，它是一个没有输入边的顶点， 然后把它和所有从它出发的边都删除。
第 五 章 减治法
仅仅通过一次重量的比较，就可以判断伪币是否存在。
算 分 析 与 设 计
西南科技大学
金块问题
有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一 个金块。按规矩，排名第一的雇员将得 到袋中最重的金块，排名最后的雇员将 得到袋中最轻的金块。如果每个月都有 新的金块周期性的加入袋中，则每个月 都必须找出最轻和最重的金块。假设有 一台比较重量的仪器，我们希望用最少 的比较次数找出最轻和最重的金块。
算 分 析 与 设 计
西南科技大学
直接插入排序实现方法
减一技术下，该方法遵循的思路是：假设对较 小数组 A[0..n-2]排序问题已经解决了，得到一 个大小为n-1的有序数组。然后将要排序的第n 个元素，插入到数组的适合位置上，得到大小 为n的有序数组 A[0..n-1]。伪代码如下： void InsertionSort(a[]) {for(i=1;i<n-1;i++) //从第二个记录起进行插入 for (j=i-1; j>=0;j--) if a[j+1]-(a[j]) < 0 Swap(a[j+1], a[j]); }
算 分 析 与 设 计
西南科技大学
俄式乘法☺ 俄式乘法☺
算法思想：两个A和B数相乘，把数A每 次除以2，直到为0为止，另一个数B则不 断加倍，若第数A未除尽时，则数B应加 上自己。 7×8的计算步骤： 7 8 3 16＋ 8 1 32＋ 16 ＋ 8
算 分 析 与 设 计
西南科技大学
约瑟夫斯问题（ 约瑟夫斯问题（一）
算 分 析 与 设 计
西南科技大学
减常数因子减治法
减常数因子减治法的一个 典型算法就是折半查找 （Bin_Search）。它搜索 一个排序好的数组，将查 找目标与数组的中间位置 的元素相比，比它大则递 归查找数组的左边，反之 亦然。这个每次迭代都将 问题减小为原来的1/2。 折半查找每次都消去一个 常数因子2，因此其时间 效率为O(logn)。
算 分 析 与 设 计
西南科技大学
金块问题
有一个老板有一袋金块。每个月将有两 名雇员会因其优异的表现分别被奖励一 个金块。按规矩，排名第一的雇员将得 到袋中最重的金块，排名最后的雇员将 得到袋中最轻的金块。如果每个月都有 新的金块周期性的加入袋中，则每个月 都必须找出最轻和最重的金块。假设有 一台比较重量的仪器，我们希望用最少 的比较次数找出最轻和最重的金块。
算 分 析 与 设 计
西南科技大学
直接插入排序实现方法
减一技术下，该方法遵循的思路是：假设对较 小数组 A[0..n-2]排序问题已经解决了，得到一 个大小为n-1的有序数组。然后将要排序的第n 个元素，插入到数组的适合位置上，得到大小 为n的有序数组 A[0..n-1]。伪代码如下： void InsertionSort(a[]) {for(i=1;i<n-1;i++) //从第二个记录起进行插入 for (j=i-1; j>=0;j--) if a[j+1]-(a[j]) < 0 Swap(a[j+1], a[j]); }
算 分 析 与 设 计
西南科技大学
俄式乘法☺ 俄式乘法☺
算法思想：两个A和B数相乘，把数A每 次除以2，直到为0为止，另一个数B则不 断加倍，若第数A未除尽时，则数B应加 上自己。 7×8的计算步骤： 7 8 3 16＋ 8 1 32＋ 16 ＋ 8
算 分 析 与 设 计
西南科技大学
约瑟夫斯问题（ 约瑟夫斯问题（一）
算 分 析 与 设 计
西南科技大学
减常数因子减治法
减常数因子减治法的一个 典型算法就是折半查找 （Bin_Search）。它搜索 一个排序好的数组，将查 找目标与数组的中间位置 的元素相比，比它大则递 归查找数组的左边，反之 亦然。这个每次迭代都将 问题减小为原来的1/2。 折半查找每次都消去一个 常数因子2，因此其时间 效率为O(logn)。
算法(复习题)1
平均情况:设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若出现在数组中每个位置的概率是均等的为p/nT(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1=p/2+n(1-p/2)1.叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。
答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解。
动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单的通过查表过的该子问题的解,避免了大量的重复计算.异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的。
分治法是自顶向下用递归的方法解决问题，而动态规划则是自底向上非递归解决问题。
1.简述分治算法求解过程的三个阶段。
答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。
（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。
（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。
2.叙述分治法的基本思想，并分析分治法与减治法二者的区别。
答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解.区别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解进行合并并得到原问题的解。
减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。
算法笔记_004：8枚硬币问题【减治法】
算法笔记_004：8枚硬币问题【减治法】⽬录1 问题描述（1）实验题⽬在8枚外观相同的硬币中，有⼀枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相⽐较轻还是较重。
可以通过⼀架天平来任意⽐较两组硬币，设计⼀个⾼效的算法来检测这枚假币。
（2）实验⽬的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提⾼应⽤减治法设计算法的技能。
3）理解这样⼀个观点：建⽴正确的模型对于问题的求解是⾮常重要的。
（3）实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察⽤减治技术设计的算法是否⾼效；3）扩展算法，使之能处理n枚硬币中有⼀枚假币的问题。
（4）实现提⽰假设⽤⼀个数组B[n]表⽰硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有⼀个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。
由于8枚硬币问题限制只允许使⽤天平⽐较轻重，所以，算法中只能出现元素相加和⽐较的语句。
2 解决⽅案2.1 减治法原理叙述在说减法法原理之前，我们先来简单看看分治法原理：分治法是把⼀个⼤问题划分为若⼲⼦问题，分别求解⼦问题，然后再把⼦问题的解进⾏合并得到原问题的解。
⽽减治法同样是把⼤问题分解成为若⼲个⼦问题，但是这些⼦问题不需要分别求解，只需求解其中的⼀个⼦问题，也⽆需对⼦问题进⾏合并。
换种说法，可以说减治法是退化的分治法。
减治法原理正式描述：减治法（reduce and conquer method）将原问题的解分解为若⼲个⼦问题，并且原问题的解与⼦问题的解之间存在某种确定关系，如果原问题的规模为n，则⼦问题的规模通常是n/2 或n-1。
2.2 8枚硬币规模解法求解思路：（1）⾸先输⼊8枚硬币重量，存放在⼀个长度为8的⼀维数组中。
（2）定义a,b,c,d,e,f,g,h⼋个变量，分别对应⼀枚硬币的重量。
然后把这8枚硬币分成三组，分别为abc(abc = a+b+c)、def(def =d+e+f)、gh。
第7章 减治法(《算法设计与分析(第3版)》C++版 王红梅 清华大学出版社)
比较对象，若 k 与中间元素相等，则查找成功；若 k 小于中间元素，则在中间元
算 法 设
计
素的左半区继续查找；若 k 大于中间记录，则在中间元素的右半区继续查找。不
与 分
析
断重复上述过程，直到查找成功，或查找区间为空，查找失败。
（ 第
版 ）
k
清 华
大
学
[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] （mid=(1+n)/2）
Page 4
3
7.1.2 一个简单的例子——俄式乘法
【问题】俄式乘法（russian multiplication）用来计算两个正整数 n 和 m 的乘积
，运算规则：如果 n 是偶数，计算 n/2×2m；如果 n 是奇数，计算(n-1)/2×2m＋
m；当 n 等于 1 时，返回 m 的值。
算
法
俄式乘法的优点？
与 分 析
2. 测试查找区间［low，high］是否存在，若不存在，则查找失败，返回 0；
（ 第
3. 取中间点 mid = (low+high)/2; 比较 k 与 rmid，有以下三种情况：
版 ）
3.1 若 k < rmid，则 high = mid - 1；查找在左半区进行，转步骤2；
清 华
3.2 若 k > rmid，则 low = mid + 1；查找在右半区进行，转步骤2；
Page 12
7.2.2 选择问题
【想法】假定轴值的最终位置是 s，则： （1）若 k=s，则 rs 就是第 k 小元素； （2）若 k<s，则第 k 小元素一定在序列 r1 ~ rs-1 中； （3）若 k>s，则第 k 小元素一定在序列 rs+1 ~ rn 中。
背包问题(修改)
（5）可行函数feasible：检查解集合中加入一个候 选对象是否可行，即解集合扩展后是否满足约束条 件。例如，在付款问题中，可行函数是每一步选择 的货币和已付出的货币相加不超过应付款。
贪心法的一般过程
Greedy(C) //C是问题的输入集合即候选集合 {
S={ }; //初始解集合为空集 while (not solution(S)) //集合S没有构成问题的一个解 {
例：付款问题： 超市的自动柜员机（POS机）要找给顾客数量最少的现金。
假 定 POS 机 中 有 n 张 面 值 为 pi(1≤i≤n) 的 货 币 ， 用 集 合 P={p1, p2, …, pn}表示，如果POS机需支付的现金为A，那么， 它必须从P中选取一个最小子集S，使得
m
pi S , pi = A (m =| S |) i =1
an=a×a×…×a n次
蛮力法所赖的基本技术——扫描技 术
关键——依次处理所有元素 基本的扫描技术——遍历
（1）集合的遍历 （2）线性表的遍历 （3）树的遍历 （4）图的遍历
虽然巧妙和高效的算法很少来自于蛮力法，基于 以下原因，蛮力法也是一种重要的算法设计技术：
（1）理论上，蛮力法可以解决可计算领域的各种问题。 （2）蛮力法经常用来解决一些较小规模的问题。 （3）对于一些重要的问题蛮力法可以产生一些合理的算 法，他们具备一些实用价值，而且不受问题规模的限制。 （4）蛮力法可以作为某类问题时间性能的底限，来衡量 同样问题的更高效算法。
减治法
普卢塔克说，萨特斯为了告诉他的士兵坚韧和 智慧比蛮力更重要的道理，把两匹马带到他们面前， 然后让两个人扒光马的尾毛．一个人是魁梧的大力 士，他抓住尾巴扒了又扒，但一点效果也没有；另 一个人是一个精明的、长相狡黠的裁缝，他微笑着， 每次扒掉一根毛，很快就把尾巴拔得光秃秃的。
贪心法的一般过程
Greedy(C) //C是问题的输入集合即候选集合 {
S={ }; //初始解集合为空集 while (not solution(S)) //集合S没有构成问题的一个解 {
例：付款问题： 超市的自动柜员机（POS机）要找给顾客数量最少的现金。
假 定 POS 机 中 有 n 张 面 值 为 pi(1≤i≤n) 的 货 币 ， 用 集 合 P={p1, p2, …, pn}表示，如果POS机需支付的现金为A，那么， 它必须从P中选取一个最小子集S，使得
m
pi S , pi = A (m =| S |) i =1
an=a×a×…×a n次
蛮力法所赖的基本技术——扫描技 术
关键——依次处理所有元素 基本的扫描技术——遍历
（1）集合的遍历 （2）线性表的遍历 （3）树的遍历 （4）图的遍历
虽然巧妙和高效的算法很少来自于蛮力法，基于 以下原因，蛮力法也是一种重要的算法设计技术：
（1）理论上，蛮力法可以解决可计算领域的各种问题。 （2）蛮力法经常用来解决一些较小规模的问题。 （3）对于一些重要的问题蛮力法可以产生一些合理的算 法，他们具备一些实用价值，而且不受问题规模的限制。 （4）蛮力法可以作为某类问题时间性能的底限，来衡量 同样问题的更高效算法。
减治法
普卢塔克说，萨特斯为了告诉他的士兵坚韧和 智慧比蛮力更重要的道理，把两匹马带到他们面前， 然后让两个人扒光马的尾毛．一个人是魁梧的大力 士，他抓住尾巴扒了又扒，但一点效果也没有；另 一个人是一个精明的、长相狡黠的裁缝，他微笑着， 每次扒掉一根毛，很快就把尾巴拔得光秃秃的。
蛮力法、分治法、减治法三种方法的理解和处理问题的类型的归纳
蛮力法、分治法、减治法三种方法的理解和处理问题的类型的归纳一、蛮力法蛮力法是一种基础且直接的问题解决策略，通常用于寻找问题的答案或解决方案。
其核心理念在于，通过逐一检查所有可能的解决方案，从而找到问题的答案或找到最佳的解决方案。
在蛮力法中，我们通常需要投入较多的时间和计算资源，尤其是在面对大规模或复杂的问题时。
蛮力法的应用范围广泛，包括但不限于以下几种类型的问题：1. 排序问题：例如，对一个数组进行排序，我们可以使用蛮力法，通过比较每对元素并交换它们的位置，使得整个数组有序。
2. 查找问题：例如，在排序数组中查找一个特定的元素，我们可以使用蛮力法，逐一检查数组中的每个元素直到找到目标元素。
3. 组合与排列问题：例如，计算给定集合的所有可能排列或组合，我们可以使用蛮力法，通过逐一排列或组合所有可能的元素组合得到答案。
二、分治法分治法是一种将复杂问题分解为更小、更易于处理的子问题的方法。
通过将问题分解为独立的子问题，我们可以分别解决每个子问题，然后将这些解决方案组合起来，形成原始问题的解决方案。
这种方法在处理复杂问题时非常有效，因为它可以降低问题的复杂性，使我们可以更有效地解决问题。
分治法的应用范围广泛，包括但不限于以下几种类型的问题：1. 排序问题：例如，归并排序就是一种使用分治法的排序算法，它将一个大列表分解为两个小列表，对这两个小列表分别进行排序，然后合并它们以得到有序列表。
2. 搜索问题：例如，二分搜索是一种使用分治法的搜索算法，它将搜索空间一分为二，每次迭代都排除一半的元素，直到找到目标元素或确定元素不存在。
3. 图问题：例如，Dijkstra的算法就是一种使用分治法的图搜索算法，它将图分解为最短路径树，然后通过搜索每个子图的最短路径来解决整个图的最短路径问题。
三、减治法减治法是一种通过减少问题的规模或复杂性来解决问题的方法。
其核心理念在于，通过消除或减少问题的某些部分或特性，从而降低问题的复杂性或规模，使得问题更容易解决。
实验三 减治法的验证与思考实验
实验三减治法的验证与思考实验
实验一：验证课本上的折半查找算法
实验二：验证课本上的堆排序算法
实验三：小组思考题
拿子游戏。
考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有n根火柴，两个玩家轮流拿走1根、2根、3根、4根，拿走最后一根火柴的玩家获胜，请为先拿的玩家设计一个必胜策略（如果策略存在）。
实验四：小组思考题
在120枚外观完全相同的硬币中有一个假币，假币重量与真币不同，可以通过一个天平来比较两组硬币的重量，试问最少用几次称重可以找到这枚假币。
计算思维06-3.3 算法思想简介讲课提纲_20
第3章 算法思维3.3 算法思想简介20世纪中期以后，随着计算机的出现、发展，算法广泛地运用于种类问题的求解，成为计算机科学的灵魂，涌现出精彩纷呈的算法。
3.3.1 蛮力法蛮力法也称穷举法，其基本思想是采用一定的策略，将待解决问题的所有可能列出来，找出问题的解。
《算经》中的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何？该问题的解决方案是：设公鸡为x 只，母鸡为y 只，小鸡为z 只；则x 的取值范围为0到20，y 的取值范围为0到33，z 的取值范围为0到100，当然z 应该为3的倍数；这样总共有21×34×34，即24276种组合方案，其中满足条件x +y +z =100，并且5x +3y +z /3=100的组合就是问题的解。
[百钱百鸡VB 伪代码] p 1tep 3d (5x+3y+z/3=100)Then 采用的关键技术是描述，算法设计时应避免重复试探，时间复杂度较高，效率较低，分而治之N }，其 中某段的和定义为1 设序列A 中有素，其最大段和为maxsum ；序列A 的开始位置为left ，结束位置为right 序列A left 和A rigth ，序列A left 的最大子段和为leftsu 相同，即用递归进一步分解子序列A left 和A left 中，其值为leftsum ；也有可能处在子序For x=0 To 20 Step 1 For y=0 To 33 Ste For z=0 To 100 S If (x+y+z=100)An Print x;y;z End If Next x Next y Next x蛮力法但现在的计算机有超强的计算能力，仍是直接解决问题的一种常用思路。
3.3.2 分治法分治法的基本思想是将一个难以直接解决的大问题划分成一些规模较小的子问题，，其求解过程通常由划分、求解子问题和合并3个阶段组成，如图3-8所示。
减治法
第5章减治法（Decrease and Conquer）减治法的基本思想规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：（1）原问题的解只存在于其中一个较小规模的子问题中；（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。
由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。
2减治法的基本思想一旦建立了这种关系，就可以从顶至下（递归），也可以从底至上（非递归）的来运用Example, n!A top down (recursive) solutionA bottom up (iterative) solution3减治法的类型减治法有三种变种：1)减去一个常量2)减去一个常数因子3)减去的规模是可变的gcd（m, n）4减（一）治技术a problem of size nsubproblemof size n-1a solution to thesubprobleme.g., n!a solution tothe original problem5减(半) 治技术a problem of size nsubproblemof size n/2a solution to thesubprobleme.g., Binary searcha solution tothe original problem67典型的分治法subproblem 2 of size n /2subproblem 1 of size n /2a solution to subproblem 1 a solution to the original problema solution to subproblem 2a problem of size ne.g., mergesort减治与分治的区别考虑以下指数问题: 计算a n减一法Bottom-up: iterative (brute Force) Top-down:recursive分治法:减常因子法:a n= a*a*a*a*...*aa n= a n-1* a if n > 1= a if n = 1a n= a ⎣n/2 ⎦* a ⎡n/2⎤if n > 1= a if n = 1a n = (a n/2 ) 2if n is even and positive= (a(n-1)/2 ) 2 * a if n is odd and > 1 = a if n = 1O (log2n) O (n log2n)89111)2/(0)(>=⎩⎨⎧+=n n n T n T 所以，通常来说，应用减治法处理问题的效率是很高的，一般是O (log 2n)数量级。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
原问题 的规模是n
子问题 的规模是n/2 子问题的解
原问题的解
图5.1 减治法的典型情况（减半技术）
对于给定的整数a和非负整数n，计算an的值。
利用减治法，如果n=1，可以简单地返回a的值，如果n是偶数并且n>1，可 以把该问题的规模减半，即计算an/2的值，而且规模为n的解an和规模减半 的解an/2之间具有明显的对应关系：an＝(an/2)2，如果n是奇数并且n>1，可 以先用偶指数的规则计算a(n-1)，再把结果乘以a。所以，应用减治技术得到 如下计算方法：
排序问题中的减治法
堆排序
选择问题
堆排序
例
28 25 36 18 32 28 36 25 18 16 32 25 16 36 25 18 16 36 28 32
28
18 16
32
堆排序是利用堆（假设利用大根堆）的特性进 行排序的方法，其基本思想是：首先将待排序 的记录序列构造成一个堆，此时，选出了堆中 所有记录的最大者即堆顶记录，然后将它从堆 中移走（通常将堆顶记录和堆中最后一个记录 交换），并将剩余的记录再调整成堆，这样又 找出了次大的记录，以此类推，直到堆中只有 一个记录为止。
n 1 n 1
查找问题中的减治法
折半查找
二叉查找树
折半查找
在有序表{ 7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46, 49, 52 }中查找值为14的 记录的过程如图所示。
0 1
7
2
14
3
18
4
21
5
23
6
29
7
31
8
35
9
38
10
42
1146124913 a n a
n
a
2
n 1
2
a n
n 1
分治法和减治法区别
分治法是对分解的子问题分别求解，需要对子问 题的解进行合并，而减治法只对一个子问题求解， 并且不需要进行解的合并。应用减治法（例如减 半法）得到的算法通常具有如下递推式：
0 T (n) T ( n / 2) 1
均≤rs 轴值 均≥rs 均≤rs 轴值 均≥rs
(a) 若k<s，则rk在左半区
(b) 若k>s，则rk在右半区
图5.10 选择问题的减治思想
以5为轴值划分序列
4<5，只在左侧查找
5 3 8 1 4 6 2 3 4 1 5 6
9 2 7 9 8 7
以2为轴值划分序列
4>2，只在右侧查找 以4为轴值划分序列 4＝4，轴值即为第4小元素 图5.11
算法与算法复杂性
王 涛
长春工业大学
计算机科学与工程学院 wangtao690103@
第五章
减 治 法
减治是基于变换的思想。 分两个阶段工作，即“变”阶段和“治”阶段. 变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction)
因为n=2k，所以，外层的while循环共执行k次，在每一次执 行时，内层的for循环的执行次数分别是n/2，n/4，…，1， 而函数comp可以在常数时间内完成，因此，算法5.8的执行 k 时间为： n 1 T ( n ) i n (1 k ) n 1 O ( n ) 2 i 1 2
组合问题中的减治法
5.4.1 淘汰赛冠军问题 5.4.2 假币问题
5.4.1 淘汰赛冠军问题 问题描述：假设有n=2k个选手进行竞技 淘汰赛，最后决出冠军的选手。
算法5.8——淘汰赛冠军问题 string Game(string r[ ], int n) { i=n; while (i>1) { i=i/2; for (j=0; j<i; j++) if (Comp(r[j+i], r[j])) r[j]=r[j+i]; } return r[0]; }
图 折半查找成功情况下的查找过程
折半查找 1. low=1；high=n； //设置初始查找区间 2. 测试查找区间［low，high］是否存在，若不存 在，则查找失败；否则 3. 取中间点mid=(low+high)/2; 比较k与r[mid]，有 以下三种情况： 3.1 若k<r[mid]，则high=mid-1；查找在左半区 进行，转2； 3.2 若k>r[mid]，则low=mid+1；查找在右半区 进行，转2； 3.3 若k=r[mid]，则查找成功，返回记录在表中位 置mid；
52
low=1
设置初始区间 mid=7
high=13 查找区间为[1, 13] 取中点mid=7 比较r[7]与k，将查找调整到左半区
low=1 mid=3 low=1 high=2 mid=1 low=high=2 mid=2
high=6
查找区间为[1, 6] 取中点mid=3 比较 r[3]与k，将查找调整到左半区 查找区间为[1, 2] 取中点mid=1 比较r[1]与k，将查找调整到右半区 查找区间为[2, 2] 取中点mid=2 比较r[2]与k，查找成功，返回mid的位置2
算法5.7的效率取决于轴值的选取。如果每次划分的轴值恰好 是序列的中值，则可以保证处理的区间比上一次减半，由于 在一次划分后，只需处理一个子序列，所以，比较次数的递 推式应该是： T ( n ) T ( n 2) O ( n ) 使用扩展递归技术对递推式进行推导，得到该递推式的解 是O(n)，这是最好情况；如果每次划分的轴值恰好是序列 中的最大值或最小值（例如，在找最小元素时总是在最大 元素处划分），则处理区间只能比上一次减少1个，所以， 比较次数的递推式应该是：
考虑快速排序中的划分过程，一般情况下，设待划分的 序列为ri ～ rj，选定一个轴值将序列ri ～ rj进行划分， 使得比轴值小的元素都位于轴值的左侧，比轴值大的元 素都位于轴值的右侧，假定轴值的最终位置是s，则： （1）若k=s，则rs就是第k小元素； （2）若k<s，则第k小元素一定在序列ri ～ rs-1中且为第 k小元素；
T ( n) T ( n 1) O ( n)
使用扩展递归技术对递推式进行推导，得到该递推式的解是 O(n2)，这是最坏情况；平均情况下，假设每次划分的轴值是 划分序列中的一个随机位置的元素，则处理区间按照一种随 机的方式减少，可以证明，算法5.7可以在O(n)的平均时间内 找出n个元素中的第k小元素。
a a n (a n 2 ) 2 ( n 1) 2 2 ) a ( a n 1 n 1且是偶数 n 1且是奇数
利用分治法，如果n=1，可以简单地返回a的值，如果n>1，可以把该问题分 解为两个子问题：计算前 n 2 个a的乘积和后 n 2 个 a的乘积，再把这两 个乘积相乘得到原问题的解。所以，应用分治技术得到如下计算方法：
5.4.2 假币问题
在n枚外观相同的硬币中，有一枚是假币， 并且已知假币较轻。已经有一架没有刻度的 天平，试设计一个算法使其时间复杂度为
T(n)=O(log2n)。 T(n)=O(log2n)
不知假币是轻是重？
a+b+c?d+e+f > a+e?d+b > a?h > = c?h > = < b?h g?a > g:H = h:L g?h > < h?a > = > e:H > e?h = b:L > f:H = <
（3）若k>s，则第k小元素一定在序列rs+1 ～ rj中且为第 k-s小元素； 无论哪种情况，或者已经得出结果，或者将选择问题 的查找区间减少一半（如果轴值恰好是序列的中值）。 选择问题的减治思想如图5.10所示。
[ ri … rk … rs-1 ] rs [ rs+1 … … rj ] [ ri … … rs-1 ] rs [ rs+1 …rk … rj ]
二叉查找树
在二叉查找树中查找关键字值为35，95的过程：
50 30 20 40 80 90 85 20 35 30 40 50 80 90
35
32
85
88
88
32
二叉排序树的查找 BiNode * SearchBST(BiNode *root, int k) { if (root= =NULL) return NULL； else if (root->data==k) return root; else if (k<root->data) return SearchBST(root->lchild, k); else return SearchBST(root->rchild, k); }
simpler instance
or
problem’s instance
Another representation or another problem’s instance
solution
减治法的设计思想
（1）原问题的解只 存在于其中一个较小 规模的子问题中； （2）原问题的解与 其中一个较小规模的 解之间存在某种对应 关系。
2 3 4 1 · · ·· · 1 2 4 3 · · ·· · · ·4 3 · · · · ·
· · 3 4
· · · · ·
选择问题的查找过程示例（查找第4小元素）
算法5.7——选择问题 1. i=1; j=n; //设置初始查找区间 2．以r[i]为轴值对序列r[i]~r[j]进行一次 划分，得到轴值的位置s; 3. 将轴值位置s与k比较 3.1 如果k=s，则将r[s]作为结果返回； 3.2 否则，如果k<s，则j=s-1，转步骤2； 3.3 否则，i=s+1，转步骤2；
子问题 的规模是n/2 子问题的解
原问题的解
图5.1 减治法的典型情况（减半技术）
对于给定的整数a和非负整数n，计算an的值。
利用减治法，如果n=1，可以简单地返回a的值，如果n是偶数并且n>1，可 以把该问题的规模减半，即计算an/2的值，而且规模为n的解an和规模减半 的解an/2之间具有明显的对应关系：an＝(an/2)2，如果n是奇数并且n>1，可 以先用偶指数的规则计算a(n-1)，再把结果乘以a。所以，应用减治技术得到 如下计算方法：
排序问题中的减治法
堆排序
选择问题
堆排序
例
28 25 36 18 32 28 36 25 18 16 32 25 16 36 25 18 16 36 28 32
28
18 16
32
堆排序是利用堆（假设利用大根堆）的特性进 行排序的方法，其基本思想是：首先将待排序 的记录序列构造成一个堆，此时，选出了堆中 所有记录的最大者即堆顶记录，然后将它从堆 中移走（通常将堆顶记录和堆中最后一个记录 交换），并将剩余的记录再调整成堆，这样又 找出了次大的记录，以此类推，直到堆中只有 一个记录为止。
n 1 n 1
查找问题中的减治法
折半查找
二叉查找树
折半查找
在有序表{ 7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46, 49, 52 }中查找值为14的 记录的过程如图所示。
0 1
7
2
14
3
18
4
21
5
23
6
29
7
31
8
35
9
38
10
42
1146124913 a n a
n
a
2
n 1
2
a n
n 1
分治法和减治法区别
分治法是对分解的子问题分别求解，需要对子问 题的解进行合并，而减治法只对一个子问题求解， 并且不需要进行解的合并。应用减治法（例如减 半法）得到的算法通常具有如下递推式：
0 T (n) T ( n / 2) 1
均≤rs 轴值 均≥rs 均≤rs 轴值 均≥rs
(a) 若k<s，则rk在左半区
(b) 若k>s，则rk在右半区
图5.10 选择问题的减治思想
以5为轴值划分序列
4<5，只在左侧查找
5 3 8 1 4 6 2 3 4 1 5 6
9 2 7 9 8 7
以2为轴值划分序列
4>2，只在右侧查找 以4为轴值划分序列 4＝4，轴值即为第4小元素 图5.11
算法与算法复杂性
王 涛
长春工业大学
计算机科学与工程学院 wangtao690103@
第五章
减 治 法
减治是基于变换的思想。 分两个阶段工作，即“变”阶段和“治”阶段. 变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction)
因为n=2k，所以，外层的while循环共执行k次，在每一次执 行时，内层的for循环的执行次数分别是n/2，n/4，…，1， 而函数comp可以在常数时间内完成，因此，算法5.8的执行 k 时间为： n 1 T ( n ) i n (1 k ) n 1 O ( n ) 2 i 1 2
组合问题中的减治法
5.4.1 淘汰赛冠军问题 5.4.2 假币问题
5.4.1 淘汰赛冠军问题 问题描述：假设有n=2k个选手进行竞技 淘汰赛，最后决出冠军的选手。
算法5.8——淘汰赛冠军问题 string Game(string r[ ], int n) { i=n; while (i>1) { i=i/2; for (j=0; j<i; j++) if (Comp(r[j+i], r[j])) r[j]=r[j+i]; } return r[0]; }
图 折半查找成功情况下的查找过程
折半查找 1. low=1；high=n； //设置初始查找区间 2. 测试查找区间［low，high］是否存在，若不存 在，则查找失败；否则 3. 取中间点mid=(low+high)/2; 比较k与r[mid]，有 以下三种情况： 3.1 若k<r[mid]，则high=mid-1；查找在左半区 进行，转2； 3.2 若k>r[mid]，则low=mid+1；查找在右半区 进行，转2； 3.3 若k=r[mid]，则查找成功，返回记录在表中位 置mid；
52
low=1
设置初始区间 mid=7
high=13 查找区间为[1, 13] 取中点mid=7 比较r[7]与k，将查找调整到左半区
low=1 mid=3 low=1 high=2 mid=1 low=high=2 mid=2
high=6
查找区间为[1, 6] 取中点mid=3 比较 r[3]与k，将查找调整到左半区 查找区间为[1, 2] 取中点mid=1 比较r[1]与k，将查找调整到右半区 查找区间为[2, 2] 取中点mid=2 比较r[2]与k，查找成功，返回mid的位置2
算法5.7的效率取决于轴值的选取。如果每次划分的轴值恰好 是序列的中值，则可以保证处理的区间比上一次减半，由于 在一次划分后，只需处理一个子序列，所以，比较次数的递 推式应该是： T ( n ) T ( n 2) O ( n ) 使用扩展递归技术对递推式进行推导，得到该递推式的解 是O(n)，这是最好情况；如果每次划分的轴值恰好是序列 中的最大值或最小值（例如，在找最小元素时总是在最大 元素处划分），则处理区间只能比上一次减少1个，所以， 比较次数的递推式应该是：
考虑快速排序中的划分过程，一般情况下，设待划分的 序列为ri ～ rj，选定一个轴值将序列ri ～ rj进行划分， 使得比轴值小的元素都位于轴值的左侧，比轴值大的元 素都位于轴值的右侧，假定轴值的最终位置是s，则： （1）若k=s，则rs就是第k小元素； （2）若k<s，则第k小元素一定在序列ri ～ rs-1中且为第 k小元素；
T ( n) T ( n 1) O ( n)
使用扩展递归技术对递推式进行推导，得到该递推式的解是 O(n2)，这是最坏情况；平均情况下，假设每次划分的轴值是 划分序列中的一个随机位置的元素，则处理区间按照一种随 机的方式减少，可以证明，算法5.7可以在O(n)的平均时间内 找出n个元素中的第k小元素。
a a n (a n 2 ) 2 ( n 1) 2 2 ) a ( a n 1 n 1且是偶数 n 1且是奇数
利用分治法，如果n=1，可以简单地返回a的值，如果n>1，可以把该问题分 解为两个子问题：计算前 n 2 个a的乘积和后 n 2 个 a的乘积，再把这两 个乘积相乘得到原问题的解。所以，应用分治技术得到如下计算方法：
5.4.2 假币问题
在n枚外观相同的硬币中，有一枚是假币， 并且已知假币较轻。已经有一架没有刻度的 天平，试设计一个算法使其时间复杂度为
T(n)=O(log2n)。 T(n)=O(log2n)
不知假币是轻是重？
a+b+c?d+e+f > a+e?d+b > a?h > = c?h > = < b?h g?a > g:H = h:L g?h > < h?a > = > e:H > e?h = b:L > f:H = <
（3）若k>s，则第k小元素一定在序列rs+1 ～ rj中且为第 k-s小元素； 无论哪种情况，或者已经得出结果，或者将选择问题 的查找区间减少一半（如果轴值恰好是序列的中值）。 选择问题的减治思想如图5.10所示。
[ ri … rk … rs-1 ] rs [ rs+1 … … rj ] [ ri … … rs-1 ] rs [ rs+1 …rk … rj ]
二叉查找树
在二叉查找树中查找关键字值为35，95的过程：
50 30 20 40 80 90 85 20 35 30 40 50 80 90
35
32
85
88
88
32
二叉排序树的查找 BiNode * SearchBST(BiNode *root, int k) { if (root= =NULL) return NULL； else if (root->data==k) return root; else if (k<root->data) return SearchBST(root->lchild, k); else return SearchBST(root->rchild, k); }
simpler instance
or
problem’s instance
Another representation or another problem’s instance
solution
减治法的设计思想
（1）原问题的解只 存在于其中一个较小 规模的子问题中； （2）原问题的解与 其中一个较小规模的 解之间存在某种对应 关系。
2 3 4 1 · · ·· · 1 2 4 3 · · ·· · · ·4 3 · · · · ·
· · 3 4
· · · · ·
选择问题的查找过程示例（查找第4小元素）
算法5.7——选择问题 1. i=1; j=n; //设置初始查找区间 2．以r[i]为轴值对序列r[i]~r[j]进行一次 划分，得到轴值的位置s; 3. 将轴值位置s与k比较 3.1 如果k=s，则将r[s]作为结果返回； 3.2 否则，如果k<s，则j=s-1，转步骤2； 3.3 否则，i=s+1，转步骤2；