《算法设计与分析》课件全套 林海 第1-9章 概述 - - 匹配与指派

算法设计与分析参考书算法导论（原书第3版）机械工业出版社算法设计技巧与分析，M.H.Alsuwaiyel著,电子工业出版社，吴伟昶等译平时（代码，作业，到课率）40%期末60%课程目标学习各种经典算法设计算法解决问题分析算法性能算法实践（课后）课程意义算法能力能够准确辨别一个程序员的技术功底是否扎实算法能力是发掘程序员的学习能力与成长潜力的关键手段算法能力能够协助判读程序员在面对新问题时，分析并解决问题的能力算法能力是设计一个高性能系统、性能优化的必备基础算法是大厂考核的必然科目课程意义算法在计算机科学中的地位核心基础课程1966年至2011年的图灵奖获得者中有19人直接或间接地与算法相关姚期智：Yao'smin-maxprinciple基本编程以数据结构为中心的算法设计─基本算法设计方法通用算法设计─算法设计方法学识字写小作文写大文章与语文学习过程类比数据结构程序设计语言算法设计与分析数据结构1.基本概念算法是什么：算法(Algorithm)是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制—百度百科。计算机解决问题的方法、步骤1.算法特征搜索给定一个数组，并给出一个数，要求在这个数组中寻找这个数，并返回相应的下标。二分搜索：对已经排序好的数据进搜索1.算法特征二分搜索：对已经排序好的数据进搜索1.算法特征二分搜索：伪代码1.算法特征二分搜索：分析最好情况：中间数据，比较一次最差情况：1.算法特征排序：选择排序找到n个元素中最小的一个元素，将其和第一个元素交换;在剩余的元素中找到最小的一个元素，将其和剩余元素的第一个元素交换;重复上面这个步骤，直到剩余元素为0。1.算法特征特征算法有输入和输出算法的每一步是可行的除了可行，每一步还必须是确定的算法必须在有限的时间(步骤)内完成2.算法复杂度选择排序为例2.算法复杂度选择排序为例2.算法复杂度2.算法复杂度2.1时间复杂度：上界2.1时间复杂度：上界2.1时间复杂度：上界2.1时间复杂度：上界2.1时间复杂度：上界O运算具有如下运算规则2.1时间复杂度：下界2.1时间复杂度：下界2.1时间复杂度：下界2.1时间复杂度：同阶2.1时间复杂度：同阶2.1时间复杂度2.1时间复杂度2.1时间复杂度：例子2.1时间复杂度：例子2.1时间复杂度：例子2.1时间复杂度：例子2.1时间复杂度：例子2.1时间复杂度：例子2.2算法的时间复杂度计算执行频率最高的语句来作为算法的复杂度在迭代(循环)的场景下，复杂度就是计算迭代次数最高的语句2.2算法的时间复杂度循环并列的情况：算法的复杂度是循环次数的相加2.2算法的时间复杂度循环嵌套的情况：算法的复杂度最里面嵌套2.3算法的空间复杂度为了求解问题的实例而执行的计算步骤所需要的内存空间数目例子选择排序的空间复杂度为Θ(1)合并排序的空间复杂度为Θ(n)例子例子算法1：将所有的歌曲按照评分复制其编号，如歌曲1的评分为5.5，就将1复制55，歌曲10评分为6.6，则将10复制66。然后随机的从这些编号中选取一个编号，选到的编号即为播放曲目。此算法的时间复杂度为O(1)，空间复杂度为n*E[歌曲的评分]。算法2：将所有的歌曲按照评分排列，并根据评分生成随机区间，然后总区间的一个随机值，这个值落在哪个区间，即播放相应的歌曲。如有4首歌其评分为[1,1.5,2,2]，则生成区间[0-1,1-2.5,2.5-4.5,4.5-6.5]4个区间，然后在[0-6.5]取一个随机数，随机数落在哪个区间，播放相应的歌曲。此算法的时间复杂度为O(logn)，空间复杂度为n*2。算法3：从1-n选取一个随机数用于随机选取一首歌曲。再从1-10选取一个随机数，当选取歌曲的评分大于这个随机数时，播放歌曲，否则不播放。空间复杂度为0，时间复杂度为随机数的生成例子P331.4

1.6

1.11

1.13

1.16

1.23

1.261.31

1.35

3.数据结构算法的实现离不开数据结构。选择一个合适的数据结构对设计一个有效的算法有十分重要的影响。结构化程序设计创始人NiklausWirth(瑞士苏黎士高工)提出一个著名的论断：“程序=算法+数据结构”。1984年，Wirth因开发了Euler、Pascal等一系列崭新的计算语言而荣获图灵奖,有“结构化程序设计之父”之美誉我们已经学过数组、队列、栈、二叉树等数据结构，这里学习堆和不相交集3.1堆(Heap)在许多算法中，需要大量用到如下两种操作：插入元素和寻找最大(小)值元素。为了提高这两种运算的效率，必须使用恰当的数据结构。普通队列：易插入元素，但求最大(小)值元素需要搜索整个队列。排序数组：易找到最大(小)值，但插入元素需要移动大量元素。堆则是一种有效实现上述两种运算的简单数据结构。3.1堆(Heap)3.1堆(Heap)：特征堆是一棵完全二叉树，堆所对应树的节点的排列必须是从上到下，从左到右的依次排列，否则将不构成堆在最大堆中，根节点值最大，叶子节点值较小，从根到叶子的一条路径上，节点值以非升序排列任何一个父节点的值都大于等于其子节点的值，但节点的左右子节点值并无顺序要求，且上层节点的值不一定大于下层节点的值堆中每个结点的子树都是堆3.1堆(Heap)有n个节点的堆T,可以用一个数组a[1…n]来存储，按照节点从上到下，从左到右的顺序依次存储用下面的方式来表示：T的根节点存储在a[1]中假设T的节点x存储在a[j]中，那么，它的左右子节点分别存放在a[2j]及a[2j+1]中(如果有的话)。a[j]的父节点如果不是根节点，则存储在a[

j/2

]中3.1堆(Heap)3.1堆(Heap)：上移若某个节点a[i]键值大于其父节点的键值，就违背了堆的特性，需要进行调整。调整方法：上移。沿着a[i]到根节点的唯一一条路径，将a[i]移动到合适的位置上：比较a[i]及其父节点a[

i/2

]的键值，若key(a[i])>key(a[

i/2

])，则二者进行交换，直到a[i]到达合适位置。3.1堆(Heap)：上移所需要的时间是O(logn).3.1堆(Heap)：下移假如某个内部节点a[i](i≤

n/2

)，其键值小于儿子节点的键值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右儿子存在)，违背了堆特性，需要进行调整。调整方法：下移。沿着从a[i]到子节点(可能不唯一，则取其键值较大者)的路径，比较a[i]与子节点的键值，若key(a[i])<max(a[2i],a[2i+1])则交换之。这一过程直到叶子节点或满足堆特性为止。3.1堆(Heap)：下移所需要的时间是O(logn).3.1堆(Heap)：插入思路：先将x添加到a[]的末尾，然后利用Sift-up，调整x在a[]中的位置，直到满足堆特性。树的高度为

