算法设计与分析复习讲义

1、课程介绍sina微博 资料下载 通知116周教学 1718周复习答疑 1920考试周考试卷面 60% 考平时所讲知识点 不考编程 考前有复习题库平时成绩 40% 作业=上机实验 自选题目交十次，或大作业（需同意）上机：南海楼209 每周四下午 14:0016:00 Java 16:0018:00数据结构交作业，可在宿舍做上课出勤课程定位：计算机基础 = 编程语言 = 数据结构 = 算法 = 复杂性理论，专题方向横向扩充，纵向深入教材 参考书 做题 学习方法：编程基础是前提，自学最重要收集：面试题，算法题，编程题，智力题引论一些数学公式估计调和级数前n项 1/x积分得对数 1/x和1/(x+1)

2、所夹估计误差 前若干项精确计算，后面误差小 P10题1.7P10题1.8P10题1.9 Fibonacci数的通项：母函数，z变换计算机中的数进制转换：Dec Bin Hex Oct整数转换：Dec Int = Bin模二 任意进制带权相加：Bin Int/Float = Dec 任意进制浮点数除法：4/3转二进制 任意进制二进制的乘除法 x*3整数编码：补码浮点数编码：IEEE 754，二进制科学计数法，能表示的浮点数个数是有限的，能表示的浮点数的精度是有限的，浮点数在数轴上的分布是不均匀的。HEX 16进制编码有效数字指数实际表示名称说明符号+指数纯小数00000000000000000线

3、性区00000000000012-1022*2-52subnormal minFFFFFFFFFFFFF2-1022 *(1-2-52)subnormal max00100000000000001+0-10222-1022realmin3CB00000000000001+0-522-52eps精度，HEX 0.00000000000013FF00000000000001+0013FFFFFFFFFFFFFFF2-eps02-eps屏幕显示2.0000.40000000000000001+012屏幕显示240080000000000001+1/2137FEFFFFFFFFFFFFF2-eps10

4、23(2-eps)*21023realmax7FF0000000000000infx/07FFxxxxxxxxxxxxxNaN0/0; 一般FFF 8000000000000考虑 -0，-infMatlab演示 format long format hex format short format1 / 0 = inf0 / 0 = NaN运算时阶码调整/对齐 1/2 4+11+eps = HEX 3FF 00000000000012+eps = HEX 400 0000000000000浮点数的误差：x=1+eps, x-1 x=2+eps, x-2x=4/3-1, y=3*x, z=1-y程

5、序中的数据数组：下标指针：地址；内存看作巨大的字节数组，下标结构；首地址+偏移=实际地址本质上都是地址/指针内存，磁盘：巨大数组 段页式/扇区、簇、文件分配 碎片算法分析时间复杂度1 for ( int i = 0; i n; i + )for ( int j = 0; j (int) Math.sin( n ); j + ) foo();P11 P12法则3 P26题2.3 P26题2.4有一个时间复杂度为n2的程序，当n=103时运行了1s，当n=106时要运行多长时间？题数组顺序查找：n数组二分查找：ln(n)数组翻转两/三个有序数组合并矩阵存储矩阵的一维数组存储n2、打印三角阵的一维数

6、组存储n2/2 打印对称阵Toeplitz阵最大定长子序列和：求积分最大子序列和，不定长：n3, n2求积分，转为求最大增长式落差。注意最大子序列，起点一定是终点前的最小值，终点一定是起点后的最大值。从前往后扫描积分序列，求以当前点为终点的最大增长落差：记录迄今为止最小值，与当前值之差就是。再参见P21算法4，里面的ThisSum就是以当前点为终点的最大子序列，其清零对应在积分序列里，每次碰到迄今最小值后就清零，所以就是从迄今最小值到当前点。直接证明此算法：以ThisSum清零点分段，每段和都=0，反向积分就一定=0。所以，以当前点为终点的最大子序列，必以最后一个ThisSum清零点位起点；起

