《算法设计与分析》课件 第1章 概述

算法设计与分析参考书算法导论（原书第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),UN