logn,所以将一个元素插入大小为n的堆所需要的时间是O(logn).3.1堆(Heap)：删除思路：先用a[n]取代a[i]，然后对a[i]作Sift-up或Sift-down)，直到满足堆特性。所需要的时间是O(logn).3.1堆(Heap)：删除堆顶元素输入：堆H[1…n]输出：返回最大键值元素，并将其从堆中删除

x←H[1]2.delete(H,1)3.returnx3.1堆(Heap)：构建方法1：从一个空堆开始，逐步插入A中的每个元素，直到A中所有元素都被转移到堆中。时间复杂度为O(nlogn)因为插入一个元素需要logn，总共需要插入n个元素3.1堆(Heap)：构建其他方法：直接对数据进行调整自上而下的调整一次调整需要O(nlogn)，总共需要log

n次调整，总复杂度为O(nlog2n)3.1堆(Heap)：构建自下而上的调整调整一次即可（对以节点i为根的子树进行调整）但复杂度依然是O(nlogn)优化：1.叶子节点不需要调整；2.对子树进行调整第i层的节点的调整最多交换⌊logn⌋−i次3.1堆(Heap)：构建例：给定数组A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，构建堆3.1堆(Heap)：构建3.1堆(Heap)：构建复杂度3.1堆(Heap)：构建复杂度3.1堆(Heap)：d堆d堆：如三叉堆，四叉堆；树的层数为logdn3.2不相交集在离散数学我们学过等价类是对集合S的一个划分，对集合S的划分形成了集合S的不相交集3.2不相交集不相交集可以用树表示4个子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分别命名。11110726539843.2不相交集：查找、合并FIND(x):寻找包含元素x的集合的名字记root(x)为包含元素x的树的根，则FIND(x)返回root(x).UNION(x,y):将包含元素x和y的两个集合合并，重命名。执行合并UNION(x,y)时，首先依据x找到root(x),记为u,依据y找到root(y)，记为v；然后，将u指向v。3.2不相交集：查找、合并3.2不相交集：秩和基于秩的合并按秩合并的顺序决定了树的高度。一个有n节点，且是通过不相交集合并操作形成的树，其最大的高度是多少？3.2不相交集：秩和基于秩的合并3.2不相交集：秩和基于秩的合并3.2不相交集是不是通过基于秩的合并就总能得到最优的不相交集?不一定：如有4个节点，先合并1和2，再合并3和4，不一定是最优的如何优化？合并时调整：复杂度从O(logn)变为O(n)专门设置一个调整操作：也为O(n)部分解决方案：路径压缩3.2不相交集：路径压缩这个算法中为什么不对rank进行改变？345例：初始状态：{1},{2},…,{9}612789执行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),得到的结果是：345612789继续执行合并序列：UNION(2,4),UNION(8,9),UNION(6,8),得到的结果是：345612789继续执行：FIND(5)得到的结果是：345612789继续执行UNION(4,8)继续执行：UNION(4,8)得到的结果是：345612789继续执行：FIND(1)得到的结果是：345612789算法设计与分析堆和不相交集数据结构算法的实现离不开数据结构。选择一个合适的数据结构对设计一个有效的算法有十分重要的影响。结构化程序设计创始人NiklausWirth(瑞士苏黎士高工)提出一个著名的论断：“程序=算法+数据结构”。1984年，Wirth因开发了Euler、Pascal等一系列崭新的计算语言而荣获图灵奖,有“结构化程序设计之父”之美誉我们已经学过数组、队列、栈、二叉树等数据结构，这里学习堆和不相交集堆(Heap)在许多算法中，需要大量用到如下两种操作：插入元素和寻找最大(小)值元素。为了提高这两种运算的效率，必须使用恰当的数据结构。普通队列：易插入元素，但求最大(小)值元素需要搜索整个队列。排序数组：易找到最大(小)值，但插入元素需要移动大量元素。堆则是一种有效实现上述两种运算的简单数据结构。堆(Heap)堆(Heap)：特征堆是一棵完全二叉树，堆所对应树的节点的排列必须是从上到下，从左到右的依次排列，否则将不构成堆在最大堆中，根节点值最大，叶子节点值较小，从根到叶子的一条路径上，节点值以非升序排列任何一个父节点的值都大于等于其子节点的值，但节点的左右子节点值并无顺序要求，且上层节点的值不一定大于下层节点的值堆中每个结点的子树都是堆堆(Heap)有n个节点的堆T,可以用一个数组a[1…n]来存储，按照节点从上到下，从左到右的顺序依次存储用下面的方式来表示：T的根节点存储在a[1]中假设T的节点x存储在a[j]中，那么，它的左右子节点分别存放在a[2j]及a[2j+1]中(如果有的话)。a[j]的父节点如果不是根节点，则存储在a[

j/2

]中堆(Heap)堆(Heap)：上移若某个节点a[i]键值大于其父节点的键值，就违背了堆的特性，需要进行调整。调整方法：上移。沿着a[i]到根节点的唯一一条路径，将a[i]移动到合适的位置上：比较a[i]及其父节点a[

i/2

]的键值，若key(a[i])>key(a[

i/2

])，则二者进行交换，直到a[i]到达合适位置。堆(Heap)：上移所需要的时间是O(logn).堆(Heap)：下移假如某个内部节点a[i](i≤

n/2

)，其键值小于儿子节点的键值,即key(a[i])<key(a[2i])或key(a[i]<key(a[2i+1])(如果右儿子存在)，违背了堆特性，需要进行调整。调整方法：下移。沿着从a[i]到子节点(可能不唯一，则取其键值较大者)的路径，比较a[i]与子节点的键值，若key(a[i])<max(a[2i],a[2i+1])则交换之。这一过程直到叶子节点或满足堆特性为止。堆(Heap)：下移所需要的时间是O(logn).堆(Heap)：插入思路：先将x添加到a[]的末尾，然后利用Sift-up，调整x在a[]中的位置，直到满足堆特性。树的高度为

logn,所以将一个元素插入大小为n的堆所需要的时间是O(logn).堆(Heap)：删除思路：先用a[n]取代a[i]，然后对a[i]作Sift-up或Sift-down)，直到满足堆特性。所需要的时间是O(logn).堆(Heap)：删除堆顶元素输入：堆H[1…n]输出：返回最大键值元素，并将其从堆中删除