7、点再往前延伸是不会使和增大的。P28题2.12最小子序列和：考虑负数最小正子序列和：不会是要求子序列内全正数，求子序列和最小，如此取最小正数即可。应该是要求所有子序列中，和为正，最小。扫描积分序列，对每个当前元素，求前面最接近又小于当前元素。可以有。最大子序列积：考虑对数。扫描积分序列，对每个当前元素，前面按符号分两组，按当前元素的符号求正组的最大（可能不存在），负组的最大。最大公约数 GCD 欧几里德辗转相除法 a/b=q.r b/r P23最小公倍数 a/x*b/x*x=a*b/x整数幂 递归：分偶数/奇数分解 非递归：幂次写成二进制 P24P28题2.15 8次乘法算X62 2 3 5

8、10 15 30 60 62（尽量折半） 穷举搜索前n个自然数取m个不重复 数组乱序P27题2.7：每个球放入前面的盒子，证明等概率：归纳，n成立，考虑n+1时的最后一步：最后一个球放入每个盒子比例相等；前n个球的任一个，已经均匀随机放入前n个盒子；前n个盒子再以1/(n+1)的比例调入n+1号盒子，共计n/(n+1)；以n/(n+1)的比例留在原地。每个球放入后面的盒子，证明等概率：第一个球等概率，后面的球是从n个里面取n-1个，概率是均匀的，依此类推。一次多项式求值 P28题2.10有序数组中，寻找元素值=下标 P28题2.11 折半，ak找前一半判断素数P28题2.13筛素数P28题2.

9、14 估计：第n个素数，前n个自然数中素数量，时间 其中因子 素因子找多数： 首先证明，在存在严格多数的元素（主要元素，过半数的元素）的前提下，算法得到此元素。分段，m=0作为每段起点。除最后一段外，前面各段：起点元素在段内恰占一半（起点元素看作+1，其它元素看作-1，段到m=0结束）。所以，前面各段，每段内主要元素最多占一半。所以，前面总起来，主要元素最多占一半。所以，最后一段，主要元素过半。如果最后一段起点不是主要元素，矛盾。再加上验证，就是完整的算法。P28题2.19复杂且慢些。列表功能读写其它取查增删改getElementAtgetSubList(last)indexOfElement

10、indexOfSubListindexOfMaxindexOfMinaddAtaddAllAtremoveAtremoveRangesetAtlength/sizecompareTogetFirstgetLastcontainsElementcontainsSubListgetMax / getMingetRandomaddFirstaddLastremoveFirstremoveLastremoveAllremoveAllEqualsclearfillswapisEmptyequals实现ADT P31基于定长数组的列表 对应的时间复杂度基于增长数组的列表链表 单向链表 双向链表 循环链表

11、P38 静态链表 P43列表的变化：栈stack FILO P46两种实现 队列queue FIFO P58 元素循环数组循环：基于循环增长数组的双端队列 Dequeue P58题一元多项式加减乘除 P39基数排序 P41稀疏矩阵三元组 转置 乘法每行/列作为一个列表 转置 乘法十字链表：P42 转置 乘法 高效遍历每行/列学生、课程 P42多对多映射/二分网的快速互查实际设计：两个类，对象含列表括号匹配计数 多种括号 P52字符串数字表达式求值P62题3.7 涉及快速卷积P62题3.8整数次幂大整数 加减乘除P62题3.9 计算出24000是多少即可 整数次幂Josephus问题：递归 P6

12、3题3.10模拟：不论数组/链表，需定位删除，时间复杂度m*n，min(m,n)*nn个人编号0,n-1，从0号开始报数0,m-1，报数为m-1者离开，从下一个人开始重新从0开始报数。对f(n,m)，第一个离开者的编号为(m-1)%n，下一个人编号为m%n，从他开始重新从0开始报数。现在总人数n-1，从他开始从0编号的话，最终留下者编号为f(n-1,m)，对应原问题编号(f(n-1,m)+m%n)%n，化简得f(n,m)=(f(n-1,m)+m)%n，时间复杂度n反转单链表 P63题3.12P63题3.15P64题3.22a记录迄今为止最小值b 不能小于lnN，否则就可以通过此方法得到小于ln

