当前位置：文档之家 › 算法-第6章-变治法

算法-第6章-变治法

  • 格式：ppt
  • 大小：3.03 MB
  • 文档页数：36

下载文档原格式

  / 36

合集下载

算法设计与分析 第5章 减治策略和变治策略

算法设计与分析 第5章 减治策略和变治策略

元素的求解过程与n个元素求解过程的联系，使问题的求解直接通
过表达式来求解，从而简化问题的求解难度。
一般采用自顶向下的分析方法，但求解时往往采用自底向上的
求解过程。这也是递归的方法。
（2）减去一个常量因子
在规模中减去一个常量因子，使求解的规模成倍的缩小，从而
提高问题求解的效率。
（3）减去的规模可变。 根据求解过程的变化来确定每次规模减少的程度。 具体实例：
减治策略及变治策略
减治策略
利用一个问题给定实例的解与该问题较小实例的解之间的关系， 使原问题求解过程简化的方法称之为减治策略。 可利用递归或者非递归的方法进行问题的求解。一般分为三类： （1）减去一个常量。 也就是在求解过程中将原来的求解规模减小一个固定的常数，
比如原来有n个元素，通过减治之后，编程n-1个元素，并且建立n个
实例
将原始序列先转化成另一种存储形式，然后再进行排序以简化
排序算法，比如：
1、堆以及堆排序
2、平衡二叉树
此外，复杂问题简化以降低求解难度： 1、多项式求解：霍纳法则
2、进制之间的转换问题。
此外，还有一些具体问题的求解方法均可采用变治策略。
1、直接插入排序
2、拓扑排序
3、全排列问题
4、子集问题
变治策略
变治策略也就是将原始问题变换成更容易求解的实例，然后对变化
后的实例进行求解。
主要ቤተ መጻሕፍቲ ባይዱ如下类型：
（1）变换为同样问题的更简单的实例，也就是实例化简。
（2）变换为同样问题实例的不同形式，也成为改变表现。
（3）变换为不同问题的实例，使问题更易求解，成为问题简化。

算法设计与分析部分算法伪代码

算法设计与分析部分算法伪代码