x←H[1]2.delete(H,1)3.returnx堆(Heap)：构建方法1：从一个空堆开始，逐步插入A中的每个元素，直到A中所有元素都被转移到堆中。时间复杂度为O(nlogn)因为插入一个元素需要logn，总共需要插入n个元素堆(Heap)：构建其他方法：直接对数据进行调整自上而下的调整一次调整需要O(nlogn)，总共需要log

n次调整，总复杂度为O(nlog2n)堆(Heap)：构建自下而上的调整调整一次即可（对以节点i为根的子树进行调整）但复杂度依然是O(nlogn)优化：1.叶子节点不需要调整；2.对子树进行调整第i层的节点的调整最多交换⌊logn⌋−i次堆(Heap)：构建例：给定数组A[1…10]={5,15,19,12,6,10,7,36,11,8，9,16}，构建堆堆(Heap)：构建堆(Heap)：构建复杂度堆(Heap)：构建复杂度堆(Heap)：d堆d堆：如三叉堆，四叉堆；树的层数为logdn不相交集在离散数学我们学过等价类是对集合S的一个划分，对集合S的划分形成了集合S的不相交集不相交集不相交集可以用树表示4个子集1:{1,7,10,11}，3:{2,3,5,6}，8:{4,8}，9:{9}并分别命名。1111072653984不相交集：查找、合并FIND(x):寻找包含元素x的集合的名字记root(x)为包含元素x的树的根，则FIND(x)返回root(x).UNION(x,y):将包含元素x和y的两个集合合并，重命名。执行合并UNION(x,y)时，首先依据x找到root(x),记为u,依据y找到root(y)，记为v；然后，将u指向v。不相交集：查找、合并不相交集：秩和基于秩的合并按秩合并的顺序决定了树的高度。一个有n节点，且是通过不相交集合并操作形成的树，其最大的高度是多少？不相交集：秩和基于秩的合并不相交集：秩和基于秩的合并不相交集是不是通过基于秩的合并就总能得到最优的不相交集?不一定：如有4个节点，先合并1和2，再合并3和4，不一定是最优的如何优化？合并时调整：复杂度从O(logn)变为O(n)专门设置一个调整操作：也为O(n)部分解决方案：路径压缩不相交集：路径压缩这个算法中为什么不对rank进行改变？345例：初始状态：{1},{2},…,{9}612789执行合并序列：UNION(1,2),UNION(3,4),UNION(5,6),UNION(7,8),得到的结果是：345612789继续执行合并序列：UNION(2,4),UNION(8,9),UNION(6,8),得到的结果是：345612789继续执行：FIND(5)得到的结果是：345612789继续执行UNION(4,8)继续执行：UNION(4,8)得到的结果是：345612789继续执行：FIND(1)得到的结果是：345612789算法设计与分析排序排序比较排序冒泡排序堆排序插入排序归并排序线性排序桶排序计数排序基数排序1.1冒泡排序冒泡排序和选择排序很相似，但冒泡排序是每次都选择一个最大的元素，在第i次循环中，冒泡排序从未排序的元素中选择一个最大的元素，并将其放在倒数第i个位置。比较：通过依次对两两相邻的元素进行比较1.1冒泡排序一次冒泡过程1.1冒泡排序1.1冒泡排序和选择排序比较1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序将元素组织成堆结构，然后每次取堆顶元素1.2堆排序1.2堆排序是否稳定排序？1.3插入排序每次都从剩余的元素中取第一个元素，将其插入到前面已经排序好的序列中，使得插入后的序列依然是排序好的序列1.3插入排序1.3插入排序复杂度计算：插入排序是稳定排序1.3插入排序平均复杂度：有没有可能将插入排序的复杂度降低?1.3插入排序：希尔排序为了减少比较次数，可以跳着比，比如每隔4个元素比较一次1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.3插入排序：希尔排序1.4归并排序（合并排序）二路归并将两个已经排序好的数组(如数组A和数组B)进行合并，合并后的数组依然是排序好的1.4归并排序二路归并1.4归并排序归并排序1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序如4路归并算法，和2路归并比较有没有可能降低比较次数?1.4归并排序多路归并排序如4路归并算法，和2路归并比较1.4归并排序多路归并排序1.4归并排序多路归并排序1.4归并排序多路归并排序1.4归并排序基于锦标赛的多路合并在对k个排序好的子数组进行合并时，利用了一种联赛的机制来选取最小值。1.4归并排序胜者树1.4归并排序基于胜者树的合并算法1.4归并排序败者树1.4归并排序基于败者树的合并算法1.4归并排序基于败者树的合并算法2线性排序比较排序所能达到的最优复杂度为O(nlog

n)能进一步降低排序的复杂度吗？非比较排序只适合特定的场景2.1桶排序桶排序的基本步骤2.1桶排序几个问题2.1桶排序几个问题如果去比较一个元素是否属于某个桶，则分发的复杂度为O(mn)。为了直接得出一个元素属于哪个桶，需要计算元素所对应桶的下标。这个可以用前面任一复杂度为O(nlogn)的比较排序2.1桶排序算法2.1桶排序例子2.1桶排序2.2计数排序基本思想2.2计数排序问题2.2计数排序算法设置两个数组B和C，其中B用于存放排序好的数组，而C起着计数的作用(也就是‘桶’的作用)。第一个for循环(语句4-6)对C进行初始化第二个for循环(语句7-9)统计每个元素的个数第三个for循环(语句10-12)就是依次对数组C中第1个元素开始到最后一个进行累加，其作用是统计某个元素前共有多少个元素。第四个for循环(语句13-16)从A数组的最后一个元素开始，通过C数组中对应的值确定其在B数组中的位置。2.2计数排序算法2.2计数排序2.3基数排序基本思想2.3基数排序流程2.3基数排序例子2.3基数排序问题：需要对‘位’上的数据进行排序，如何排序？桶排序或者计数排序算法2.3基数排序问题2.3基数排序例子2.3基数排序算法MSD是一个递归的过程基数排序也可以用于其他方面，如字母的排序算法设计与分析递归主要内容基本概念递归的例子复杂度的递归求解1基本概念数学中的阶乘可以用递归表示，也可以很好的解释递归边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果1基本概念数学中的阶乘可以用递归表示，也可以很好的解释递归1基本概念执行函数Factorial(3)时，会进入函数Factorial(2)，之后进入Factorial(1)，因Factorial(1)满足边界条件，返回结果1到函数Factorial(2)，Factorial(2)完整计算，并返回结果2到Factorial(3)，Factorial(3)得出结果6。进入递归函数时，调用函数依旧保留其状态。也就是说如果执行Factorial(n)，当递归调用到Factorial(1)时，系统中总共创建了100个Factorial函数1例子：斐波那契数列数列:0、1、1、2、3、5、8、13、21、34、......这个数列从第3项开始，每一项都等于前两项之和1例子：汉诺塔问题1例子：汉诺塔问题1.1递归和迭代所有的递归实现都可以转换为迭代实现吗?反之，所有的迭代实现都可以通过递归实现吗？迭代转化为递归通常较简单：二分搜索输入：非降序排列的数组A[1…n]和元素x输出：如果x=A[j],1