13、N的基于比较的排序方法了P63题3.23 数组模拟内存指针树概念图 结点/节点 边 有向 无向 度树 度 根 叶 层/深度 子/子树/子孙 亲/祖先 兄弟 结点数=边数+1二叉树 左/右子 叶子数=度2数+1满（理想平衡树） 完全 平衡树/森林二叉树实现结构体+指针P66嵌套列表/广义表邻接矩阵遍历打印目录文件P67个数 总大小 平均大小 深度 最大 最小 P69二叉树 三序遍历表达式 前缀 中缀 后缀字符串算式构造表达式树：拆分 无运算优先级无括号 有运算优先级 有括号 参考P71已知其中两序求原树 证明三序遍历/深度优先遍历：递归 通用非递归广度优先遍历/层次遍历：通用非递归树的广度优先遍

14、历 深度优先遍历二叉查找树（二叉排序树）FindMin FindMax Find P74Insert P75Delete P76 P77删除结点无子结点，即叶结点：直接删除有一子：顶替有二子：改为（递归）删除左子树最大值/右子树最小值，也可以用来处理有一子的情况懒惰删除 P77随机生成的二叉查找树最坏情况下树深度/结点平均深度O(n)：递增或递减序列最好情况下树深度/结点平均深度O(ln n)：平衡树随机生成的二叉查找树，平均情况下树深度/结点平均深度 O(ln n) ： P781、任何插入序列等概率，即前n个自然数1,n的全排列；并非所有可能的树等概率，可能的树和全排列并非一一对应。2、随机

15、生成的二叉查找树所有节点深度之和为一随机变量=左子树深度和+右子树深度和+n-1。根节点深度0。3、插入序列首数就是树根，是随机的，均匀分布1,n。对某个给定的首数m，左子树所含结点即前m-1个自然数1,m-1。4、下面说明，在原问题中，若给定首数m，则左子树的所有节点深度之和就是。原插入序列是前n个自然数全排列等概率，考虑其中首数为m的序列，在这样的序列中，前m-1个自然数的每一个排列是等概率的，因为前n个自然数的全排列可以分三步产生：选择m-1个位置放前m-1个自然数；排列这m-1个自然数；排列剩下的自然数。只要其它两步确定了，中间一步总是前m-1个自然数的全排列。5、同理可说明，在原问题

16、中，若给定首数m，则右子树的所有节点深度之和就是。6、 ，其中均匀随机地取，对应取。7、 ，其中，得到，递推公式简记为8、 仿照P184推导AVL树：基本平衡的二叉查找树越平衡查找越快 O(ln n)严格平衡：极端情况下插入慢，例如末端缺一个结点，首端插入；平均情况类似B树AVL定义 P80-81AVL插入时调整：从插入节点向上找第一个不平衡节点P82-86AVL删除完整过程：插入/删除后更新路径上每结点层数信息从插入/删除节点向上找第一个不平衡节点若未找到，结束若左层数=右层数+2若左左层数=右层数+1则为LL型若左右层数=右层数+1则为LR型若右层数=左层数+2若右右层数=左层数+1则为R

17、R型若右左层数=左层数+1则为RL型assert断言查/增/删时间复杂度O(ln n)红黑树红黑树性质 注意空指针为黑插入：新结点N初始为红，记N父P，爷G，叔UP不存在 / N为根 / 空树：直接N变黑 wiki情形1P存在P黑：OK wiki情形2P红，故G存在、非空、黑，U存在U红：UP变黑，G变红；对G递归；四种形状都一样。 wiki情形3U黑NPG成之字形：N提升，成为下面情况 wiki情形4NPG成一字形：P提升变黑，G变红 wiki情形5删除：要删除某（非空）结点X。若X有2个非空儿子，则复制左儿子最大值（或右儿子最小值）Y到X，改为删除Y。所以只需讨论下面情况：要删除某结点X，

