算法分析与设计多媒体课件-

算法设计与分析

AlgorithmDesignandAnalysis湖南商学院计算机与电子工程学院2009.52022/10/300-算法设计与分析

AlgorithmDesignand目录Chapter1绪论Chapter2算法效率分析基础

Chapter3分治法Chapter4减治法Chapter5变治法Chapter6时空权衡Chapter7动态规划Chapter8贪心法Chapter9回溯与分枝限界附：算法设计与分析实例动画集成2022/10/301-目录Chapter6时空权衡附：算法设计与分析实例动画集

Chapter1绪论

Introduction

2022/10/302-Chapter1绪论

绪论什么是算法算法的实例算法研究的基本问题为什么要学习算法已有的基础—数据结构返回总目录2022/10/303-绪论什么是算法返回总目录2022/10/233-什么是算法算法是为了解决某一问题而设计的无疑义的指令序列，对于合法的输入，能在有限的时间内得出所需要的输出。problemalgorithmcomputerinputoutput2022/10/304-什么是算法算法是为了解决某一问题而设计的无疑算法满足下列性质输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。2022/10/305-算法满足下列性质输入：有零个或多个外部量作为算法的输入。算法的实例排序查找最短路径最小生成树旅行商问题背包问题皇后问题汉诺塔2022/10/306-算法的实例排序2022/10/236-算法研究的基本问题如何设计算法如何描述算法证明算法的正确性常用数学归纳法算法效率理论分析实证分析算法优化2022/10/307-算法研究的基本问题如何设计算法2022/10/237-为什么要学习算法理论学习上的重要性计科专业的核心课程计科专业的基础课程实践上的重要性2022/10/308-为什么要学习算法理论学习上的重要性2022/10/238-已有的基础—数据结构典型的问题类型排序查找字符串处理图组合问题几何问题数值问题2022/10/309-已有的基础—数据结构典型的问题类型2022/10/239-已有的基础—数据结构数据结构基础表数组链表字符串栈和队列图树集合和字典2022/10/3010-已有的基础—数据结构数据结构基础2022/10/2310-思考带锁的门走廊上n个带锁的门，从1到n一次编号，最初都关着，我们从门前经过n次，每次都从1号门开始，在第i次经过时，我们改变i的倍数的门所状态，这样，最后一次经过时，那些门开着，那些门关着？有四个人过桥，他们都在桥的一端，17分钟让他们全部通过，必须携带手电筒，必须步行携带，每个人速度不同，甲过桥一分钟，乙过桥2分钟，丙过桥5分钟，丁要10分钟，2个人一起走需要的时间是较慢的人的时间，他们要如何走才能顺利完成？2022/10/3011-思考带锁的门2022/10/2311-本章结束，返回总目录2022/10/3012-本章结束，返回总目录2022/10/2312-

Chapter2算法效率分析基础

FoundationofAlgorithmAnalysis

2022/10/3013-Chapter2算法效率分析基础

算法效率分析基础研究的主要问题方法时间效率的理论分析时间效率的实证分析最好、最坏与平均情况增长速度非递归与递归分析过程返回总目录2022/10/3014-算法效率分析基础研究的主要问题返回总目录2022/10/23研究的主要问题算法的正确性时间效率空间效率最优性2022/10/3015-研究的主要问题算法的正确性2022/10/2315-方法理论分析实证分析2022/10/3016-方法理论分析2022/10/2316-2.1时间效率的理论分析输入规模基本运算为什么要用基本运算？如何找基本运算？运行时间基本运算的执行时间基本运算的执行次数输入规模

T(n)≈

copC(n)2022/10/3017-2.1时间效率的理论分析输入规模运行时间基本运算的执行时间基输入规模与基本操作举例基本运算输入规模的度量问题对节点或对边的访问节点数或者边数典型的图问题除法n的大小（经常转化为二进制表示，即为二进制的位数）对于给定的数n，判断是否为素数两个数相乘矩阵的维度或者元素的个数两个矩阵相乘关键字比较列表节点数目，例如n在长度为n的列表中按关键字查找2022/10/3018-输入规模与基本操作举例基本运算输入规模的度量问题对节点或对边对时间效率的实证分析选择特别的或者典型的输入统计实际运行时间(e.g.,milliseconds)统计基本操作执行的次数对统计数据进行分析2022/10/3019-对时间效率的实证分析选择特别的或者典型的输入2022/10/最好、最坏、平均情况很多算法的效率都取决于输入的组织最坏情况:Cworst(n)–对于规模为n的输入，最大的消耗最好情况:Cbest(n)–对于规模为n的输入，最小的消耗平均情况:Cavg(n)–对于规模为n的输入，“平均”的消耗基本操作执行的次数体现在典型输入中不是最好最坏情况的平均将规模n的实例划分为几种类型，同种实例所需要的基本操作执行次数一样，然后我们得到或者假设各种输入的概率分布，以推导出我们的平均次数2022/10/3020-最好、最坏、平均情况很多算法的效率都取决于输入的组织2022例：顺序查找最坏情况：n最好情况：1平均情况：(1+n)p/2+n(1-p)//在一个指定的数组中顺序查找指定元素//输入：A[0..n-1],k//输出：指定查找元素在数组中的下标，没有返回-12022/10/3021-例：顺序查找最坏情况：n//在一个指定的数组中顺序查找指定元思考对于下面每种算法，1.指出输入规模的合理度量，2.它的基本操作，对相同规模的输入来说，3.基本操作的执行次数是否有所不同？