j

n,则输出j,否则输出0.1.low←1;high←n;j←02.while(low

high)and(j=0)3.mid←

(low+high)/2

4.ifx=A[mid]thenj←mid5.elseifx<A[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnjbinarySearch(a,x,right,

left){while(left<=right){

middle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])return

binarySearch(a,

x,

right,

middle+1);

elsereturn

binarySearch(a,

x,

middle+1,

left);}

return-1;//未找到x}1.1递归和迭代迭代转化为递归通常较简单：选择排序1.1递归和迭代迭代转化为递归通常较简单：插入排序1.1递归和迭代递归转化为迭代时，要复杂很多如很难将汉诺塔问题转化为循环迭代（需要通过栈）从实际上说，所有的迭代可以转换为递归，但递归不一定可以转换为迭代2.1生成排列递归实际上就是找n规模问题和<n规模问题(通常是n−1规模问题)的一个关系2.1生成排列如已知X={1,2,3}的全排列P(X)，Y={1,2,3,4}的全排列P(Y)和P(X)之间存在什么关系2.1生成排列2.1生成排列2.1生成排列算法的复杂度由if和else两部分决定，直觉上觉得是else起决定作用输出语句共执行了nn！次，其中n！代表排序的总数，而每个排序有n个输出所以复杂度由if决定为2.2整数划分2.2整数划分下面的方法是否可行？存在重复计算2.2整数划分2.2整数划分2.2整数划分3时间复杂度计算迭代次数频度分析使用递归方程3.1计算迭代次数

计算迭代次数通常，程序的运行时间和程序的迭代次数成比例。因此计算程序的迭代次数就可以作为算法运行时间的指示器。这在很多算法中都可以得到应用，如查找、排序等等3.1计算迭代次数

输入：n(n=2k

，k为某一正整数)输出：count（迭代次数）1.count←02.whilen≥13.forj←1ton4.count←count+1//执行一次耗费时间设为a5.endfor6.n←n/2//执行一次耗费时间设为d7.endwhile8.returncount分析：while迭代的次数是k+1次(因为n≥1可以写成n≥20,运行过程n=2k→20)，k=logn。在每次while循环里面for依次执行n，n/2,n/4,…,1次，所以，算法的时间复杂度为：3.1计算迭代次数

为什么在上面计算算法的时间复杂度时不考虑step6,而只是考虑step4呢？如果同时考虑step4和step6，我们有小结：使用计算迭代次数的技术来分析算法的时间复杂度时，只需要考虑最深层次的迭代。3.2频度分析