18、X有（至少）1个儿子为空。记另一个儿子为N（可能也为空）。此时，删除X即去掉X，把N上升到X处，即用N代替X。如果X红，删除后OK。如果X黑N红，删除后N变黑即OK。所以下面只需讨论X黑N黑的情况，此时删除后，N子树缺了一个黑，需要调整。对删除后的树，记N父P，兄弟S，左侄L，右侄R。由于对称性，不妨设N兄（左儿子）S弟。P不存在 / N为根：OK wiki情况1P存在，由删除前的图黑色均衡可知，S存在非空，LR存在（可能为空）S红：S提升，PS交换颜色，成为下面情况 wiki情况2，注意PLR必黑，图不准，LR可能为空S黑R红：S提升，PS交换颜色，R变黑 wiki情况6R黑L红：只看S子树

19、，L提升，LS交换颜色，成为上面情况 wiki情况5L黑P红：PS交换颜色 wiki情况4P黑：S变红，改为调整P wiki情况3伸展树了解P90-93B树系列分裂与合并 限定每个节点只有一个值：严格平衡的二叉查找树实际使用内存非常快，所以数据只要能放进内存，AVL已很快红黑树实际效率高，一般有现成类库数据大到内存装不下，数据库B树数据操作读多写少，因为大量的写操作往往批量完成（实时更新少），此时可使用快排等散列Hash原理（按某规则）排序后查找：字典，黄页 O(ln n)Hash查找：电话号码，人名Hash函数的构造散列值均匀分布手机号码后四位、末位、前四位、首位人名首字母、末字母字符串字母

20、和 P112字符串前三个字母 P112推荐Hash函数：，其中m常取31, 33, 37 P112插入 查找 删除 O(1)冲突插入时冲突的解决方法拉链 P113Java中的Object.hashCode() HashMap拉链 HashTable HashSet开放定址 P117 删除的问题线性探测 P117平方探测 P118补充：互素=数列模q，不重复地占满。若有重复，假设，其中，则含q因子，显然不能含q因子。双Hash P122大数据量re-hash太满时做 P123可扩散列 P125 均匀分布时效果好，否则索引项太多 实际中一般固定使用一个较长的hash码海量网页文件的存储与访问：对u

21、rl进行hash，hash码较长；存储文件含url；分布式存储节点；多个对外服务节点，同步含hash码=存储节点映射；访问用户增加引起对外服务节点增加；节点文件数量增加引起存储节点增加，文件存储位置发生变化，使用双映射配置文件逐步转移文件。字符串查找暴力法 JavaHash法 K.M.P.B.M.堆/优先队列定义：二叉完全树，堆序数组实现：父子节点下标公式 P134插入：末尾上移 P136删除：交换后根下移 P138初始化堆：O( n ) P141左式堆：P145左式堆合并：大根与小根右子（递归）合并（并调整根）P159题6.9aP159题6.7b排序选择排序冒泡排序插入排序P165Shell

22、排序P167 先p排序，再q排序，仍然是p排序 pq平衡排序树排序堆排序P170归并排序P173快速排序P177 小数组P181 分析P183外部排序：内部排序+多路归并桶排序P189基数排序排序的稳定性P196题7.25不稳定：选择 Shell 堆 快排解决稳定性的通用方法：增加比较字段基于比较的排序时间下界P187P196题7.3413球问题补P64题3.16f选择问题/中位数P185小数据量：排序；快速选择大数据量：外排等价关系（不相交集）像素图片的同色联通集逐行扫描的像素图片的同色联通集；老乡关系等价关系判断；等价类划分类树 数组表示 P201小树添加到大树根 P204路径压缩 P205图定义P215表示P216 结点指针 嵌套列表 矩阵拓扑排序P217可拓扑排序 无圈 = 存在结点入度0可拓扑排序 = 无圈：反证无圈 = 存在结点入度0：反证，去掉出度0的结点，构造圈无圈 = 可拓扑排序深度优先遍历 递归广度优先遍历 列表无权图单源最短路径 广度优先遍历P220有权图单源最短路径Dijkstra P225无圈图P230关键路径P230Floyd算法 原理 结果双矩阵 最短路径的存储物理方