1、2022-11-14-0算法设计与分析算法设计与分析Algorithm Design and Analysis湖南商学院计算机与电子工程学院2009.52022-11-141-目录qChapter1 Chapter1 绪论绪论qChapter2 Chapter2 算法效率分析基础算法效率分析基础 qChapter3 Chapter3 分治法分治法 qChapter4 Chapter4 减治法减治法qChapter5 Chapter5 变治法变治法qChapter6 Chapter6 时空权衡时空权衡qChapter7 Chapter7 动态规划动态规划qChapter8 Chapter8 贪心
2、法贪心法qChapter9 Chapter9 回溯与分枝限界回溯与分枝限界附：算法设计与分析实例动画集成2022-11-14-2 Chapter1 绪论 Introduction2022-11-143-绪论q什么是算法q算法的实例q算法研究的基本问题q为什么要学习算法q已有的基础数据结构返回总目录2022-11-144-什么是算法 算法是为了解决某一问题而设计的无疑义的指令序列，对于合法的输入，能在有限的时间内得出所需要的输出。problemalgorithmcomputerinputoutput2022-11-145-算法满足下列性质n输 入：有零个或多个外部量作为算法的输入。n输 出：算法
3、产生至少一个量作为输出。n确定性：组成算法的每条指令清晰、无歧义。n有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2022-11-146-算法的实例q排序q查找q最短路径q最小生成树q旅行商问题q背包问题q皇后问题q汉诺塔2022-11-147-算法研究的基本问题q如何设计算法q如何描述算法q证明算法的正确性q常用数学归纳法q算法效率q理论分析q实证分析q算法优化2022-11-148-为什么要学习算法q理论学习上的重要性q计科专业的核心课程q计科专业的基础课程q实践上的重要性2022-11-149-已有的基础数据结构q典型的问题类型q排序q查找q字符串处理q图q组合问题q几
4、何问题q数值问题2022-11-1410-已有的基础数据结构q数据结构基础q表n数组n链表n字符串q栈和队列q图q树q集合和字典2022-11-1411-思考q带锁的门走廊上n个带锁的门，从1到n一次编号，最初都关着，我们从门前经过n次，每次都从1号门开始，在第i次经过时，我们改变i的倍数的门所状态，这样，最后一次经过时，那些门开着，那些门关着？q有四个人过桥，他们都在桥的一端，17分钟让他们全部通过，必须携带手电筒，必须步行携带，每个人速度不同，甲过桥一分钟，乙过桥2分钟，丙过桥5分钟，丁要10分钟，2个人一起走需要的时间是较慢的人的时间，他们要如何走才能顺利完成？2022-11-1412-
5、本章结束，返回总目录2022-11-14-13 Chapter2 算法效率分析基础 Foundation of Algorithm Analysis2022-11-1414-算法效率分析基础q研究的主要问题q方法q时间效率的理论分析q时间效率的实证分析q最好、最坏与平均情况q增长速度q非递归与递归分析过程返回总目录2022-11-1415-研究的主要问题q算法的正确性q时间效率q空间效率q最优性2022-11-1416-方法q理论分析q实证分析2022-11-1417-2.1时间效率的理论分析q输入规模q 基本运算 为什么要用基本运算？如何找基本运算？运行时间基本运算的执行时间基本运算的执行次
6、数输入规模 T(n)copC(n)2022-11-1418-输入规模与基本操作举例基本运算输入规模的度量问题对节点或对边的访问节点数或者边数典型的图问题除法n的大小（经常转化为二进制表示，即为二进制的位数）对于给定的数n，判断是否为素数两个数相乘矩阵的维度或者元素的个数两个矩阵相乘关键字比较列表节点数目，例如 n在长度为n的列表中按关键字查找2022-11-1419-对时间效率的实证分析q选择特别的或者典型的输入q统计q实际运行时间(e.g.,milliseconds)q统计基本操作执行的次数q对统计数据进行分析2022-11-1420-最好、最坏、平均情况q很多算法的效率都取决于输入的组织q
7、最坏情况:Cworst(n)对于规模为n的输入，最大的消耗q最好情况:Cbest(n)对于规模为n的输入，最小的消耗q平均情况:Cavg(n)对于规模为n的输入，“平均”的消耗q基本操作执行的次数体现在典型输入中q不是最好最坏情况的平均q将规模n的实例划分为几种类型，同种实例所需要的基本操作执行次数一样，然后我们得到或者假设各种输入的概率分布，以推导出我们的平均次数2022-11-1421-例：顺序查找q最坏情况：nq最好情况：1q平均情况：(1+n)p/2+n(1-p)/在一个指定的数组中顺序查找指定元素/输入：A0.n-1,k/输出：指定查找元素在数组中的下标，没有返回-12022-11-
8、1422-思考q对于下面每种算法，1.指出输入规模的合理度量，2.它的基本操作，对相同规模的输入来说，3.基本操作的执行次数是否有所不同？a、计算n个数的和 b、计算n！c、找出包含n个数字的列表的最大元素 c、两个十进制正整数相乘的笔算算法 d、欧几里得法求公约数2022-11-1423-q选择手套一个抽屉里有22只手套，5双红色的，4双黄色的，2双绿色的，黑暗中挑选，最优情况下就最少选几只能找到一对匹配的手套？最坏情况下呢？q丢失的袜子 假设洗了5双不同的袜子后，发现两只找不到了，当然希望留下数量最多的完整的袜子，在最好的情况下，你会留下4双袜子，最坏情况下只有3双，假设10只袜子每只丢失
9、的概率相同，请找出最好与最坏的发生概率，平均情况下能指望有几双？2022-11-1424-增长次数 q最重要的:考虑n时，效率的乘积增长速度q例如：q当计算机的速度增加两倍时，算法运行的速度会有多快q当在两倍的输入规模下解决某问题时，时间会增加多少 T(n)copC(n)2022-11-1425-n时的重要增长值比较一下logn与n2的区别2022-11-1426-分析框架概要q算法的效率用输入规模函数进行度量q基本操作的执行次数q输入规模相同情况下，有时候需要区分最好、最差和平均效率q算法输入规模趋向无穷大时，它的运行时间函数的增长次数2022-11-1427-2.2增长率渐进表示q我们关心
10、的是算法的基本操作次数的增长次数，并把它作为算法效率分析的主要指标，为了进行比较归类，引入下列3个符号：qO(g(n):增长不会超过g(n)的一类函数f(n)q(g(n):增长率与g(n)相同的一类函数f(n)q(g(n):增长至少与g(n)相同的一类函数f(n)2022-11-1428-Big-oh成立的条件是对于足够大的nn0，存在大于0的常数c，使得以上图形满足,后面符号的两个条件相同P41例2022-11-1429-Big-omega2022-11-1430-Big-theta2022-11-1431-)()1(212nnn证明2022-11-1432-渐进增长的相关属性qf(n)O(
11、f(n)qf(n)O(g(n)if g(n)(f(n)qIf f(n)O(g(n)and g(n)O(h(n),then f(n)O(h(n)qIf f1(n)O(g1(n)and f2(n)O(g2(n),then f1(n)+f2(n)O(maxg1(n),g2(n)2022-11-1433-使用极限比较增长次数qlim T(n)/g(n)=0 order of growth of T(n)0 order of growth of T(n)=order of growth of g(n)order of growth of T(n)order of growth of g(n)Exampl
12、es:10n vs.n2 n(n+1)/2 vs.n2 n2022-11-1434-基本的渐进效率分类：1常数log n对数n线性n log nn-log-nn2平方n3立方2n指数n!阶乘2022-11-1435-qP46 1选择合适的符号来指出顺序查找算法时间效率类型q最优q最差q平均情况q作业 2、52022-11-1436-2.3非递归算法时间效率分析过程q使用变量n来描述输入规模q定义算法的基本操作q在输入规模为n的情况下，区分最坏、平均和最好情况q对基本操作执行的次数求和q使用相关公式和规则对和进行化简2022-11-1437-示例1：求最大元素2022-11-1438-示例2：元
13、素的唯一性问题2022-11-1439-示例3：矩阵的乘法2022-11-1440-示例4.十进制数转化成二进制数后的位数 2022-11-1441-q练习 p51 1 e、g 其余作业2022-11-1442-2.4递归算法的时间效率分析过程q递归算法：q函数调用自身的情况称为递归。q递归的条件：q子问题与原问题是同样的问题，且更为简单q不能无限制调用，必须有出口条件2022-11-1443-q确定一个变量来描述输入规模q确定算法的基本操作q对于相同规模的不同输入，在执行时是否有不同的基本操作次数，如果有，那么最坏、平均和最好情况应该分别考虑q建立与适当初始条件的递归联系，表示基本操作的执行
14、次数q使用反向迭代方法和初始条件解出递归式，至少要建立递归解的增长率2022-11-1444-N!定义:n!=1 2 (n-1)n for n 1 and 0!=1递归的定义 n!:F(n)=F(n-1)n for n1 and F(0)=1问题规模？基本操作？运算时间的递推式？初始条件？2022-11-1445-q实例2：汉诺塔问题q实例3：十进制正整数在二进制表示中的数字个数 递归方法 q练习p58页（1）a b、c、d、e做作业qP64页 习题2.5 （4）2022-11-1446-本章结束，返回总目录2022-11-14-47Chapter3 分治法 Divid and Conquer
15、2022-11-1448-分治法q分治法q通用分治递推式q分治法实例返回总目录2022-11-1449-分治法q通用算法设计技术q将问题的实例划分为同一个问题的几个较小实例q对这些较小的实例求解q合并这些较小问题的解，已得到原始问题的解q分治算法很适合用递归来解决2022-11-1450-分治法子问题子问题2的规模是的规模是n/2子问题子问题1的规模是的规模是n/2子问题子问题1的解的解原始问题的解原始问题的解子问题子问题2的解的解原始问题规模是原始问题规模是n2022-11-1451-通用分治递推式T(n)=aT(n/b)+f(n)其中，f(n)(nd),d 0主定理:当 a bd,T(n)
16、(nlog b a)注意：对 O 和符号来说类似的结论也是成立的。例如:T(n)=4T(n/2)+n T(n)?T(n)=4T(n/2)+n2 T(n)?T(n)=4T(n/2)+n3 T(n)?2022-11-1452-分治法实例q归并排序和快速排序q二叉树遍历q二分查找q大整数乘法qStrassen矩阵乘法q凸包问题2022-11-1453-归并排序q将数组A0.n-1 分成两个相等数组，并分别用数组B和数组C备份q分别对B,C进行排序q按照如下方法合并B,C到数组A：q重复如下步骤，直到数组中没有元素为止：n比较两个待合并数组的第一个元素n将较小的元素添加到一个新创建的数组中，被复制数组
17、中下标后移。q在未处理完的数组中，剩下的元素被复制到新创建数组的尾部。2022-11-1454-8 3 2 9 7 1 5 48 3 2 97 1 5 48 32 97 15 4832971543 82 91 74 52 3 8 91 4 5 71 2 3 4 5 7 8 92022-11-1455-两个列表归并成一个有序列表的算法2022-11-1456-归并排序算法2022-11-1457-归并排序效率分析q所有实例都有同一个效率:(n log n)q最坏情况下的键值比较次数十分接近于任何基于比较的排序算法在理论上所能达到的最少次数.当n=2k时 c(n)=nlog2n-n+1q空间需求:
18、(n)q可以不用递归(自底而上）2022-11-1458-快速排序q选择一个中轴 元素，我们这里选择第一个元素q对数组进行排序，使得小于或等于中轴的元素位于子数组的第一部分，剩下的元素都大于或等于中轴元素的值。q将中轴子与第一个子数组中的元素进行交换-此时，中轴在最后的位置q对两个子数组进行递归排序2022-11-1459-0 1 2 3 4 5 6 7 5 3 1 4 8 2 9 7 5 3 1 9 8 2 4 7 3 1 9 8 2 4 7 5 3 1 4 8 2 9 7 5 3 1 4 2 8 9 7 5 3 1 4 2 8 9 7 2 3 1 4 5 8 9 7ijl=0,r=7 5i
19、jijijijjiS=4 2 3 1 4 ijl=0,r=3 2 3 1 4 ij 2 1 3 4 ij 2 1 3 4 ij 1 2 3 4 S=1 1 l=5,r=7 3 4 i j 3 4 ij 4 l=0,r=0l=2,r=3S=2l=2,r=1l=3,r=3 8 9 7ij 8 7 9ij 8 7 9ij 7 8 9l=5,r=5 7 9 l=7,r=7S=6快速排序操作的一个例子。(a)数组的变化，其中中轴用粗体表示；(b)快速排序的递归调用树，调用的输入值是子数组的边界l和r，以及分区的分裂点位置s(a)(b)2022-11-1460-快排效率分析q最好情况:从中间拆分(n lo
20、g n)q最坏情况:已经是排好序的数组 (n2)q平均情况:无序数组(n log n)q对该算法的改进:q更好的选择中轴:三平均分区法 q当子数组足够小时改用更简单的排序方法q递归消去法n可将该算法的运行时间削减20%-25%q考虑用该种方法来对大文件（n10000)来进行内部排序2022-11-1461-二分查找对于有序数组的查找的一种高速算法 K vsA0 .Am .An-1q如果 K=Am,停止查找;q否则当K Am 时，在 Am+1.n-1中查找。2022-11-1462-二分查找效率分析q时间效率q最坏情况下递推式：Cw(n)=1+Cw(n/2),Cw(1)=1 q经过调整后：Cw(
21、n)=log2(n+1)这是非常快的，例如：Cw(106)=20q最适合用于查找已排序数组q限制：必须是一个排序数组（不是链接数组）q折半查找并不是分治法典型的特例2022-11-1463-二叉树遍历二叉树时分治法的较好的结构例1:遍历(前序,中序,后序)Algorithm Inorder(T)if T Inorder(Tleft)print(root of T)Inorder(Tright)效率:(n)2022-11-1464-二叉树遍历例 2:计算二叉树的高度 TTLR 2022-11-1465-大整数乘法两位整数相乘可以用数组表示如：a1 a2 anb1 b2 bnA=123456789
22、01357986429B=87654321284820912836(d10)d11d12 d1n(d20)d21d22 d2n(dn0)dn1dn2 dnn效率：O(n2)2022-11-1466-大整数乘法两位数两位数A=2135 和和B=4014可以这样表示：可以这样表示：将每个数字从中间一分为二将每个数字从中间一分为二它们的积可以用这个公式计算：它们的积可以用这个公式计算：A B=A1 B110n +(A1 B2+A2 B1)10n/2+A2 B2 A=(21102+35),B=(40 102+14)A B=(21 102+35)(40 102+14)=21 40 104 +(21 14
23、+35 40)102+35 14效率效率：M(n)=4M(n/2),M(1)=1 M(n)=n2 2022-11-1467-大整数乘法(A1 B2+A2 B1)=(A1+A2)(B1+B2)-A1 B1-A2 B2A B=A1 B110n +(A1 B2+A2 B1)10n/2+A2 B2可以这样做减少乘法：A B=A1 B1 +(A1 B2+A2 B1)+A2 B2因为上述中只有三个乘法所以乘法次数M(n)的递推式是：当n1时 M(n)=3M(n/2),M(1)=1 当n=2k时 M(2k)=3M(2 k-1)=.=3k 因为：k=log2n M(n)=nlog23=n1.5852022-1
24、1-1468-大整数乘法 A=21 35 B=40 14 A1A2B1B2A B=21*35+（21*14+35*40）+35*14（21*14+35*40）=（21+35）*（40+24）-21*35-35*14例如：计算计算 2135 4014 2022-11-1469-A和B的乘积矩阵C中的元素Ci,j定义为:nkjkBkiAjiC1若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3)u传统方法：O(n3)2022-11-1470-使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小
25、相等的子矩阵。由此可将方程C=AB重写为：u传统方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC由此可见，单纯采用分治法，没有改进2022-11-1471-为了降低时间复杂度，必须减少乘法的次数。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122
26、126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC2022-11-1472-复杂度分析复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进较大的改进22)2/(7)1()(nnnTOnT2022-11-1473-u传统方法：O(n3)u分治法:O(n2.81)u更快的方法?Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进
27、了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。2022-11-1474-凸包问题（相关定义p84）q什么是凸集合？对于平面的一个点集合（有限或无限），如果以集合中任意两点p和q为端点的线段都属于该集合，则称集合为凸的。q定义：凸包：一个点集合s的凸包是包含s的最小凸集合。q定理任意包含n2个点（不共线的点）的集合s的凸包是以s中的某些点为顶点的多边形（如果所有的的店都位于一条直线上，多边形退化为一条线段，但它的2个端点让人包含在s中）2022-11-1475-q假设点按照x轴排序q找出最左和 最右的极点 (leftmos
28、t and rightmost)q递归的求凸包的上包:q发现点 Pmax 是离直线 P1P2直线最远的点q计算在直线 P1Pmax左侧的上包q计算在直线 PmaxP2左侧的上包q递归的计算下包2022-11-1476-p1p2凸包问题1、最左边的点p1 1和最右边的p2 2一定是该集合凸包顶点。2022-11-1477-p1p2凸包问题2、找到上包的顶点，它是距离直线最远的点，如果用两条连接线的话，这个确定了最大的三角形pmaxp1p2。pmax2022-11-1478-p1p2凸包问题p1max3、找出距离p1pmax左边最远的点p3。如此进行下去，直到对应的包左边没有点p32022-11-
29、1479-p1p2凸包问题p1maxp2max4、找出PmaxP2左边最远的点p4。，按照改方法进行，直到左边没有点p42022-11-1480-p1p2凸包问题p1maxp2max连接所得到的这些点2022-11-1481-p1p2凸包问题p1maxp2max利用上述求上包的方法求出下包。2022-11-1482-如何判断离线段p1p2最远的点？假设p3为任意点X1 y1 1X2 y2 1X3 y3 1该行列式的绝对值表示以这3点构成的三角形面积，值为正，表示该点位于直线先左侧2022-11-1483-本章结束，返回总目录2022-11-14-84Chapter 4 减治法Decrease-
30、and-Conquer2022-11-1485-减治法q减治法q减治法的类型q减治法与其它方法的区别返回总目录2022-11-1486-减治法q基本思路：q将原问题的实例转化为规模较小的实例q对规模较小的实例的求解q将较小的实例的解扩展到原实例q能够使用自顶向下或者是自底向上q经常被称为归纳法或者是增量法2022-11-1487-减治法的类型q减去一个常量（一般是）q插入排序 q图形遍历算法（深度优先查找和广度优先查找）q拓扑排序q减去一个常量因子（一般是一半）q折半查找和二分法q矩阵的幂运算q俄式乘法q减可变规模q欧几里得问题q部分选择2022-11-1488-减去常量q在这种减治法中，每次
31、减去一个常量因子1。q例如：q插入排序 q图形遍历算法（深度优先查找和广度优先查找）q拓扑排序2022-11-1489-插入排序q对数组A0.n-1，数组A0.n-2已经排好序，然后在数组中A0.n-2中找一个合适的位置将An-1插入q经常使用自底向上（非递归）q例如:对 6,4,1,8,5进行排序 6|4 1 8 5 4 6|1 8 5 1 4 6|8 5 1 4 6 8|5 1 4 5 6 82022-11-1490-插入排序 2022-11-1491-插入排序8945689029341745比较45与89的大小2022-11-1492-插入排序894568902934174545 68
32、89后移一个位置2022-11-1496-插入排序8968902934174568比较45与68的大小2022-11-1497-插入排序8968902934174568将68插入到45后面2022-11-1498-插入排序89902934174568比较90与前面的数的大小2022-11-1499-插入排序89902934174568 89902022-11-14100-插入排序89902934174568 1 and m if n=1 n 2n 1 22022-11-14162-俄式乘法Compute 20*26 n m 20 26 10 52 5 104 104 2 208 +1 416
33、416 Note:把所有n列中包含基数的m列元素进行相加2022-11-14163-约瑟夫斯问题q问题的提出2022-11-14164-减可变因子在这种减治法当中，每次迭代都减小规模不同的 因子。例如:q欧几里得算法q查找问题计算中值和选择问题2022-11-14165-欧几里得求最大公约数算法欧几里得算法重复使用公式：gcd(m,n)=gcd(n,m mod n)例如:gcd(80,44)=gcd(44,36)=gcd(36,8)=gcd(8,4)余数为0结束，取次数被除数作为最大公约数T(n)O(log n)2022-11-14166-查找问题q在n个数中查找第k小的元素k=1 or k=
34、nq中值:k=n/2 例如:4,1,10,9,7,12,8,2,15 中值=?q中值是数理统计中用来求平均值的一个很好的方法q事实上，它比其他类似合并排序的算法要优秀很多。2022-11-14167-a0 a1a2a3aj-1an-1如果有一个数组an，现要求出其中第k小元素a0 a1a2a3aian-1A:以数组第一个元素为标准，利用快速排序得到此数值在数组中的位置是第j个K=j继续步骤Aaj-1即为所求求第K小元素2022-11-14168-411097128215K=9/2=5中值问题2022-11-14169-411097128215214971281015K=9/2=5中值问题202
35、2-11-14170-411097128215214971281015S=35,处理列表的右边部分。K=9/2=5中值问题2022-11-14171-411097128215214971281015S=35,处理列表的右边部分。971281015K=9/2=5中值问题2022-11-14172-411097128215214971281015S=35,处理列表的右边部分。971281015K=9/2=5879121015中值问题2022-11-14173-411097128215214971281015S=35,处理列表的左边部分。中值问题2022-11-14174-4110971282152
36、14971281015S=35,处理列表的左边部分。8中值问题2022-11-14175-411097128215214971281015S=35,处理列表的左边部分。87中值问题2022-11-14176-411097128215214971281015S=35,处理列表的左边部分。87中值问题2022-11-14177-411097128215214971281015S=35,处理列表的左边部分。8778中值问题2022-11-14178-411097128215214971281015S=35,处理列表的左边部分。8778S=5=k,可以停止了。中值问题2022-11-14179-粘游戏
37、有一堆石子有n粒，两个人轮流从中拿取1m个石子，最后拿完的为胜者。如果两个人都使用了正确的方法，谁可能获胜，第一个人或第二个？N=0是败局1=n=m是胜局N=m+1是败局m+2=n=2m+1是胜局N=2m+2是败局什么情况下是必胜或者必败？如何选择策略只要让对方得到m+1的倍数就必胜，只需每次拿走n mod m+1即可2022-11-14180-N=10,m=4 的粘游戏的图0512341067892022-11-14181-q一般粘游戏：有i堆棋子，每堆数量n1,n2到ni,可以从任意一堆拿走任意个棋子，甚至可以把一堆拿光，最后一个还能走的是赢家？q一个非常妙的解法将每堆棋子数用2进制数表示
38、，计算2进制数位和并忽略进位，如何某人面临的二进制和 中只有有1存在，就是一个胜局，如果全为0，就是必输局2022-11-14182-减治与其它方法的区别考虑一个幂计算的实例：an q穷举：an=a*a*aq分治:an=an/2*an/2=q减一:an=an-1*a=q减一个常量因子:a5=a2*a2*a12022-11-14183-q生成n=4个的格雷码qP142 2 3,4qP147 32022-11-14184-本章结束，返回总目录2022-11-14-185变治法Transform-and-Conquer2022-11-14186-变治法q本章所讨论的这组技术，都是基于变换的思想q变换
39、为同样问题实例的一个更简单或者是更方便的实例(实例化简)q变换为同样问题的不同表现(改变表现)q变换为另外一个问题的实例，这种问题的算法是已知的(问题化简)2022-11-14187-变治法实例q实例化简q改变表现q问题化简返回总目录2022-11-14188-实例化简 预排序q将实例变换为同样问题实例的一个更简单或者是更方便的实例q预排序q如果列表有序，许多涉及到列表的问题就更加容易求解q查找问题q计算中值(选择问题)q检查元素的唯一性(元素唯一性)q其它：q拓扑排序解决了许多关于无环有向图的问题。q预排序用于解决几何问题.2022-11-14189-排序能够有多快?q依赖于所选用的排序算法
40、的效率。q理论：没有一种基于比较的普通排序算法，在最坏的情况下效率能够超过log2 n!n log2 n q注意:nlog2 n次比较也可以对含有n个元素的数组进行排序（合并排序）2022-11-14190-基于预排序的查找q问题:在数组 A0.n-1中查找给定的K值 q基于预排序的算法:q第一步：对数组进行排序q第二步：应用折半查找 q时间效率:(nlog n)+O(log n)=(nlog n)q为 什 么 我 们 要 对 字 典、电 话 簿 等 东 西 排 序?2022-11-14191-检查数组元素的唯一性q基于预排序的算法q第一步:对数组进行排序(例如：归并排序)q第二步:检查元素之
41、间的连续性q时间效率:(nlogn)+O(n)=(nlogn)q蛮力法q比较数组中所有的元素q时间效率:O(n2)q另外一种算法?q哈希2022-11-14192-改变表现高斯消去法q思路:把n个线性方程构成的n元联立方程组变换为一个等价的方程组q变形:把n个线性方程构成的n元联立方程组变换为一个上三角系数矩阵q从最后一个方程，可以立即求出最后一个方程的的解，然后代入倒数第二个，就可以求出倒数第二个方程的解，依次类推，从而求出第一个方程的解 a11x1+a12x2+a1nxn=b1 a1,1x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 a22x2+a2nxn=b
42、2 an1x1+an2x2 +annxn=bn annxn=bn 2022-11-14193-高斯消去法经过一系列的初等变换可以从一个具有任意系数矩阵的方程组推导出一个具有上三角系数矩阵的等价方程组（不改变系数矩阵的答案):forfor i 1 to n-1 dodo 交换方程组中两个方程的位置。把一个方程替换为它的非零倍。把一个方程替换为他和另一个方程倍数之间的和或差2022-11-14194-高斯消去法S o l v e 2 x1-4 x2 +x3 =6 3x1-x2 +x3=11 x1+x2 -x3=-3 高斯消去法 2 -4 1 6 2 -4 1 6 3 -1 1 11 row2 (3
43、/2)*row1 0 5 -1/2 2 1 1 -1 -3 row3 (1/2)*row1 0 3 -3/2 -6 row3(3/5)*row2 2 -4 1 6 0 5 -1/2 2 0 0 -6/5-36/5 回代 x3=(-36/5)/(-6/5)=6 x2=(2+(1/2)*6)/5=1 x1=(6 6+4*1)/2=22022-11-14195-高斯消去法的伪代码和时间效率第一步:上三角矩阵的简化for i 1 to n-1 do for j i+1 to n do for k i to n+1 do Aj,k Aj,k-Ai,k*Aj,i/Ai,i /improve!第二步:回代f
44、or j n downto 1 do t 0 for k j+1 to n do t t+Aj,k*xk xj (Aj,n+1-t)/Aj,j 效率:(n3)+(n2)=(n3)2022-11-14196-查找问题q问题:给定一组数据S，和一个元素K，如果S中包含K，则要找到K在S中的位置，在查找的过程中要考虑以下问题：q文件大小(i内部文件 vs.外部文件)q动态数据(静态 vs.动态)q字典操作(动态数据):q查找q插入q删除2022-11-14197-查找算法分类q列表查询q顺序查找q折半查找q插值查找q查找树 q二分查找树q平衡查找树:AVL trees,red-black trees
45、q多路查找树:2-3 trees,2-3-4 trees,B treesq哈希q开散列(分离链)q闭散列(开式寻址)2022-11-14198-二叉查找树KK2022-11-14199-q二叉平衡s树（平衡查找树）每棵树的平衡因子定义为该节点的左子树和右子树的高度差，这个平衡因子只能为0，1或-1。（空树的高度定义为-1）2022-11-14200-平衡查找树（AVL）在最坏情况下，平衡查找树的效率是线性的。从而退化到了严重不平衡的情。下面是两套解决方案:q 把一棵不平衡的二叉树转换为一棵平衡的二叉树q AVL treesq red-black treesq 允许一棵查找树的单个节点不止包含一
46、个元素q 2-3 treesq 2-3-4 treesq B-trees2022-11-14201-平衡树（AVL树）一棵 AVL tree 是一棵二叉查找树，其中每个结点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么为0，要么为+1.要么为-1（一棵空树的高度定义为-1）52012472(a)10181010-100520472(b)10280010-102022-11-14202-.非平衡二叉树的平衡处理可以对非平衡二叉树进行平衡处理，使其变成一棵平衡二叉树。下面将分四种情况讨论平衡处理。2022-11-14203-（1）LL型型 的处理的处理(左左型左左型)如图所示，在C
47、的左孩子B上扦入一个左孩子结点A，成为不平衡的二叉树序树。这时的平衡处理为：将C顺时针旋转，成为B的右子树，待扦入结点A作为B的左子树。平衡外理 1 A B C 0 2 C B A 0 0 0 LL 型平衡外理 2022-11-14204-2）LR型的处理型的处理(左右型左右型)如图所示，在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将B变到A与C 之间，使之成为LL型，然后按第(1)种情形LL型处理。0-1 C A B 2 0 1 C A B 2 B 0 0 C A 0 平衡处理 旋转 LR 型平衡处理 2022-11-14205-
48、ABCEFDABCEFDABCEFD以左子树的右子树根节点E为中心，逆时钟旋转成ll型仍然以E为中心，顺时钟旋转LR型的普通形状的转化GGG2022-11-14206-3）RR型的处理型的处理(右右型右右型)如图所示，在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待扦入结点C成为B的右子树。平衡处理-1 C B A 0-2 C B A 0 0 0 RR型平衡处理 2022-11-14207-4）RL型的处理型的处理(右左型右左型)如 图所示，在A的右孩子C上扦入一个左孩
49、子B，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将B变到A与C之间，使之成为RR型，然后按第(3)种情形RR型处理。平衡处理 C B A 0 0 0 RL 型平衡处理-1-2 C B A B 0 1-2 A 旋转 C 2022-11-14208-以右子树的左子树根节点D为中心，顺时钟旋转成RR型仍然以D为中心，逆顺时钟旋转RL型的普通形状的转化ABCDEFABCDEFABCEDFGGG2022-11-14209-例，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立
50、的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图。(a)插入插入 4(b)插入插入 5(c)插入插入 7 RR 型型 4 0 4 5 0-1 7 4 5-2-1 0 0 0 4 5 7 0 2022-11-14210-LL 型型 (d)插入插入 2(e)插入插入 1 4 2 5 7 1 0 0 0 0 0 4 2 5 7 1 0 0 1 2 2 4 2 5 7 0 0 1 1 -1 5 2 1 4 3 7 2 0 1 0 0 5 2 1 4 3 7-1 0 0 0 0 0 LR 型型 (f)插入插入 3 2022-11-14211-5 2 1 4 3