频度分析对于有些算法，计算迭代次数非常麻烦，有时甚至是不可能的。这时候，可以使用频度分析。在MEGE算法中，赋值运算具有最大频度将A的每个元素移到B又将B的每个元素移到A所以算法复杂度为2n3.2最坏情况和平均情况分析平均情况分析：通常考虑均匀分布情况下的复杂度如插入排序中，将第i个元素插入到前面已经排序好的数组中插入到第1个位置，比较i-1次插入到其他位置（位置j），比较i-j+1次平均比较次数为：3.2最坏情况和平均情况分析插入排序总的平均比较次数为：插入排序最差的比较次数为：3.3复杂度的递归求解3.3复杂度的递归求解3.3.1展开法3.3.1展开法3.3.2代入法步骤先猜测解的形式再通过数学归纳法证明适用于对递归形式比较熟悉的情况代入法另外一用法是对展开法或者递归树法求得的复杂度，进行进一步的确认3.3.2代入法这个复杂度的递归式和快速排序的复杂度递归式类似，猜测其也为O(nlogn)3.3.2代入法边界条件：3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.3递归树方法3.3.3递归树方法首先将T(n)看出一个节点，如图展开将每个子节点按照T(n)方式展开从图中可知，递归树总共有logn层，对每层所有节点的复杂度进行累加，得出每层的复杂度为cn，叶子层的复杂度为nT(1)=nc′。所以总的复杂度T(n)=nlogn3.3.3递归树方法首先将复杂度的递归式展开为树的形式之后，计算树每层的复杂度最后，将所有层的复杂度相加，得到T(n)的复杂度3.3.3递归树方法这棵树并不是满二叉树，最短路径为n/2，最长路径为n。3.3.3递归树方法3.3.3递归树方法3.3.4主方法主要应用于先从简单的形式3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法3.3.5几种递归形式的分析3.3.5几种递归形式的分析3.3.5几种递归形式的分析3.3.5几种递归形式的分析此公式的求和项中，貌似每一项都是Θ(n2)，所以很容易错误的认为期望值也是Θ(n2)3.3.5几种递归形式的分析3.3.5几种递归形式的分析3.3.5几种递归形式的分析算法设计与分析分治主要内容分治的基本方法快速排序最大子数组问题最近点对问题寻找第k小元素棋盘覆盖分治的思想规模比较大的问题分解成较小的问题，较小的问题再解决成更小的问题，直到容易解决为止对较小问题的解决，是继续分解--递归方程直到容易解决为止（通常为1个元素）--边界条件1合并排序（分治）52分解47分解13分解26分解5247分解1326分解52471326分解524713261合并排序（分治）25合并47合并13合并26合并2457合并1236合并12234567合并524713261合并排序（分治）首先对原数组分解成左右两个子数组（减小问题的规模）（语句4-5）对这两个子数组进行排序，怎么排序？递归的调用原函数进行排序即可（语句6-7）最后通过合并操作对排序后的子数组进行合并（语句8）1分治步骤分解：将原问题分解成规模较小的子问题原问题P可以被分成多个子问题P1,P2,···,Pk子问题的形式需要和原问题一致解决：通过递归的方式解决子问题P1,P2的独立解，以及P1,P2共同相关的解合并：对子问题的解进行合并，形成原问题的解。1分治步骤原问题(sizen)子问题1子问题2子问题k…子问题21子问题22子问题2k…:分解:递归解决

:合并2快速排序快速排序的基本步骤2快速排序：分解主元的选择：第一个元素或者最后一个元素问题：相同元素的位置发生了改变2快速排序：分解主让i指向小于等于主元素部分的最后一个元素，j指向大于主元素部分的最后一个元素2快速排序2快速排序：复杂度分析对半分按比例分2快速排序：复杂度分析常数划分算法期望复杂度3最大子数组问题3最大子数组问题最大子数组的基本步骤3最大子数组问题最大子数组的基本步骤3最大子数组问题横跨在两个子问题上的最大子数组只要依次遍历左右数组的所有子数组，即可找到横跨在两个子问题上的最大子数组复杂度3最大子数组问题复杂度4最近点对问题穷举求解将每一个点都与其它n-1个点的距离算出来，然后找出其中最小的即可4最近点对问题最近点对的基本步骤4最近点对问题最近点对的基本步骤4最近点对问题为此，我们设δ=min{δl,δr}，并在直线L左右两边分别画出宽度为δ的区域，如图中的Sl′和Sr′，显而易见，小于min{δl,δr}的点对只可能出现在这个两个区域。那么，是不是只要比较所有Sl′和Sr′间点对的距离即可4最近点对问题只需要比较图中所示的δ∗2δ长方形上的点即可，落在这个长方形外的点和p的距离一定是大于δ的。这个长方形区域最多只能放6个点

哪6个点？在y轴上投影，相邻的8个点

4最近点对问题复杂度还能不能进一步降低？4最近点对问题复杂度4最近点对问题5寻找第k小元素5寻找第k小元素5寻找第k小元素如何将原数组分成两个子问题？寻找一个中间元素如何找到这个处于中间位置的元素m？将n个元素划分成m个组(通常是每组5个元素)，取每组的中间元素，再取这些中间元素的中间元素怎么找到中间元素的中间元素？递归调用5寻找第k小元素哪个子问题需要被舍弃？元素分成3组，小于m，等于m，和大于m，找到相应的组，舍弃其他组一