第三章 蛮力法1.选择排序SelectionSort(A[0..n-1])for i=0 to n-2 domin=ifor j=i+1 to n-1 doif A[j]<A[min]min=jswap A[i] and A[min]2.冒泡排序BubbleSort(A[0..n-1])// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i=0 to n-2 dofor j=0 to n-2-i doif A[j+1]<A[j] swap A[j] and A[j+1]3.改进的冒泡算法ALGORITHM BubbleSortImproved( A[0,…,n –1] )// 冒泡排序算法的改进// 输入：数组A，数组中的元素属于某偏序集// 输出：按升序排列的数组Afor i ← 0 to n – 2 doflag ← Truefor j ← 0 to n – 2 – i doif A[j+1] < A[j]swap(A[j], A[j+1])flag ← False// 如果在某一轮的比较中没有交换，则flag为True，算法结束returnif flag = True4. 顺序查找算法算法 SwquentialSearch2(A[0...n],k)//顺序查找算法的实现，它用了查找键来作限位器//输入：一个n个元素的数组A和一个查找键K//输出：第一个值等于K的元素的位置，如果找不到这样的元素就返回 -1A[n]<--ki<--0while A[i]!=K doi<--i+1if i<n return iElse return -15. 蛮力字符串匹配算法 BruteForceStringMatch(T[0...n-1],P[0...m-1])//该算法实现了蛮力字符串匹配代表一段文本//输入：一个n个字符的数组T[0...n-1]// 一个m个字符的数组P[0..m-1]代表一个模式//输出：如果查找成功的话，返回文本的第一个匹配字串中第一个字符的位置， // 否则返回-1For i<--0 to n-m doj<--0While j<m and P[j]=T[i+j]doj<--i+1If j=m return ireturn -1合并排序最差Θ(nlog2n)快速排序最优Θ(nlog2n)最差Θ(n2)平均Θ(1.38nlog2n)选择排序 Θ(n2)冒泡排序 Θ(n2)插入排序最差Θ(n2)最优 Θ(n)平均 Θ(n2)第四章 分治法合并排序算法 MergeSort(A[0..n-1] )排序 // 递归调用mergesort来对数组 A[0...n-1]// 输入：一个可排序数组A[0..n-1]// 输出：非降序排列的数组A[0..n-1]if n > 1n/2 -1]copy A[0.. n/2 -1] to B[0..n/2 -1]copy A[ n/2 ..n-1] to C[0..MergeSort( B )MergeSort( C )Merge( B,C,A )两个数组合并的算法算法 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])//将两个有序数组合并成一个有序的数组和C[0...q-1]//输入：两个有序数组B[0...p-1]//输出：A[0..p+q-1]中已经有序存放了B和C中的元素 i=0,j=0,k=0;while i<p and j<q do≤C[j]if B[i]A[k]=B[i], i=i+1elseA[k]=C[j], j=j+1k=k+1if i=pcopy C[j..q-1] to A[k..p+q-1]elsecopy B[i..p-1] to A[0..p+q-1]快速排序算法QuickSort(A[l..r])// 使用快速排序法对序列或者子序列排序或者序列本身A[0..n-1]// 输入：子序列A[l..r]// 输出：非递减序列Aif l < rs ← Partition( A[l..r] )QuickSort( A[l..s-1] )QuickSort( A[s+1..r] )//s是中轴元素/基准点，是数组分区位置的标志实现分区的算法Partition( A[l..r] )// 输入：子数组A[l..r]// 输出：分裂点/基准点pivot的位置p ← A[l]i ← l; j ← r+1repeat≥ prepeat i ←i + 1until A[i]≤ prepeat j ← j – 1 until A[j]swap( A[i], A[j] )≥ juntil iswap( A[i], A[j] )swap( A[l], A[j] )return j折半查找BinarySearch( A[0..n-1], k )// 输入：已排序大小为n的序列A，待搜索对象k// 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1;While l≤rmid= (l+r)/2if k = A[mid] return midelse if k < A[mid] r=m-1else l=m+1return -1Strassen矩阵Strassen方法M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)第五章 减治法插入排序ALGORITHM InsertionSort( A[0..n-1] )// 对给定序列进行直接插入排序// 输入：大小为n的无序序列A// 输出：按非递减排列的序列Afor i ← 1 to n-1 dotemp ← A[i]j ← i-1while j ≥ 0 and A[j] > temp doA[j+1] ← A[j]j ← j –1A[j+1] ←temp深度优先查找算法 BFS（G）//实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被DFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0//记录这是第几个访问的节点标记为 unvisitedmark each vertex with 0//∈ V dofor each vertex vif v is marked with 0dfs(v)dfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countv dofor each vertexw adjacent toif w is marked with 0dfs(w)广度优先BFS(G)/实现给定图的深度优先查找遍历//输入：图G=<V,E>//输出：图G的顶点，按照被BFS遍历第一次访问到的先后次序，用连续的整数标记，将V中的每个顶点标记为0，表示还“未访问”count =0mark each vertex with 0for each vertex v∈ V dobfs(v)bfs(v)//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值//根据遇到它们的先后顺序，给它们附上相应的数字count = count + 1mark v with countinitialize queue with vwhile queue is not empty doa = front of queuefor each vertex w adjacent to a doif w is marked with 0count = count + 1mark w with countadd w to the end of the queueremove a from the front of the queue拓扑排序第六章 变治法Gauss消去法GaussElimination(A[1..n], b[1..n])// 输入：系数矩阵A及常数项 b// 输出：方程组的增广矩阵等价的上三角矩阵for i=1 to n doA[i][n+1] =b[i]for j= i+1 to n dofor k = i to n+1 do– A[i][k]*A[j][i]/A[i][i]A[j][k] = A[j][k]堆排序堆排序主要包括两个步骤：对于给定的数组构造相应的堆。

计算机算法设计与分析基础(第六章变治法)