a、计算n个数的和b、计算n！

c、找出包含n个数字的列表的最大元素

c、两个十进制正整数相乘的笔算算法

d、欧几里得法求公约数2022/10/3022-思考对于下面每种算法，1.指出输入规模的合理度量，2.它的基选择手套一个抽屉里有22只手套，5双红色的，4双黄色的，2双绿色的，黑暗中挑选，最优情况下就最少选几只能找到一对匹配的手套？最坏情况下呢？丢失的袜子假设洗了5双不同的袜子后，发现两只找不到了，当然希望留下数量最多的完整的袜子，在最好的情况下，你会留下4双袜子，最坏情况下只有3双，假设10只袜子每只丢失的概率相同，请找出最好与最坏的发生概率，平均情况下能指望有几双？2022/10/3023-选择手套2022/10/2323-增长次数最重要的:考虑n→∞时，效率的乘积增长速度例如：当计算机的速度增加两倍时，算法运行的速度会有多快当在两倍的输入规模下解决某问题时，时间会增加多少

T(n)≈

copC(n)2022/10/3024-增长次数最重要的:考虑n→∞时，效率的乘积增长速度T(n时的重要增长值比较一下logn与n2的区别2022/10/3025-n时的重要增长值比较一下logn与n2的区别2022/1分析框架概要算法的效率用输入规模函数进行度量基本操作的执行次数输入规模相同情况下，有时候需要区分最好、最差和平均效率算法输入规模趋向无穷大时，它的运行时间函数的增长次数2022/10/3026-分析框架概要算法的效率用输入规模函数进行度量2022/10/2.2增长率渐进表示我们关心的是算法的基本操作次数的增长次数，并把它作为算法效率分析的主要指标，为了进行比较归类，引入下列3个符号：O(g(n)):增长不会超过g(n)的一类函数f(n)Θ(g(n)):增长率与g(n)相同的一类函数f(n)Ω(g(n)):增长至少与g(n)相同的一类函数f(n)2022/10/3027-2.2增长率渐进表示我们关心的是算法的基本操作次数的增长次数Big-oh成立的条件是对于足够大的n>n0，存在大于0的常数c，使得以上图形满足,后面符号的两个条件相同P41例2022/10/3028-Big-oh成立的条件是对于足够大的n>n0，存在大于0的常Big-omega2022/10/3029-Big-omega2022/10/2329-Big-theta2022/10/3030-Big-theta2022/10/2330-证明2022/10/3031-证明2022/10/2331-渐进增长的相关属性f(n)O(f(n))f(n)O(g(n))ifg(n)(f(n))Iff(n)O(g(n))andg(n)O(h(n)),thenf(n)O(h(n))Iff1(n)O(g1(n))andf2(n)O(g2(n)),then f1(n)+f2(n)O(max{g1(n),g2(n)})

2022/10/3032-渐进增长的相关属性f(n)O(f(n))2022/10使用极限比较增长次数limT(n)/g(n)=0

orderofgrowthofT(n)<orderofgrowthofg(n)

c>0orderofgrowthofT(n)=orderofgrowthofg(n)

∞

orderofgrowthofT(n)>orderofgrowthofg(n)

Examples:

10nvs.n2

n(n+1)/2vs.n2

n→∞2022/10/3033-使用极限比较增长次数limT(n)/g(n)=基本的渐进效率分类：1常数logn对数n线性nlognn-log-nn2平方n3立方2n指数n!阶乘2022/10/3034-基本的渐进效率分类：1常数logn对数n线性nlognP461选择合适的符号来指出顺序查找算法时间效率类型最优最差平均情况作业2、52022/10/3035-P4612022/10/2335-2.3非递归算法时间效率分析过程使用变量n来描述输入规模定义算法的基本操作在输入规模为n的情况下，区分最坏、平均和最好情况对基本操作执行的次数求和使用相关公式和规则对和进行化简2022/10/3036-2.3非递归算法时间效率分析过程使用变量n来描述输入规模20示例1：求最大元素2022/10/3037-示例1：求最大元素2022/10/2337-示例2：元素的唯一性问题2022/10/3038-示例2：元素的唯一性问题2022/10/2338-示例3：矩阵的乘法2022/10/3039-示例3：矩阵的乘法2022/10/2339-示例4.十进制数转化成二进制数后的位数2022/10/3040-示例4.十进制数转化成二进制数后的位数2022/10/2练习p511e、g其余作业2022/10/3041-练习p511e、g其余作业2022/10/232.4递归算法的时间效率分析过程递归算法：函数调用自身的情况称为递归。递归的条件：子问题与原问题是同样的问题，且更为简单不能无限制调用，必须有出口条件2022/10/3042-2.4递归算法的时间效率分析过程递归算法：2022/10/2确定一个变量来描述输入规模确定算法的基本操作对于相同规模的不同输入，在执行时是否有不同的基本操作次数，如果有，那么最坏、平均和最好情况应该分别考虑建立与适当初始条件的递归联系，表示基本操作的执行次数使用反向迭代方法和初始条件解出递归式，至少要建立递归解的增长率

2022/10/3043-确定一个变量来描述输入规模2022/10/2343-N!定义:n!=12…(n-1)

nforn≥

1and0!=1递归的定义n!:F(n)=F(n-1)

nforn≥1andF(0)=1问题规模？基本操作？运算时间的递推式？初始条件？2022/10/3044-N!定义:n!=12…(n-1)实例2：汉诺塔问题实例3：十进制正整数在二进制表示中的数字个数

递归方法练习p58页（1）ab、c、d、e做作业P64页习题2.5（4）2022/10/3045-实例2：2022/10/2345-本章结束，返回总目录2022/10/3046-本章结束，返回总目录2022/10/2346-Chapter3分治法

DividandConquer2022/10/3047-Chapter3分治法

分治法分治法通用分治递推式分治法实例返回总目录2022/10/3048-分治法分治法返回总目录2022/10/2348-分治法通用算法设计技术将问题的实例划分为同一个问题的几个较小实例对这些较小的实例求解合并这些较小问题的解，已得到原始问题的解分治算法很适合用递归来解决2022/10/3049-分治法通用算法设计技术2022/10/2349-分治法子问题2的规模是n/2子问题1的规模是n/2子问题1的解原始问题的解子问题2的解原始问题规模是n2022/10/3050-分治法子问题2的规模是n/2子问题1的规模是n/2子问题1的通用分治递推式T(n)=aT(n/b)+f(n)

其中，

f(n)

(nd),d0主定理:当a<bd,T(n)

(nd)

当a=bd,T(n)

(ndlogn)

当a>bd,T(n)

(nlogba)

注意：对O和符号来说类似的结论也是成立的。例如:T(n)=4T(n/2)+nT(n)?

T(n)=4T(n/2)+n2T(n)?

T(n)=4T(n/2)+n3T(n)?2022/10/3051-通用分治递推式T(n)=aT(n/b)+f(n)分治法实例归并排序和快速排序二叉树遍历二分查找大整数乘法Strassen矩阵乘法凸包问题2022/10/3052-分治法实例归并排序和快速排序2022/10/2352-归并排序将数组A[0..n-1]分成两个相等数组，并分别用数组B和数组C备份分别对B,C进行排序按照如下方法合并B,C到数组A：重复如下步骤，直到数组中没有元素为止：比较两个待合并数组的第一个元素将较小的元素添加到一个新创建的数组中，被复制数组中下标后移。在未处理完的数组中，剩下的元素被复制到新创建数组的尾部。2022/10/3053-归并排序将数组A[0..n-1]分成两个相等数组，并分别用832971548329715483297154832971543829174523891457123457892022/10/3054-832971548两个列表归并成一个有序列表的算法2022/10/3055-两个列表归并成一个有序列表的算法2022/10/2355-归并排序算法2022/10/3056-归并排序算法2022/10/2356-归并排序效率分析所有实例都有同一个效率:Θ(nlogn)最坏情况下的键值比较次数十分接近于任何基于比较的排序算法在理论上所能达到的最少次数.

当n=2k时c(n)=nlog2n-n+1空间需求:Θ(n)可以不用递归(自底而上）2022/10/3057-归并排序效率分析所有实例都有同一个效率:Θ(nlogn快速排序选择一个中轴

元素，我们这里选择第一个元素对数组进行排序，使得小于或等于中轴的元素位于子数组的第一部分，剩下的元素都大于或等于中轴元素的值。将中轴子与第一个子数组中的元素进行交换---此时，中轴在最后的位置对两个子数组进行递归排序2022/10/3058-快速排序选择一个中轴元素，我们这里选择第一个元素2022/

01234567

5

3148297

53198247

3198247

53148297

53142897

53142897

23145897ijl=0,r=7

5ijijijijjiS=4

2314ijl=0,r=3

2314ij

2134ij

2134ij

1234S=1

1l=5,r=7

34ij

34ij

4l=0,r=0l=2,r=3S=2l=2,r=1l=3,r=3

897ij

879ij

879ij

789l=5,r=5

7

9l=7,r=7S=6快速排序操作的一个例子。(a)数组的变化，其中中轴用粗体表示；(b)快速排序的递归调用树，调用的输入值是子数组的边界l和r，以及分区的分裂点位置s(a)(b)2022/10/3059-01234快排效率分析最好情况:从中间拆分—Θ(nlogn)最坏情况:已经是排好序的数组—Θ(n2)平均情况:无序数组—Θ(nlogn)对该算法的改进:更好的选择中轴:三平均分区法当子数组足够小时改用更简单的排序方法递归消去法可将该算法的运行时间削减20%--25%考虑用该种方法来对大文件（n≥10000)来进行内部排序2022/10/3060-快排效率分析最好情况:从中间拆分—Θ(nlogn)二分查找对于有序数组的查找的一种高速算法

K vs A[0]...A[m]...A[n-1]如果K=A[m],停止查找;否则当K<A[m]时，用同样的方法在A[0..m-1]进行查找；当K>A[m]时，在A[m+1..n-1]中查找。

2022/10/3061-二分查找对于有序数组的查找的一种高速算法2022/10/23二分查找效率分析时间效率最坏情况下递推式：Cw(n)=1+Cw(n/2),Cw(1)=1

经过调整后：Cw(n)=

log2(n+1)

这是非常快的，例如：Cw(106)=20最适合用于查找已排序数组限制：必须是一个排序数组（不是链接数组）折半查找并不是分治法典型的特例2022/10/3062-二分查找效率分析时间效率2022/10/2362-二叉树遍历二叉树时分治法的较好的结构例1:遍历(前序,中序,后序)AlgorithmInorder(T)ifT

Inorder(Tleft)print(rootofT)

Inorder(Tright)效率:Θ(n)2022/10/3063-二叉树遍历二叉树时分治法的较好的结构2022/10/2363二叉树遍历例2:计算二叉树的高度

h(T)=max{h(TL),h(TR)}+1ifT

并且h()=-1效率:Θ(n)

2022/10/3064-二叉树遍历例2:计算二叉树的高度h(T)=max{h大整数乘法两位整数相乘可以用数组表示如：a1a2…an

b1b2…bnA=12345678901357986429B=87654321284820912836(d10)

d11d12…d1n(d20)

d21d22…d2n………………(dn0)

dn1dn2…dnn效率：O(n2)2022/10/3065-大整数乘法两位整数相乘可以用数组表示如：a1a2…大整数乘法两位数A=2135和B=4014可以这样表示：将每个数字从中间一分为二它们的积可以用这个公式计算：AB=A1B1·10n

+(A1B2+A2B1)·10n/2+A2B2

A=(21·102+35),B=(40·102+14)

AB=(21·102+35)(40·102+14)

=2140·104+(2114+3540)·102+3514效率：

M(n)=4M(n/2),M(1)=1M(n)=

n22022/10/3066-大整数乘法两位数A=2135和B=4014可以这样大整数乘法(A1B2+A2B1)=(A1+A2)(B1+B2)-A1B1-A2B2AB=A1B1·10n

+(A1B2+A2B1)·10n/2+A2B2可以这样做减少乘法：AB=A1B1

+(A1B2+A2B1)

+A2B2因为上述中只有三个乘法所以乘法次数M(n)的递推式是：当n>1时M(n)=3M(n/2),M(1)=1当n=2k时M(2k)=3M(2k-1)=….=3k因为：k=log2nM(n)=nlog23=n1.5852022/10/3067-大整数乘法(A1B2+A2B1)=(A1大整数乘法A=21

35B=40

14

A1A2B1B2AB=21*35+（21*14+35*40）+35*14（21*14+35*40）=（21+35）*（40+24）-21*35-35*14例如：计算213540142022/10/3068-大整数乘法A=2135Strassen矩阵乘法A和B的乘积矩阵C中的元素C[i,j]定义为:

若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3)传统方法：O(n3)2022/10/3069-Strassen矩阵乘法A和B的乘积矩阵C中的元素C[i,jStrassen矩阵乘法使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：传统方法：O(n3)分治法:由此可得：由此可见，单纯采用分治法，没有改进2022/10/3070-Strassen矩阵乘法使用与上例类似的技术，将矩阵A，B和Strassen矩阵乘法为了降低时间复杂度，必须减少乘法的次数。2022/10/3071-Strassen矩阵乘法为了降低时间复杂度，必须减少乘法的次复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进2022/10/3072-复杂度分析2022/10/2372-Strassen矩阵乘法传统方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)是否能找到O(n2)的算法？？？目前为止还没有结果。2022/10/3073-Strassen矩阵乘法传统方法：O(n3)Hopcroft凸包问题（相关定义p84）什么是凸集合？对于平面的一个点集合（有限或无限），如果以集合中任意两点p和q为端点的线段都属于该集合，则称集合为凸的。定义：凸包：一个点集合s的凸包是包含s的最小凸集合。定理任意包含n>2个点（不共线的点）的集合s的凸包是以s中的某些点为顶点的多边形（如果所有的的店都位于一条直线上，多边形退化为一条线段，但它的2个端点让人包含在s中）2022/10/3074-凸包问题（相关定义p84）什么是凸集合？对于平面的一个点集合假设点按照x轴排序找出最左和最右的极点(leftmostandrightmost)递归的求凸包的上包:发现点Pmax

是离直线P1P2直线最远的点计算在直线P1Pmax左侧的上包计算在直线PmaxP2左侧的上包递归的计算下包2022/10/3075-假设点按照x轴排序2022/10/2375-p1p2凸包问题1、最左边的点p1和最右边的p2一定是该集合凸包顶点。2022/10/3076-p1p2凸包问题1、最左边的点p1和最右边的p2一定是该集合p1p2凸包问题2、找到上包的顶点，它是距离直线最远的点，如果用两条连接线的话，这个确定了最大的三角形pmaxp1p2。pmax2022/10/3077-p1p2凸包问题2、找到上包的顶点，它是距离直线最远的点，如p1p2凸包问题p1max3、找出距离p1pmax左边最远的点p3。如此进行下去，直到对应的包左边没有点p32022/10/3078-p1p2凸包问题p1max3、找出距离p1pmax左边最远的p1p2凸包问题p1maxp2max4、找出PmaxP2左边最远的点p4。，按照改方法进行，直到左边没有点p42022/10/3079-p1p2凸包问题p1maxp2max4、找出PmaxP2左边p1p2凸包问题p1maxp2max连接所得到的这些点2022/10/3080-p1p2凸包问题p1maxp2max连接所得到的这些点202p1p2凸包问题p1maxp2max利用上述求上包的方法求出下包。2022/10/3081-p1p2凸包问题p1maxp2max利用上述求上包的方法求2如何判断离线段p1p2最远的点？假设p3为任意点X1y11X2y21X3y31该行列式的绝对值表示以这3点构成的三角形面积，值为正，表示该点位于直线先左侧2022/10/3082-如何判断离线段p1p2最远的点？假设p3为任意点该行列式的绝本章结束，返回总目录2022/10/3083-本章结束，返回总目录2022/10/2383-Chapter4减治法Decrease-and-Conquer2022/10/3084-Chapter4减治法Decrease-and-Con减治法减治法减治法的类型减治法与其它方法的区别返回总目录2022/10/3085-减治法减治法返回总目录2022/10/2385-减治法基本思路：将原问题的实例转化为规模较小的实例对规模较小的实例的求解将较小的实例的解扩展到原实例能够使用自顶向下或者是自底向上经常被称为归纳法或者是增量法2022/10/3086-减治法基本思路：2022/10/2386-减治法的类型减去一个常量（一般是１）插入排序图形遍历算法（深度优先查找和广度优先查找）拓扑排序

减去一个常量因子（一般是一半）折半查找和二分法矩阵的幂运算俄式乘法减可变规模欧几里得问题部分选择2022/10/3087-减治法的类型减去一个常量（一般是１）2022/10/2387减去常量在这种减治法中，每次减去一个常量因子1。例如：插入排序

图形遍历算法（深度优先查找和广度优先查找）拓扑排序2022/10/3088-减去常量在这种减治法中，每次减去一个常量因子1。2022/1插入排序对数组A[0..n-1]，数组A[0..n-2]已经排好序，然后在数组中A[0..n-2]中找一个合适的位置将A[n-1]插入经常使用自底向上（非递归）例如:对6,4,1,8,5进行排序

6|4185 46|185 146|85 1468|5 145682022/10/3089-插入排序对数组A[0..n-1]，数组A[0..n-2]已经插入排序2022/10/3090-插入排序2022/10/2390-插入排序8945689029341745>比较45与89的大小2022/10/3091-插入排序8945689029341745>比较45与89的大插入排序8945689029341745>45<89，插入到89前面2022/10/3092-插入排序8945689029341745>45<89，插入到插入排序89689029341745比较68与前面的数的大小2022/10/3093-插入排序89689029341745比较68与前面的数的大小插入排序8968902934174568>68<892022/10/3094-插入排序8968902934174568>插入排序8968902934174568>89后移一个位置2022/10/3095-插入排序8968902934174568>插入排序8968902934174568<比较45与68的大小2022/10/3096-插入排序8968902934174568<比较45与68的大插入排序8968902934174568<将68插入到45后面2022/10/3097-插入排序8968902934174568<将68插入到45后插入排序89902934174568比较90与前面的数的大小2022/10/3098-插入排序89902934174568比较90与前面的数的大小插入排序89902934174568<89<902022/10/3099-插入排序89902934174568<插入排序89902934174568<将90插入到89后面的位置2022/10/30100-插入排序89902934174568<将90插入到89后面的插入排序89902934174568比较29与前面的数的大小2022/10/30101-插入排序89902934174568比较29与前面的数的大小插入排序………2022/10/30102-插入排序………2022/10/23102-插入排序34456889901729排好序后的数组2022/10/30103-插入排序34456889901729排好序后的数组2022/插入排序效率分析时间效率 Cworst(n)=n(n-1)/2

Θ(n2) Cavg(n)≈n2/4Θ(n2) Cbest(n)=n-1Θ(n)空间效率稳定的最好排序方法二分法插入排序2022/10/30104-插入排序效率分析时间效率2022/10/23104-图遍历许多问题要求自动系统地遍历图所有的节点：Depth-firstsearch(DFS)深度优先查找Breadth-firstsearch(BFS)广度优先查找2022/10/30105-图遍历许多问题要求自动系统地遍历图所有的节点：2022/10深度优先遍历(DFS)从任意顶点开始访问图的顶点，然后把改顶点标记已访问，在每次迭代的的时候，紧接着访问与当前顶点邻接的未访问顶点，直到遇到一个死端。用一个堆栈第一次访问时入栈当该顶点变成一个死端时出栈2022/10/30106-深度优先遍历(DFS)从任意顶点开始访问图的顶点，然后把改顶深度优先遍历(DFS)2022/10/30107-深度优先遍历(DFS)2022/10/23107-DFSDFStraversalstack:DFStree:aaabefcdgha入栈2022/10/30108-DFSDFStraversalstack:DFStreDFStraversalstack:DFStree:baababefcdghb入栈DFS2022/10/30109-DFStraversalstack:DFStree:bDFStraversalstack:DFStree:fbaabfabefcdghf入栈DFS2022/10/30110-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:efbaabfeabefcdghe入栈DFS2022/10/30111-DFStraversalstack:DFStree:eDFStraversalstack:DFStree:fbaabfeabefcdghe出栈DFS2022/10/30112-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:fbaabfeabefcdghf出栈DFS2022/10/30113-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:baabfeabefcdghb出栈DFS2022/10/30114-DFStraversalstack:DFStree:bDFStraversalstack:DFStree:gbaabfebgabefcdghg入栈DFS2022/10/30115-DFStraversalstack:DFStree:gDFStraversalstack:DFStree:cgbaabfebgcabefcdghc入栈DFS2022/10/30116-DFStraversalstack:DFStree:cDFStraversalstack:DFStree:dcgbaabfebgcdabefcdghd入栈DFS2022/10/30117-DFStraversalstack:DFStree:dDFStraversalstack:DFStree:hdcgbaabfegcdhabefcdghh入栈DFS2022/10/30118-DFStraversalstack:DFStree:hDFStraversalstack:DFStree:hdcgbaabfegcdhabefcdghh出栈DFS2022/10/30119-DFStraversalstack:DFStree:hDFStraversalstack:DFStree:dcgbaabfegcdhabefcdghd出栈DFS2022/10/30120-DFStraversalstack:DFStree:dDFStraversalstack:DFStree:cgbaabfegcdhabefcdghc出栈DFS2022/10/30121-DFStraversalstack:DFStree:cDFStraversalstack:DFStree:gbaabfegcdhabefcdghg出栈DFS2022/10/30122-DFStraversalstack:DFStree:gDFSDFStraversalstack:DFStree:baabfegcdhabefcdghb出栈2022/10/30123-DFSDFStraversalstack:DFStreDFSDFStraversalstack:DFStree:aabfegcdhabefcdgha出栈2022/10/30124-DFSDFStraversalstack:DFStreDFSDFStraversalstack:DFStree:abfegcdhabefcdghDFS完成2022/10/30125-DFSDFStraversalstack:DFStre深度优先遍历(DFS)DFS能够在两种表示方式下实现：Θ(V2)邻接矩阵Θ(|V|+|E|)邻接表产生两种节点序列：第一次访问的顶点（入栈）的次序顶点成为死端（出栈）的次序应用：检查图的连通性和找出图的连通分量量

检查图的无环性查找关节点和重连通分量搜索状态空间的问题解决方案（人工智能）2022/10/30126-深度优先遍历(DFS)DFS能够在两种表示方式下实现：20广度优先遍历(BFS)访问所有和初始顶点邻接的顶点使用队列而不是堆栈类似于层次遍历2022/10/30127-广度优先遍历(BFS)访问所有和初始顶点邻接的顶点2022/广度优先遍历(BFS)2022/10/30128-广度优先遍历(BFS)2022/10/23128-BFSBFStraversalstack:BFStree:aabefcdgh

a入队a2022/10/30129-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfebfeabefcdgh

a出队，b、e、f入队a2022/10/30130-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfeggabefcdgh

b出队，g入队bfe2022/10/30131-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegabefcdgh

e出队gfe2022/10/30132-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegabefcdgh

f出队gf2022/10/30133-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegchchabefcdgh

g出队，c、h入队g2022/10/30134-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhdabefcdgh

c出队，d入队ch2022/10/30135-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhdabefcdgh

h出队h2022/10/30136-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhabefcdgh

d出队，BFS完成d2022/10/30137-BFSBFStraversalstack:BFStre广度优先遍历(BFS)BFS和DFS具有相同的效率，也并且能够使用其他的图来表示：邻接矩阵:Θ(V2)邻接表:Θ(|V|+|E|)只产生一种顶点序列(入队和出队的次序时一样的)

应用:和DFS一样,但是BFS还能够用来查找从一个顶点到其他所有顶点间边的数量最少的路径。2022/10/30138-广度优先遍历(BFS)BFS和DFS具有相同的效率，也并无环有向图和拓扑排序无环有向图:

有向图没有回边

许多牵扯到先决条件的问题都可以通过建立一个图形模型来解决(施工项目,文档版本控制)对于图中的每一条边来说，边的起始顶点总是排在边的顶点结束之前.为了使拓扑排序成为可能，图必须是一个无环有向图

abcd无环有向图abcd非无环有向图2022/10/30139-无环有向图和拓扑排序无环有向图:有向图没有回边许多牵扯到先拓扑排序举例将下列食物链按顺序排列fishhumanshrimpsheepwheatplanktontiger2022/10/30140-拓扑排序举例将下列食物链按顺序排列fishhumanshri基于DFS的算法基于DFS算法的拓扑排序执行一次DFS遍历，并记住顶点变成死端（退出遍历栈）的顺序将该次序反过来得到拓扑排序的一个解遇到回边?→不是无环有向图!abefcdgh2022/10/30141-基于DFS的算法基于DFS算法的拓扑排序abefcdgh20源删除算法源删除算法

不断的做一件事，再余下的有向图中求一个源，他是一个没有输入边的顶点，然后把它和所有从他出发的边都删除（如果有多个源，任意删掉一个，如果不存在，算法就停止）。abefcdgh2022/10/30142-源删除算法源删除算法abefcdgh2022/10/2314拓扑排序fishhumanshrimpsheepwheatplanktontiger2022/10/30143-拓扑排序fishhumanshrimpsheepwheatp拓扑排序fishhumanshrimpsheepwheattiger剔除plankton2022/10/30144-拓扑排序fishhumanshrimpsheepwheatt拓扑排序fishhumanshrimpsheeptiger剔除plankton剔除wheat2022/10/30145-拓扑排序fishhumanshrimpsheeptiger剔拓扑排序fishhumansheeptiger剔除plankton剔除wheat剔除shrimp2022/10/30146-拓扑排序fishhumansheeptiger剔除plan拓扑排序humansheeptiger剔除plankton剔除wheat剔除shrimp剔除fish2022/10/30147-拓扑排序humansheeptiger剔除plankton拓扑排序humantiger剔除plankton剔除wheat剔除shrimp剔除fish剔除sheep2022/10/30148-拓扑排序humantiger剔除plankton剔除wh拓扑排序tiger剔除plankton剔除wheat剔除shrimp剔除fish剔除sheep剔除human2022/10/30149-拓扑排序tiger剔除plankton剔除wheat剔除拓扑排序剔除plankton剔除wheat剔除shrimp剔除fish剔除sheep剔除human剔除tiger求得的解是plankton，wheat，shrimp，fish，sheep，human，tiger2022/10/30150-拓扑排序剔除plankton剔除wheat剔除shri生成组合对象的算法1.生成排列对于n个元素，如何生成其排列呢？可以想像已经生成了n-1个元素的排列，我们可以将第n个元素插入到n-1个元素所产生的全部排列中去开始时将n从右往左插入到前面n-1生成的排列中去,然后每处理一个新的排列时，再调换方向。开始： 1开从右往左将2插入： 1221开从右往左将3插入： 123132312 开从左往右将3插入： 321231213 2022/10/30151-生成组合对象的算法1.生成排列开始： 1用该方法生成排列有什么优点呢？

满足最小变化的要求2022/10/30152-用该方法生成排列有什么优点呢？2022/10/23152-Johnson-Trotter算法生成排列该算法是一种有效的生成排列的算法将每个元素赋予一个方向，如果箭头指向一个相邻的较小元素，我们说它在这个箭头标记的排列中是移动的元素。例如32412022/10/30153-Johnson-Trotter算法生成排列该算法是一种有效的应用该算法生成3个元素的所有排列过程如下将所有元素初始化为123，以后重复执行2-5步骤如果存在移动元素，则找到最大的移动元素k把k和它所指向的相邻元素互换跳转所有大于k的元素的方向将排列加到列表中2022/10/30154-应用该算法生成3个元素的所有排列过程如下2022/10/23生成字典序排列的算法Johnson-Trotter算法生成的是最小变化的序该算法生成的不是字典顺序的序列字典序列123，132，213，231，312，312如何生成字典序列呢？从右往左寻找到第一对升序序的数字ai,ai+1，然后在ai+1到an中找到最小的大于ai的数字，将其与ai交换，然后将ai与后面的其他数字进行升序排列

四个数的字典序列1234124313241342……2022/10/30155-生成字典序排列的算法Johnson-Trotter算法生成的生成子集利用减1思想，集合分成2个部分，一个部分包含an，一个部分是其他n-1个元素的所有集合，通过把ai+1加入到每一个子集中来获得全部n个元素的子集利用n个元素的2n个子集和长度为n的所有2n个比特串之间的对象关系，二进制比特串的第i位为1表示n个元素中的第i个元素在该集合中，为o表示不在该集合中，如3位的比特串010，表示该子集中只有第2个元素。如3个元素的a1a2a3所有子集 000001010011100101110111空集a3a2a2a3a1a1a3a1a2a1a2a32022/10/30156-生成子集利用减1思想，集合分成2个部分，一个部分包含an，一格雷码格雷码是一个数列集合，相邻两数间只有一个位元改变，为无权数码，且格雷码的顺序不是唯一的。某些情况，例如从十进制的3转换成4时二进制码的每一位都要变，使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它是一种数字排序系统，其中的所有相邻整数在它们的数字表示中只有一个数字不同。它在任意两个相邻的数之间转换时，只有一个数位发生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。2022/10/30157-格雷码格雷码是一个数列集合，相邻两数间只有一个位元改变，为无如何生成格雷码方法1：以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反覆，即可排列出n个位元的格雷码。方法2：先生成n-1的二进制格雷码序列a，然后复制一份该代码序列b，将0加在a序列的最左边，将1加在序列b的最左边，然后将修改后的b序列反序连接在修改后a序列后2022/10/30158-如何生成格雷码2022/10/23158-减常量因子在这种减治法中，每次减去一个相同的常量因子。例如：假币问题俄式乘法2022/10/30159-减常量因子在这种减治法中，每次减去一个相同的常量因子。202假币问题（简单版本）在n枚外观相同的硬币中寻找一枚假币.

有一架没有刻度的天平但是能够显示两边的重量是否相等,如果相等，天平就不会倾斜，如果不相等，重的一边就会倾斜

设计一个有效的算法来找出这枚假币。假设这枚假币比真币要轻。2022/10/30160-假币问题（简单版本）在n枚外观相同的硬币中寻俄式乘法问题:两个正整数相乘该问题能够使用下面的公式进行减半的运算:对于每一个n:如果n是奇数:n*m=*2m

n*m=*2m+mifn>1andmifn=1n2n–122022/10/30161-俄式乘法问题:两个正整数相乘对于每一个n:如果n是奇数俄式乘法Compute20*26

nm

2026105251041042208+1416416

520

Note:把所有n列中包含基数的m列元素进行相加2022/10/30162-俄式乘法Compute20*26520Note:约瑟夫斯问题问题的提出2022/10/30163-约瑟夫斯问题问题的提出2022/10/23163-减可变因子在这种减治法当中，每次迭代都减小规模不同的因子。例如:欧几里得算法查找问题—计算中值和选择问题2022/10/30164-减可变因子在这种减治法当中，每次迭代都减小规模不同的因子。欧几里得求最大公约数算法欧几里得算法重复使用公式：gcd(m,n)=gcd(n,mmodn)例如:

gcd(80,44)=gcd(44,36)=gcd(36,8)=gcd(8,4)余数为0结束，取次数被除数作为最大公约数T(n)

O(logn)2022/10/30165-欧几里得求最大公约数算法欧几里得算法重复使用公式：2022/查找问题在n个数中查找第k小的元素k=1ork=n中值:k=n/2

例如:4,1,10,9,7,12,8,2,15 中值=?中值是数理统计中用来求平均值的一个很好的方法事实上，它比其他类似合并排序的算法要优秀很多。2022/10/30166-查找问题2022/10/23166-a[0]a[1]a[2]a[3]…a[j-1]…a[n-1]如果有一个数组a[n]，现要求出其中第k小元素a[0]a[1]a[2]a[3]……a[i]a[n-1]A:以数组第一个元素为标准，利用快速排序得到此数值在数组中的位置是第j个K<j-1K=j-1a[j-1]…a[n]a[0]…a[j-1]K>=j继续步骤Aa[j-1]即为所求求第K小元素2022/10/30167-a[0]a[1]a[2]a[3]…a[j-1]…a[n-1411097128215K=[9/2]=5中值问题2022/10/30168-411097128215K=[9/2]=5中值问题2022/411097128215214971281015K=[9/2]=5中值问题2022/10/30169-411097128215214971281015K=[9/2411097128215214971281015S=3<5,处理列表的右边部分。K=[9/2]=5中值问题2022/10/30170-411097128215214971281015S=3<5,411097128215214971281015S=3<5,处理列表的右边部分。971281015K=[9/2]=5中值问题2022/10/30171-411097128215214971281015S=3<5,411097128215214971281015S=3<5,处理列表的右边部分。971281015K=[9/2]=5879121015中值问题2022/10/30172-411097128215214971281015S=3<5,411097128215214971281015S=3<5,处理列表的右边部分。971281015K=[9/2]=5879121015S=6>5,处理列表的左边部分。中值问题2022/10/30173-411097128215214971281015S=3<5,411097128215214971281015S=3<5,处理列表的右边部分。971281015K=[9/2]=5879121015S=6>5,处理列表的左边部分。8中值问题2022/10/30174-411097128215214971281015S=3<5,411097128215214971281015S=3<5,处理列表的右边部分。971281015K=[9/2]=5879121015S=6>5,处理列表的左边部分。87中值问题202