为方便演示，设阈值为6。现要寻找下面数组A中的第13小元素：A={8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7}{8,33,17,51,57}{49,35,11,25,37}{14,3,2,13,52}{12,6,29,32,54}{5,16,22,23,7}{8,17,33,51,57}{11,25,35,37,49}{2,3,13,14,52}{6,12,29,32,54}{5,7,16,22,23}M={33,35,13,29,16}mm=29A1={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A2={29}A3={33,51,57,49,35,37,52,32,54}因为k=13<|A1|=15{8,17,11,25,14}{3,2,13,12,6}{5,16,22,23,7}M={14,6,16}mm=14{8,11,14,17,25}{2,3,6,12,13}{5,7,16,22,23}A={8,17,11,25,14,3,2,13,12,6,5,16,22,23,7}A1={8,11,3,2,13,12,6,5,7}A2={14}A3={17,25,16,22,23}M={14,6,16}mm=14因为k=13>|A1|+|A2|＝9＋1=10因为|A3|<p=6阈值{16,17,22,23,25,}returnA[3]因为(3=13-9-1)5寻找第k小元素5寻找第k小元素：复杂度5寻找第k小元素：复杂度5寻找第k小元素：复杂度5寻找第k小元素：以平均值为中项元素对S中所有的元素求一个均值，用这个均值对数组进行划分即可5寻找第k小元素：5寻找第k小元素：6棋盘覆盖问题：6棋盘覆盖问题：6棋盘覆盖问题：复杂度递归式（n为棋盘格子总数）：算法设计与分析动态规划主要内容动态规划的基本性质和步骤最大子数组问题0-1背包问题旅行商问题最长公共子序列状态压缩动态规划1引例：斐波那契数递归形式的算法：procedurefib(n)ifn=1orn=2thenreturn1elsereturnfib(n-1)+fib(n-2)1引例：斐波那契数存在大量重复计算当n=100时，用递归求解的时间T(100)≈3.53×1020,若每秒计算108次，需111,935年1解决方法从第1个元素开始计算，从而消除重复计算f1←1f2←1fori←3tonresult←f1+f2f1←f2f2←resultendforreturnresult1基本性质和分治类似动态规划也是将原问题分解为子问题求解和分治不同不是通过递归的方式，而是自低向上的求解问题1基本性质动态规划和分治的比较需要列出递归式1机器人行走1机器人行走分治1机器人行走分治需要计算多少次？55次

1机器人行走动态规划自底向上的计算：12次1基本性质动态规划适用的场景子问题并不独立，即子问题是可能重复的主要用于优化问题（求最优解），且问题具有最优子结构性质1最优子结构性质最短路径问题具有最优子结构性质（替换法证明）1最优子结构性质最长路径问题不具有最优子结构性质1基本步骤定义子问题，并分析最优解的结构特征分治通常是将原问题对半分，而动态规划是将n规模的问题分解成n−1规模的问题找出最优解对应的最优值，并递归地定义最优值以自底向上的方式计算出最优值根据计算最优值时得到的信息，构造最优解2最大子数组问题子问题的定义：基于分治的方法2最大子数组问题递归定义最优值是否存在重复计算？2最大子数组问题动态规划：n-1为原问题n的子问题求解改为：包含数组最后一个元素的最大子数组2最大子数组问题动态规划：最大子数组问题最优解的结构特征找出最优解对应的最优值，并递归地定义最优值2最大子数组问题动态规划：自底向上的求解最优值2最大子数组问题动态规划：根据b值矩阵得出最优解3

0-1背包问题3

0-1背包问题分析0-1背包问题最优解的结构特征一种情况是第n个物品不包括在最优解里第二种情况是第n个物品包括在最优解里3

0-1背包问题找出0-1背包问题最优解对应的最优值，并递归地定义最优值3

0-1背包问题自底向上的求解最优值3

0-1背包问题自底向上的求解最优值3

0-1背包问题根据m值矩阵得出最优解算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。4旅行商问题4旅行商问题旅行商问题最优解的结构特征最优子结构性质旅行商问题的子问题是显然重叠的假设路径c1...cn−1cn

是城市{c1,c2,...,cn−1,cn}的最短路径，取这个路径子路径c1...cn-1

必然是城市{c1,c2,...,cn-1}中从c1

到cn-1

经过其他城市一次且仅一次的最短路径。如下两个路径c1c2c3c4...cn

和c1c3c2c4...cn

都具有相同的子路径c4...cn−1cn。4旅行商问题旅行商问题最优解对应的最优值，并递归地定义最优值4旅行商问题旅行商问题最优解对应的最优值，并递归地定义最优值4旅行商问题自底向上求解最优值4旅行商问题4旅行商问题4旅行商问题自底向上求解最优值在此算法中，因TSP(c1,C,ci)中的c1

可忽略，我们用一个二维数组TP[C][ci]存储TSP(c1,C,ci)的值4旅行商问题构造最优解While循环(语句4-18)依次往最短路径添加城市，每次添加实际上就是找出下一层哪一个TSP和当前城市cˆ形成了最短回路5最长公共子序列若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

穷举法(Brute-Force)：找出X字符串所有可能的子序列(2n)；对于X的每一个子序列，判断其是否是Y的一个子序列,需要的时间为Θ(m);求max;总的时间为Θ(m2n).5最长公共子序列5最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则5子问题的递归结构3115自底向上计算c[i][j]

两个序列分别为X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>j0123456iyiBDCABA0xi1A2B3C4B5D6A7B000000000000004432214332213322213322112222112211111110003125计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。3135构造最长子序列6状态压缩动态规划集合状态压缩用二进制表示集合，之后用整型表示二进制，如旅行商问题中的TP数组空间状态压缩自底向上的方法求解最优值的过程中，压缩最优值的存储空间6集合状态压缩整数的一些基本的位操作6集合状态压缩旅行商问题的状态压缩TP[C][ci]数组通过状态压缩可以用二维数组TP[m][n−1]表示，其中m=2n−1

−1那么如何依次计算这个TP表?按行依次计算6集合状态压缩旅行商问题的状态压缩TP[C][ci]数组通过状态压缩可以用二维数组TP[m][n−1]表示，其中m=2n−1

−1那么如何依次计算这个TP表?按行依次计算6集合状态压缩旅行商问题的状态压缩需要判断一下:

j所代表的城市集合C是否包含了i所代表的城市，如果不包含，就无需做任何处理，如包含，则依次比较j集合所有下一层的TP值6空间状态压缩采用一种维度更低的数据结构来存储高维度的数据结构如在机器人行走的例子中，可以采用一维数组来存储path值从而降低空间复杂度设机器人行走按行依次计算，所以按行进行压缩6空间状态压缩6空间状态压缩同时需要第j−1列的i−1行和i行的状态值，所以，此时我们必须使用额外的变量来临时存储(i−1,j−1)的状态值6空间状态压缩按列压缩算法设计与分析贪心算法主要内容基本概念小数背包和0-1背包最小生成树霍夫曼编码1基本概念是指算法每次做选择的时是‘贪心’的，也就是尽量选择从目前看来是最好的如旅行商问中，设目前处于城市ci，那么就选择一条从ci到其他城市(还没有的城市)最短的边局部最优选择，并不一定能达到全局最优对某些问题是可以得到全局最优解，但对另外一些问题是无法获得全局最优解的1例子：钱币兑换1钱币兑换：动态规划步骤11钱币兑换：动态规划步骤21钱币兑换：动态规划步骤31钱币兑换：动态规划步骤41钱币兑换贪心算法先兑换大面额的硬币，只有在大面额的硬币无法兑换时，才兑换小面额的硬币1钱币兑换贪心算法和动态规划1贪心解是最优解吗？需要证明：贪心算法每次选出的解都属于最优解集合替换法归纳法1贪心解是最优解吗？替换法用贪心算法得出的解(x1,x2,···,xn)和最优解(y1,y2,···,yn)中的元素依次进行比较，如果元素xi

和yi

相同，则将最优解中的yi替换成xi，显然替换后的解还是最优解;如果不同，还是要将yi

替换成xi，但这时，还需要证明替换后的解依然是最优解1贪心解是最优解吗？归纳法贪心选择是正确的

问题具有最优子结构性质2小数背包2小数背包2小数背包2小数背包小数背包贪心算法的正确性证明：替换法设物品都已经按照性价比排好，并设X=(x1,x2,···,xk,xk+1,···,xn)是贪心算法得出的解，其中0≤xi≤1设最优解为Y=(y1,y2,···,yn)，其中0≤yi≤1找到第一个不相同的元素j，xj

≠yj

2小数背包2小数背包2

0-1背包贪心算法不一定能够得出0-1背包的最优解3最小生成树3最小生成树3最小生成树：Kruskal算法3最小生成树：Kruskal算法3

Kruskal算法对边排序(语句7)复杂度为O(mlogm)，第二个for循环(语句8-13)执行m次，循环体内的FIND语句(语句9)的复杂度为O(logn)，即第二个for循环的复杂度为O(mlogn)，所以算法总复杂度为O(mlogm+mlogn)=O(mlogm)3

最小生成树3

最小生成树3

最小生成树3

最小生成树：Prim算法3

最小生成树：Prim算法3

最小生成树：Prim算法4霍夫曼编码数据压缩应用网络、磁盘数据压缩减少数据传输量减少数据存储量.霍夫曼编码广泛的应用在数据压缩，可节省约20%-90%的数据量4霍夫曼编码4霍夫曼编码4霍夫曼编码定长和变长编码形成的编码树最优编码树，每个非叶子节点都有两个子节点4霍夫曼编码最优编码树的每个节点都有两个节点4霍夫曼编码前缀码：没有任何码字是其他码字的前缀编码：将每个码字连接起来即可解码需要从一串编码中解码出每个码字。简单，因为没有重复的前缀01101000，很容易解码出为单词‘bad’霍夫曼编码是前缀码4霍夫曼编码：算法流程4霍夫曼编码：算法流程因步骤3要重复n−1次，每次都需排序，复杂度为O(n2

logn)如果将A中的元素按照频率组织成最小堆，则取两个频率最低元素的复杂度为logn，插入一个合并后元素的复杂度也是logn，所以总体复杂度降到了O(nlogn)4霍夫曼编码：例子4霍夫曼编码：例子4霍夫曼编码4霍夫曼编码4霍夫曼编码算法设计与分析图算法主要内容深度优先搜索广度优先搜索单源最短路径多源最短路径1基本概念1基本概念：图的遍历图的遍历是求解图问题的基础。和树的遍历类似，图的遍历希望从图中某一顶点出发，对其余各个顶点都访问一次，但比树的遍历要复杂得多。图的任一顶点都有可能和其余顶点相邻接，因此在访问了某顶点后，可能沿着某条路径搜索以后，又回到该顶点。通常有两种遍历图的方法：深度优先搜索、广度优先搜索。他们都适合于无向图和有向图。1深度优先搜索1深度优先搜索流程1深度优先搜索流程32014v=2的DFS序列：21034遍历过程结束32014DFS思路：距离初始顶点越远越优先访问！1深度优先搜索通过对图G进行深度优先搜索，按照节点的遍历顺序会生成一棵树，称为深度优先搜索生成树，当原图为非联通时，会生成深度优先搜索生成森林每个节点标注两个属性，一个称为先序号(用predfn表示)，另一个属性称为后序号(用postdfn表示)。1深度优先搜索dfs(v)函数共被调用了n次，而每次调用dfs(v)函数都需要对节点v所连的边都遍历一次(dfs(v)函数中的for循环)，所以for循环总共执行了2m次，复杂度为Θ(2m)，所以总的复杂度为Θ(2m+n)1.1无向图深度优先搜索无向图的边根据深度优先搜索可分成两类1.1无向图深度优先搜索：例子1.1无向图深度优先搜索：例子1.1无向图深度优先搜索通过堆栈实现1.2有向图深度优先搜索有向图的边根据深度优先搜索可分成两类1.2有向图深度优先搜索：例子1.2有向图深度优先搜索：例子为何DFS用于无向图时，不存在前向边及横跨边?(1)前向边（v，w）(2)横跨边（w,v）1.3深度优先搜索：应用寻找图的关节点显然，如果G是连通的，那么在移除关节点和与其关联的边后，图变为不连通的1.3寻找图的关节点用α(v)表示某一节点v自身的层级，用β(v)表示节点能够到达的层级节点的α值可以直接用深度优先搜索的先序号表示β值则由以下几种情况决定:

1.3寻找图的关节点根节点只要判断其子节点的个数是否大于等于2即可非根节点：当要判断某一个节点v是不是关节点，需要比较节点v的α值和其子节点的β值，只要任一子节点的β大于等于节点v的α值(说明这个子节点没法到达比节点v更上层级)，则节点v为关节点，否则为非关节点1.3寻找图的关节点Predfn用于计算\alpah值和\beta值rtdegree是深度优先搜索树根的度1.3寻找图的关节点初始化节点v的alpha和beta为predfn依次访问节点v的边如果边的另一个节点没有访问（树边），递归访问，递归回来后，更新beta值，并判断是否关节点如果边的另一个节点已经访问（回边），更新beta值1.3寻找图的关节点a(1,1)，b(2,2)，c(3,3)，

d(4,4)，e(5,5)，

f(6,6)访问efb,min{f.beta,b.alpha}=f(6,2)min{e.beta,f.beta}=e(5,2),d(4,2)，c(3,2),b(2,2)(b为关节点)g(7,7),h(8,8),i(9,9),j(10,10),k(11,11)k(11,9),j(10,9),i(9,9)(关节点),h(8,1)(关节点),h(7,1),a(1,1)decbaghijkf1.3图的回路判断问题：若G=(V,E)为一个有n个顶点和m条边的有向或是无向图。要测试G中是否包含有一个回路。方法：对G施加深度优先搜索，如果探测到一个回边，那么可以判定G中含有回路；否则G中无回路。注意：如果G是连通的无向图，则不需要对G进行深度优先搜索来判定是否有回路。G无回路，当且仅当|E|=|V|-1。1.3拓扑排序给定一个有向无回路图(DirectedAcyclicGraph,DAG)G=(V,E)。拓扑排序是为了找到图顶点的一个线性序，使得：如果(v,w)∈E,那么，在线性序中，v在w之前出现。我们假设在DAG中只有唯一一个入度为0的顶点；如果有一个以上的顶点入度为0，可以通过添加一个新的顶点s，然后将s指向所有入度为0的顶点，这样s就成为唯一一个入度为0的顶点。decbafgabdcefg1.3拓扑排序拓扑排序的实现：从入度为0的顶点开始，对DAG实施深度优先搜索。遍历完成后，计数器postdfn恰好对应于一个在DAG中顶点的反拓扑序得到拓扑序：在DFS算法中恰当位置增加输出语句，然后将输出结果反转。在DFS算法中恰当位置增加顶点入栈操作，然后依次取栈顶元素输出。1.3拓扑排序decbafgdecbafgssdcbafge86735214abcedfg1.3

网络页面检索深度优先搜索是一种在开发爬虫早期使用较多的方法优点是能遍历一个Web站点或深层嵌套的文档集合；缺点是因为Web结构相当深,，有可能造成一旦进去，再也出不来的情况发生。主要内容深度优先搜索广度优先搜索单源最短路径多源最短路径2广度优先搜索2广度优先搜索v=2的BFS序列：21340遍历过程结束3201432014BFS思路：距离初始顶点越近越优先访问！2广度优先搜索采用队列Bfn表示访问顺序算法复杂度2.1无向图广度优先搜索无向图的边根据深度优先搜索可分成两类2.1无向图广度优先搜索：例子2.2有向图广度优先搜索2.2有向图广度优先搜索为什么有向图的BFS中不会出现前向边1.前向边(Forwardedges)－在迄今为止所构建的搜索生成树中，w是v的后裔，并且在探测(v,w)时，w已经被标记为”visited”,则(v,w)为前向边。2.既然要w是v的后裔，那么可以断定，w所在层较v所在的层要低；另一方面，广度优先搜索生成树是逐层产生的，即后裔顶点总是在祖先顶点之后访问2.3有向图广度优先搜索：应用假设目前需要对节点v的邻节点实行入队列，则这些要进入队列的节点的最短距离(设w.dist)就是节点v的最短距离(设v.dist)加1，即w.dist=v.dist+1

算法复杂度主要内容深度优先搜索广度优先搜索单源最短路径多源最短路径3单源最短路径3.1单源最短路径：Dijkstra算法3.1单源最短路径：Dijkstra算法在此算法中，设置两个集合X和Y，其中X用于存放已经加入到树中的节点，Y用于存放还未加入到树中的节点每个节点设置两个属性v.dist和v.prev

用于存放源节点到此节点的路径长度(一旦此节点加入到树中，此长度为最短距离)和此节点的在树中的父节点(用于最短路径计算)采用堆，复杂度为：3.1Dijkstra算法：例子3.1Dijkstra算法3.1Dijkstra算法3.1Dijkstra算法3.2Bellman-ford

算法当图中存在权重为负的环时，某些点之间就不存在最短路径，而Dijkstra算法是无法得出不存在最短路径结果的Bellman-Ford算法当图存在最短路径，算法返回最短路径，否则，返回false松弛操作

3.2Bellman-ford

算法3.2Bellman-ford

算法Bellman-Ford算法3.2Bellman-ford

算法算法中第一个for循环(语句4)共执行了n−1次，嵌套内的for循环(语句5，松弛操作)共执行了m次，所以复杂度为O(nm)。第二个for循环(语句11)共执行了m次。总复杂度为O(nm)3.2Bellman-ford

算法：例子3.2Bellman-ford

算法：例子3.3

SPFA

算法SPFA算法全称是最短路径快速算法(ShortestPathFasterAlgorithm)，它是对Bellman-Ford算法的改进在每轮松弛的过程中，我们保留那些d值更新过的节点，而在下一次松弛时，仅仅需要对这些节点为起始节点的边进行松弛即可3.3SPFA

算法算法开始时，先将节点v0

进入队列每次从队列中取一个节点(语句6)，并对这个节点为起始节点的所有边进行松弛在松弛的过程中，如果对应的节点d值发生改变，且节点并不在队列中，则此节点进入队列(语句8到11)节点进入队列的次数达到n次，说明节点被松弛过n次，算法返回False，说明图G存在权重为负的环。3.3SPFA

算法复杂度：SPFA算法在最坏的情况是和Bellman-Ford算法一样的，也就是O(mn)。SPFA算法最好的情况为Ω(n)设图为随机图形，则任意节点相连边的条数的平均值为m/n(也就是算法for循环执行m/n

次)，每个节点进入队列的平均值为k次(k是一个常数，在稀疏图中小于2)，即while循环执行kn次，所以算法的平均复杂度为O(m/n∗kn)=O(