计算机算法设计与分析基础(第六章变治法)
第 6 章 变治法
★ 变治策略
★ 预排序
★ 高斯消去法 ★ 平衡查找树（略）
★ 堆与优先队列（略）
★ 堆排序（略） ★ 霍纳法则和二进制幂 ★ 问题化简 ★ 本章习题
★ 变治策略
通用的算法设计方法，基于变换的思想
变：变换问题更容易求解 治：对变换后的问题求解
3 种主要类型
实例化简：问题求解变得更简单，如预排序
while ( i≤n-1 )
runlength←1，runvalue←A[i] // 行程长度 = 等值元素个数 while ( i+runlength≤n-1 and A[i+runlength] = runvalue )
runlength ++ // 与下一个元素相等则行程长度+1
if ( runlength > ModeFrequency ) ModeFrequency←runlength，modeValue←runvalue i←i+runlength // 跳过本行程，i 始终指向行程的第一个元素 return ( ModeValue, ModeFrequency )
需要与辅助列表中已加入的 k-1个元素比较，共 k-1 次。
最差效率：
T ( n) ( k 1) 1 ... n 1 (n2 )
k 1
n
变治法 —— 预排序（nlogn型），排序后 等值元素一定相邻 扫描统计：模式具有最多的相邻元素，需比较 n -1 次。 PresortMode_1(A[0...n-1]) // 行程算法 对数组A排序 // 排序结果 { 1, 5, 5, 5, 6, 7, 7 } i←0，ModeFrequency←0 // 最大频率，最大行程长度

第7章 减治法(《算法设计与分析(第3版)》C++版 王红梅 清华大学出版社)

第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 中。

算法设计与分析-变治法共62页文档

算法设计与分析-变治法共62页文档
算法设计与分析-变治法
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进 而变成 法律。 ——朱 尼厄斯
40、人类法律，事物有规律，这是不 容忽 的。— —爱献 生
66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭

变治法

变治法

Tbest ( n ) = 2 * log n +1 2
第六章 变治法
6.4 堆排序
HeapSort(H[1..n]) 算法 //用自底向上算法，从给定数组的元素进行堆排序 用自底向上算法， 用自底向上算法 //输入：一个可排序元素的数组 输入： 输入 一个可排序元素的数组H(1..n) //输出：一个有序数组 输出： 输出 一个有序数组H(1..n) HeapUp(H[1..n]) i=1,j=n; while i<j swap (H[i] , H[j]) HeapUp(H[i..--j]) 请自行分析堆排序的时间效率，这一点， 请自行分析堆排序的时间效率，这一点，应该可以比较 容易分析得出了！ 容易分析得出了！
2
n −1 i=1
∈ n
3
第六章 变治法
6.4 堆和堆排序
是一个完全二叉树， 定义 堆：是一个完全二叉树，并且对于每一个非叶子节点而 它的键值都大于它的子女的键值。 言，它的键值都大于它的子女的键值。 特性： 特性： 1、一个具有 个节点的堆，它的高度等于 2n+1； 个节点的堆， 等于log 、一个具有n个节点的堆 它的高度等于 2、堆的根总是包含了堆的最大元素； 包含了堆的最大元素； 、堆的根总是包含了堆的最大元素 3、堆的一个节点以及该节点的子孙也是一个堆； 一个节点以及该节点的子孙也是一个堆 、堆的一个节点以及该节点的子孙也是一个堆； 数组前n/2个位置中 4、可以用数组来实现堆：其中数组前 个位置中，存放着的 、可以用数组来实现堆：其中数组前 个位置中， 都是父亲节点。 个节点中， 都是父亲节点。后n/2个节点中，存放着所有的叶子节点； 个节点中 存放着所有的叶子节点； 5、对于任何一个父亲节点 来讲，如果它有子女的话，它的子 父亲节点i来讲 、对于任何一个父亲节点 来讲，如果它有子女的话，它的子 女应该会在位置2i和 女应该会在位置 和2i+1上面； 上

分冶法


f ( n) n 1 ( n ), d 1
d
T (n) 2T (n / 2) ( n 1)
a b 2, d 1, a b
d
d
T ( n) ( n lg n)
解递推方程得精确解： T (n) n log2 n n 1
10:39
13／42
减一技术
原问题(规模 n) (1) 子问题(n-1) (n-1)解 (n) 解 扩展解
无解
折 半 查 找
原问题解
插 入 排 序
10:39
22／42
插入排序（Insertion Sort）
任务：对 n 个元素作插入排序（规模 n） 减一策略 ——自顶向下：规模减小 ① 规模减小：规模减一，即 n-1 ② 求解：解 n-1规模子问题 ③ 扩展解：n-1规模解扩展为 n规模解 扩展方法的不同，有不同的插入排序 减一过程递归进行，直到 规模 = 1或0 为止 实现方法 —— 自底向上：规模增大 为便于实现，规模从 0 或 1 增加到 n
1, n 2 T ( n) k 2T ( n / 2) 1, n 2
10:39
7／42
分治法的一般时间效率分析 规模 n , 每次分为 a 个子问题，子问题规模相等 n/b 为简化分析, 不妨设 n = bk, k = 1, 2, 3, ...
通用分治递推式
c , n t 常量时间（基本操作次数） T ( n) aT ( n / b) f ( n), n t , a 1, b 2, c 0 f (n) : 分解时间 + 合并时间
平均 Tavg (n) 2n ln n 1.38n log2 n (n log2 n) 效率

算法设计与分析-第5章-减治法


0 T (n) T (n / 2) 1
n 1 n 1
所以，通常来说，应用减治法处理问题的效率是很高的， 一般是O(log2n)数量级。
5.2 查找问题中的减治法
5.2.1 折半查找 5.2.2 二叉查找树 5.2.3 选择问题
5.2.1
一、问题描述：
折半查找
应用折半查找方法在一个有序序列中查找值为k的记 录。若查找成功，返回记录k在序列中的位置，若查找失 败，返回失败信息。
low=1
பைடு நூலகம்
18>14
mid=3
mid=7 31>14 high=6
high=13
high=2
mid=1
7<14
low=2
mid=2
14=14
5.2.1 折半查找
三、算法设计
算法5.1——折半查找
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；
{ int data; //结点的值，假设查找集合的元素为整型
BiNode *lchild, *rchild; //指向左、右子树的指针 };
算法5.2——二叉排序树的查找
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); }

《算法分析与设计》期末复习题

一、选择题1．一个.java文件中可以有（）个public类。

A．一个B．两个C．多个D．零个2．一个算法应该是（）A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。

若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（）A．3，15，130，20，98，67B．3，15，20，130，98，67C．3，15，20，67，130，98 D．3，15，20，67，98，1305．下列关于算法的描述，正确的是（）A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出C．算法只能用流程图表示D．一个完整的算法至少有一个输入6．Java Application源程序的主类是指包含有（）方法的类。

A、main方法B、toString方法C、init方法D、actionPerfromed方法7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（）A．分治法B．减治法C．蛮力法D．变治法8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。

A、import java.awt.* ;B、import java.applet.Applet ;C、import java.io.* ;D、import java.awt.Graphics ;9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。

图中空白处理框①和②处应填入的是（）A．①sum ←sum + d B．①sum ←sum + c②c ←c + 1②c ←c + 1C．①sum ←sum + d D．①sum ←sum + c②d ←d + 1 ②d ←d + 110．报名参加冬季越野赛跑的某班5位学生的学号是：5，8，11，33，45。

西安交通大学《计算方法》课件-第六章


当f (t , y)在区域a t b c y d 中连续 ,且对变量y
满足Lipschitz条件 :对t [a, b] , y1 , y2 [c, d ] , 都有
f (t , y1 ) f (t , y2 ) L y1 y2 (6-2)
其中L为常数 则初值问题(6-1)的解存在且唯一
y(t ) f (t , y (t ))确定了函数y (t )在平面 上的方向场
yi 1 yi hf (ti , yi )是y(ti 1 )的一个近似,即由(ti , yi )到(ti 1 , yi 1 )的 直线段局部近似代替了由(ti , y(ti ))到(ti 1 , y(ti 1 ))的曲线
( 3)可以看出后退Euler方法比Euler方法的结果更好一些
显式方法:由yi直接计算yi 1的算法 隐式方法:不能直接由yi直接计算yi 1,而需要从方程中求解yi 1的算法
第6章 常微分方程数值解法 6.1 常微分方程初值问题的数值方法 6.1.2 多步法
对于微分方程 y f ( t , y( t ))
条件下是
h h2 (b a) y( ) O(h), a b y (i ) 2 i 1 2
N
若初值问题(6-1)通过某一种数值方法得到yN ,则最终误差 E ( y(b), h) y(b) - yN
称为总体截断误差 简记为 EN
第6章 常微分方程数值解法 6.1 常微分方程初值问题的数值方法 6.1.1 Euler方法及其变形
令t0 0, y0 1 yi 1 yi h( yi 2sin ti )进行计算,得到数值解.
程序演示
第6章 常微分方程数值解法
例.用Euler法求解初值问题
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 自顶向下堆构造
– 将一个节点K附加在当前堆的最后一个叶子后面 – 把K和它的双亲节点比较，K小于等于双亲则算法停止， 否则交换之。继续与上层双亲节点比较
2012-6-27
第六章 变治法
58
2
2 7 9 6 9 5 7 9 8 6 2 5 7
59
9 6 5 2
9 6 5
2012-6-27
8
8
8
7
8
6
5
9
8 2 5
8
5
6
1
6
6
1
64
2
2012-6-27
5
第六章 变治法
2
堆删除的效率
• 删除的效率取决于交换和堆的规模减1后， 树的”堆化“所需的键值比较次数 • 因为是沿树向下比较，所以它所需的键值 比较次数不可能超过堆的高度的两倍。 • 所以删除的效率 ≤ 2log2n, 属于O(logn)
min( f ( x )) max( f ( x ))
– 即为求函数的最小值，我们可以先求它的负函数的最大 值
2012-6-27
第六章 变治法
81
优化问题的化简
• 求函数的最大 值和最小值问 题。
第六章 变治法
优化问题的化简
• 最小化和最大化问题之间的关系是非常具有一般 性的：它对于定义在任何定义域D上的函数都有 效。即，我们可以对满足额外约束条件的多个变 量的函数应用这个公式。 • 求函数极值点的标准微积分过程实际上就是问题 化简：
2012-6-27
第六章 变治法
3
6.1 预排序
• 预排序是基于这么一种考虑：如果列表有序的 话，许多关于列表的问题更容易求解
– 例1 检验数组中元素的唯一性 – 例2 模式计算 – 例3 查找问题
2012-6-27
第六章 变治法
4
预排序(Presorting)
• 如果列表是有序的话，许多关于列表的问题更容易解决。
蛮力法如何做？
2012-6-27
第六章 变治法
6
预排序(Presorting)
2012-6-27
第六章 变治法
7
本节习题
6.1 -4 （P153） 求一个n元数组的最大元素和最小元素的值. a. 设计一个基于预排序的算法并确定它的效率类型。 b. 比较一下3种算法的效率：
1）蛮力算法； • 6.1 -4 （P153）
要求
– 掌握变治法的基本思想及在常见问题中的应用。
2012-6-27
第六章 变治法
2
变治法算法思想
• 变治法都是基于变换的思想
–“变”的阶段：出于这样或那样的原因，把问题的实例 变得更容易求解 –“治”的阶段：对实例进行求解
•
变治法的3种类型
–变换为同样问题的一个更简单或者更方便的实例——称 之为实例化简 –变换为同样实例的不同表现——称之为改变表现 –变换为另一个问题的实例，这种问题的算法是已知的— —称之为问题化简
不仅缺乏效率，而且需要一个连续的质数列表
2012-6-27
第六章 变治法
78
求最小公倍数
• 通过问题化简，发现lcm和gcd的积刚好把m 和n的质因数都包含了一次，故有：
lcm ( m , n )
mn gcd( m , n )
2012-6-27
第六章 变治法
79
图中的路径数量
• 计算图中两个顶点之间的路径数量问题
算法设计与分析基础 Introduction to the Design and Analysis of Algorithms
Transform and Conquer
第六章 变治法
本章教学内容
• • • • • • • 引言 6.1 6.2 6.3 6.4 6.5 6.6 变治法的思想及其3种主要类型 预排序(Presorting) 高斯消去法(Gaussian Elimination) 平衡查找树(Balanced Search Trees) 堆和堆排序(Heaps and Heapsort) 霍纳法则和二进制幂(Horner’s Rule) 问题简化(Problem Reduction)
• 分治算法编写伪代码，该算法同时求出一个n元数组 的最大元素和最小元素的值。
同时求出最 大值和最 小值，只 需要将原 数组一分 为二，再 使用相同 的方法找 出这两个 部分中的 最大值和 最小值， 然后经过 比较就可 以得到整 个问题的 最大值和 最小值。 算法 MaxMin(A[l..r],Max,Min) //该算法利用分治技术得到数组A中的最大值和最小值 //输入：数值数组A[l..r] //输出：最大值Max和最小值Min {if(r=l) Max←A[l]；Min←A[l]; //只有一个元素时 else if r－l=1 //有两个元素时 if A[l]≤A[r] Max←A[r]; Min←A[l] else Max←A[l]; Min←A[r] else //r－l>1 MaxMin(A[l,(l+r)/2],Max1,Min1); //递归解决前一部分 MaxMin(A[(l+r/)2..r],Max2,Min2); //递归解决后一部分 if Max1＜Max2 Max= Max2 //从两部分的两个最大值中选择 大值 if Min2<Min1 Min=Min2; //从两部分的两个最小值中选择小 值 }
– 从图(无向图或有向图)中的第i个顶点到第j个顶点之间， 长度为k>0的不同路径的数量等于Ak的第(i,j)个元素， 其中，A是该图的邻接矩阵。
第六章 变治法
优化问题的化简
• 最大化问题：求某些函数的最大值问题 • 最小化问题：求某些函数的最小值问题 • 现在，我们必须求某个函数的最小值，假设我们知道一 个求函数最大值的算法，我们如何利用后者呢？
i 0 第 i层 i0
第六章 变治法
h 1
h 1
i
2 n log 2 ( n 1))
2012-6-27
61
9
9 8
6 2 5
10
6
10
10
7
2
5
7
8
6 2 5
2012-6-27
9 7 8
插入操作所需的键值 比较次数≤log2n，所 以插入的效率属于 O(logn)
62
第六章 变治法
第六章 变治法
9
2012-6-27
分治算法效率的计算
2012-6-27
第六章 变治法
10
蛮力法的算法如下
算法 simpleMaxMin(A[l..r]) //用蛮力法得到数组A的最大值和最小 值 //输入：数值数组A[l..r] //输出：最大值Max和最小值Min Max=Min=A[l]; for i=l+1 to r do if A[i]>Max Max←A[i]; else if A[i]<Min Min←A[i] return Max,Min }
• 例1：检查数组中元素的唯一性(每个元素都不一样P48)
T(n)=Tsort(n)+Tscan(n) ∈ Θ(nlogn)+ Θ(n)= Θ(nlogn)
2012-6-27
第六章 变治法
5
预排序(Presorting)
模式：给定数字列表中最经常出现的一个数值，称为模式！
例2 模式计算(Computing a mode)
• 堆是一种灵巧的、部分有序的数据结构，尤其 适合用于实现优先队列，因为他对于：
– 找出一个具有最高优先级的元素（最大值） – 删除一个具有最高优先级的元素 – 添加一个元素到集合中
都能高效的实现。
2012-6-27
第六章 变治法
55
堆的概念
• 定义：一棵二叉树，树的节点中包含键（每个节点一个 键），并且满足下列条件：
2012-6-27
第六章 变治法
65
堆排序
• J.W.J.Williams发明的堆排序算法分两步走：
– 构造堆：为一个给定的数组构造一个堆 – 删除最大键：对剩下的堆应用n-1次根删除操作
• 效率：
– 构造堆：O(n) 总效率为 ( n ) ( 2 n log – 删除最大键：
2 log
2 5
3 7
4 4
5 2
6 1
10
10 7 5 2 10 5 7 1
5 6 2
1
7 2 1
57
4
2012-6-27
第六章 变治法
构造一个堆
• 自底向上堆构造
– 初始化一个包含n个节点的完全二叉树，按照给定顺序放 置键 – 从最后的双亲节点开始，到根为止，检查这些节点是否 满足要求，如果不满足，将父节点与最大孩子节点交换
– 这棵二叉树是完全二叉树 – 每个节点的键都要大于等于子女
• 性质
– n个节点的堆，高度为
log 2 n
– 树的根总是包含堆的最大元素 – 堆的一个节点以及该节点的子孙也是一个堆 – 可以用数组实现堆，即从上到下，从左到右存储堆的元 素
2012-6-27
第六章 变治法
56
下标 值
0
1 10
蛮力法：时间复杂度 t(n)=2(n-1) 算法MaxMin（分治法） 的时间复杂度为3n/2-2; simpleMaxMin的时间复 杂度为2n-2，都属于 Θ(n); 但比较一下发现， MaxMin的速度要比 simpleMaxMin的快一些!
2012-6-27
第六章 变治法
11
6.4 堆和堆排序
i 1
2012-6-27
2
n ) ( n log n )
n 1