中科大软院算法设计与分析的期末复习重点

文档是用幕布写的，上传到csdn格式有些变化，附上原文档链接：https://mubu.com/doc/14W7ECNW5bO

19级算法设计与分析期末复习重点

• 数据结构
  • 红黑树
    • 红黑树的性质
      • 1.本身是一棵二叉查找树
      • 2.每个结点要么是黑色要么是红色  
      • 3.树根结点的颜色为黑色 
      • 4.叶结点(nil)为黑色 
      • 5.如果某个结点为红色，则它的左、右孩子结点均为黑色
      • 6.  对树中任一结点，所有从该结点出发到其叶结点的路径中均包含相同数目的黑色结点  
    • 红黑树的操作及时间
      • 插入：时间复杂度O（lgn）
      • 删除：时间复杂度O（lgn）
      • 查找结点，找前驱、后继：时间复杂度O（lgn）
    • 红黑树的应用
      • 序统计树
        • 概念
          • 序统计就是在一系列数中找出最大、最小值，某个数的序值等操作。
          • 解决动态序统计问题
          • Size[x]域的定义为：以x为根的子树所包含的内部结点数(包括x本身)
          • Size[x]=Size[x.left]+Size[x.right]+1
        • 找第i个最小值操作：算法时间：O(lgn)
        • 求x的序值操作：算法时间：O(lgn)
        • 完成一次插入或删除操作：时间为O(lgn)
      • 区间树
        • 概念
          • 关键字=区间的低端点
          • 新增域int：区间的端点值
          • 新增域max：x.max=Max(x.int.high, x.left.max, x.right.max )
        • 查找操作：算法时间O(lgn)
    • 数据结构的扩张步骤
      • 1. 挑选一个合适的基本数据结构
      • 2. 决定在基本数据结构上应增加的信息
      • 3. 修改基本数据结构上的操作并维持原有的性能
      • 4. 修改或设计新的操作
    • 定理
      • 1.具有n个内部结点的红黑树高度h最多为2lg(n+1)  ，即h=O（lgn）
      • 2.黑高度：黑高度bh(x)表示从x结点出发(不包含x结点)到其叶结点路径上的黑色结点个数。
        
      • 3.令f为具有n个结点的红黑树扩张后的一个域，如果结点x的f域值仅需通过结点x、left[x]、right[x]以及f(left[x])、f(right[x])就可获得，那么插入和删除操作对树T中所有结点f值进行维护将维持O(lgn)的性能
      • 区间树的查找算法，要么返回与i重叠的某个结点，要么返回为空表示树T中未找到与i重叠的区间。
  • 二项堆
    • 二项树
      • 定义
        • 仅包含一个结点的有序树是一棵二项树称为B0树。
        • 二项树Bk由二棵Bk-1树组成
        • 其中一棵Bk-1树的根作为另一棵Bk-1树根的最左孩子(k≥0)。
      • 性质
        • 1. 有2^k个结点 ，即n=2^k
        • 2. 树的高度为k , 即k=lgn（注：二项树的高度从0开始计数）
        • 3. 深度为i处恰好有  个结点           0≤i≤k
        • 4. 根的度最大且为k，若根的孩子从左到右编号为k-1,k-2,…,1,0，则孩子i恰好是子树Bi的根。
        • 5. 一棵具有n个结点的二项树中,任一结点的最大度为lgn
    • 二项堆
      • 定义
        • 二项堆H是一个满足下述条件的二项树的集合：
        • ①H中的每棵二项树满足最小堆性质
        • ②对任意的非负整数k，H中至多有一棵二项树根的度为k（保证每一棵二项树度的唯一性）
    • 根表的性质
      • eg：head[H]------->B0-------->B2-------->B3
      • ①根表为一单链表
      • ②根表链接所有二项树的根结点
      • ③根表按照度的递增序链接
    • 二项堆的操作
      • 1. 创建空堆：算法时间O（1）
      • 2. 插入结点：算法时间O(lgn)
        • ①将待插入结点变为一个只有一个结点的二项堆
        • ②合并两个二项堆
      • 3. 合并堆H1，H2：算法时间O(lgn)
        • ① 先把两个根表合并为一个根表
        • ②合并度相同的两颗二项树。（如果有3个度相等的二项树，优先合并后两个）
      • 4. 取最小值：算法时间O(lgn)
        • 遍历根表
      • 5. 抽取最小值：算法时间O(lgn)
        • ① 把该二项树根结点移除，所有孩子形成一个二项堆
        • ②合并两个二项堆
      • 6. x减值为k：算法时间O(lgn)
        • 冒泡上升
      • 7. 从堆中删除结点x：算法时间O(lgn)
        • ①将该节点x减值为负无穷
        • ②调用抽取最小值操作。
  • Fib堆
    • Fib堆的定义
      • 1. Fib堆是一具有最小堆有序的树的集合。
      • 2. 每棵树均满足最小堆性质
      • 3. 树不要求一定是二项树
      • 4. 操作的时间分析采用平摊分析方法
    • 根表的性质
      • 1. 根表链接堆中所有树根结点
      • 2. 根表中度不再唯一
      • 3. 根表不需要按照度的递增序排列
      • 4. 根表头指针改用Min[H]表示，指向根表中具有最小值的树根结点
      • 5. 根表及每棵树的兄弟间均采用双向循环链表形式
    • Fib堆的操作
      • 1. 创建空堆 ：平摊代价O(1)
      • 2. 插入一个结点 ：平摊代价O(1)
        • ①x作为新树插入根表中
        • ②检查Min[H]头指针
        • ③新结点x的mark域置为false
      • 3. 取最小值 ：平摊代价O(1)
        • 根表头指针指的就是最小值
      • 4. 合并堆操作 ：平摊代价O(1)
        • ①合并二个根表为一个新的根表
        • ②检查头指针Min[H]
      • 5. 抽取最小值操作 ：平摊代价O(lgn)
        • ①将被删结点z的所有孩子作为新树插入到根表中
        • ②将z从堆H中删除
        • ③调整根表，合并相同度的根，重构堆并确定新的最小结点（需要额外的指针数组辅助完成）
      • 6. 减值操作 ：平摊代价O(1)
        • if x为根结点   then 减值不违背最小堆性质，只需检查min[H]指向即可
        • if x为非根结点  then 令y=p[x]，此时若key[x]<key[y]，则将x为根的子树从y上删除并插入到根表中，检查y结点
          • if mark[y]=true，将y结点删除并插入到根表
          • if mark[y]=faulse, 不进行操作。
          • if y为该树的根结点，不进行操作。
      • 7. 删除任一结点 ：平摊代价O(D(n))=O(lgn)
        • ①先减值到负无穷
        • ②调用抽取最小值操作
• 算法设计方法
  • 分治法
    • 基本步骤
      • ①分解问题(divide)：把原问题分解为若干个与原问题性质相类似的子问题
      • ②求解子问题(conquer)：不断分解子问题直到可方便求出子问题的解为止
      • ③合并子问题的解(combine)：合并子问题的解得到原问题的解
    • 适用条件
      • ①原问题可以分解为若干个与原问题性质相类似的子问题
      • ②问题的规模缩小到一定程度后可方便求出解
      • ③子问题的解可以合并得到原问题的解
      • ④分解出的各个子问题应相互独立，即不包含重叠子问题
    • 相关算法
      • 归并排序（Merge sort）
        • 步骤
          • ①divide：把具有n个元素的数组分解为二个n/2大小的子数组
          • ②conquer：递归地分解子数组，直到子数组只包含一个元素为止
          • ③combine：二二合并已排好序的子数组使之成为一个新的排好序的子数组，重复这样二二合并的过程直到得到原问题的解
        • 算法分析
          • 算法时间：最好 最坏 平均：O(nlgn)
            
      • 快速排序（Quick sort）
        • 在当前的无序区A[p..r]中任取一个元素x作为比较的基准，并用该基准将当前无序区分为左右二个较小的无序区A[p..q-1]和A[q+1..r]，使得左边的无序区A[p..q-1]中的元素均小于基准元素x，右边的无序区A[q+1..r]中的元素均大于x。
        • 算法时间：T(n) = T(q)+T(n-q-1)+ θ(n)
          • 最坏情况：T(n) = O(n2)
          • 最好情况：T(n)= O(nlgn)
          • 平均情况：T(n)= O(nlgn)
      • 插入排序（Insert sort）
        • 算法时间
          • 最坏情况：T(n) = O(n2)
          • 最好情况：T(n)= O(n)
          • 平均情况：T(n)= O(n2)
  • 动态规划（最优问题）
    • 基本步骤
      • ①描述问题的最优解(optimal solution)结构特征
        • 即：一个大问题的解是最优的，则比他稍小的子问题的解也是最优的。
        • 剪贴法证明
          • 假设这个子问题 不是最优的
          • 那么一定存在一个更优的子问题
          • 那么得到的大问题就会是更优的
          • 与大问题是最优的矛盾
          • 假设是错的，即子问题也是最优的
      • ②递归定义最优解值
      • ③自底向上计算最优解值
      • ④从已计算得到的最优解值信息中构造最优解
    • 基本要素
      • 1.最优子结构性质（必要前提）
        • 一个问题的最优解中所包含的所有子问题的解都是最优的。
          
      • 2.重叠子问题（不是必要前提）
      • 3.记忆法(Memorization)
        • 采用自顶向下计算最优解值的方法。
    • 相关算法
      • 装配线调度问题
        • f1[j]表示通过装配线1的第j个工作站的最快时间。
        • f2[j]表示通过装配线2的第j个工作站的最快时间。
          
        • 算法求解：
          
          
          
          每个单元格两个数，第一个数是从本装配线而来的花销，第二个数是从对面装配线而来的花销
          • 算法时间：O(n)
      • 矩阵链乘问题
        
        
        • 最优解构造过程：m[1,6]以3为分界点得到最少的乘法次数。然后再去找m[1,3]和m[4,6]的最佳分裂点。m[1,3]的最佳分裂点是1，m[4,6]的最佳分裂点是5
        • 算法时间：O(n3) ，空间复杂度：O(n2)
      • 最长公共子序列问题（LCS问题）
        
        
        
        PS：箭头的指向方向不唯一，也就是说最后的LCS不唯一，但是LCS长度是唯一的。
        • 算法时间：O（mn）m、n分别是两个序列的长度
      • 最优二叉查找树
        • 具有最小E[T]值（平均检索代价）的二叉查找树称为最优二叉查找树
        • 证明最优子结构性质
          
        • 算法步骤
          
          
          
        • 最优解构造过程：e[1,5]以k2作为根，左子树是e[1,1]，右子树是e[3,5]。e[1,1]以k1为根。e[3,5]以k5为根。
        • 算法时间O(n3)
  • 贪心法
    • 基本思想
      • 每次选择总是选出当前最优的解
    • 基本要素
      • 贪心选择性质的证明
        • 即本次贪心选择与剩余子问题的最优解可以构成原问题的最优解
      • 最优子结构性质的证明
    • 相关算法
      • 活动选择问题
        
        • 确定一种活动选择方案，使活动数最多
        • 依次选择最早完成时间的活动
        • 动态规划算法时间为O（n3）
        • 贪心算法时间为O（nlgn）
      • 背包问题
        • 0-1背包问题不能用贪心选择
        • 零头背包问题可以用贪心选择
      • Huffman编码
        • 树中所有叶结点均为译码字符
        • 贪心选择策略：每次挑选二个频度值最小的字符。
        • 算法时间：时间为O(nlgn)
      • 任务调度问题
        • 描述
          
          
          • 一组单位时间任务，确定一种最优调度，使总处罚最小
        • 算法步骤
          • 按处罚值从大到小排序，优先选择处罚大的任务。
        • 算法时间：O（n2）
    • 理论基础-胚的定义及相关概念
      • 胚的定义
        • 一个胚应是满足下述条件的有序对M=(S,I)
        • ①S是有穷非空集
        • ②I是S的一个非空独立子集族
        • 非空独立子集族I具有遗传性，即B独立，B的子集也独立
        • 胚的交换性
          • 若A∈I，B∈I且|A|<|B|，则存在一个元素x∈B-A，使得A∪{x} ∈I，则称M具有交换性。
      • 最大独立子集
        • 给定一个胚M=(S,I)，对于I中一个独立子集A∈I，若S中有一个元素x不属于A，使得将x加入A后仍保持A的独立性，即A∪{x}∈I，则称x为A的一个可扩张元素，当胚中的一个独立子集A没有可扩张元素时，称A是一个最大独立子集。
      • 胚中所有最大独立子集大小相等
      • 加权胚
        • 若对M=(S,I)中的S给定一个权函数w，对任意的x∈S，有w(x)>0，则称M为加权胚。
      • 最优子集
        • 使w(A)权值达到最大的独立子集A称为最优子集。
  • 三种方法的相同及不同点
• 算法分析
  • 渐进符号
    • 渐进符号
      
    • 对于任意的函数f(n)和g(n)，当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))时，f(n)=Θ(g(n))。
    • 利用极限比较函数间的增长速度
      
  • 传统分析方法
    • 计算方法
      
    • 会计算最好情况的算法时间
    • 会计算最坏情况的算法时间
      见ppt 第一节课
  • 递归算法的分析方法
    • T(n)的一般式
      
      
    • 替换法
      • 思想：首先对T(n)的解做一个猜测（可以利用主方法作出假设），然后用归纳法证明所做猜测是否正确。
      • 例题
        
    • 递归树法
      • 例题
        
      • 公式
        
        
    • Master方法
      • 对于非负递归函数T(n)=aT(n/b)+f(n)，其中a ≥1，b>1且为常数，f(n)为渐进函数，则T(n)有如下三种渐进界限：
        
        
  • 平摊分析方法
    • 基本思想
      • 平摊分析是指在某种数据结构上完成一系列操作，在最坏情况下所需的平均时间。
    • 合计法
    • 记账法
    • 势函数方法
      • 通过定义一个势函数完成对每个操作的平摊核定
      • 第i次操作的核定费用：
        
        
        
      • 势函数的验证
        
    • 相关操作
      • 栈的三种操作：平摊代价为O（1）
      • 二进制计数器的加1操作：平摊代价为O（1）
    • 动态表分析
      • 表扩张(table expansion)：
        • 发生在插入一个元素x时，此时表满没有空间存放x，所以将引起表扩张
        • 先拷贝原表到新表，再在新表中插入x
      • 表收缩（table contraction)：
        • 发生在删除一个元素x后，表中元素个数小于某个设定值时，引起表收缩
        • 先在原表删除x，再把剩下的元素拷贝到新表
      • 自然策略
        • 表满时插入一个元素(α=1)，此时表扩张一倍
        • 表半满时删除一个元素(α=1/2)，此时表收缩一半
      • 改进后的策略
        • α=1时，插入一个元素表扩张一倍
        • α=1/4时，删除一个元素表收缩一半
      • 定义势函数
        
• 算法正确性分析
  • 循环不变式方法
  • 贪心选择方法
  • 归纳法
• 最大流
  • 流、流网络定义
    
    • 图a是一个流网络，是一个带权有向图，权值代表两个顶点之间的容量，该容量值非负。
    • 图b是含有一个流的流网络，每条边上的标注f（u，v）/c（u，v）含义是：流量/容量。
      • 容量约束：流量值≤容量值
      • 反号对称：f(u,v)= -f(v,u)
      • 流守恒：除了源点和汇点，流网络中的每一个顶点，流入的流量等于流出的流量，净流量为零。
      • 网络流量值=流出源点的流量总和=汇入汇点的流量总和，记为|f|
  • Ford-Fulkerson方法
    • 解决的问题：如何根据一个流网络，求解出流网络中的最大流。
    • 算法过程:
      
    • 算法时间：O（E|f*|）,f*是流网络的一个最大流
  • 剩余网络
    • 剩余网络就是在流网络中除去某个流后，所有剩余容量(residual capacity)组成的网络
    • 对于给定的流网络G=(V,E)以及流f，则Gf(V,Ef)是相对与流f的剩余网络。
    • 原流网络中边数与剩余网络的边数满足关系：|Ef|≤2|E|
  • 剩余容量
    • 对于二个顶点u,v间的剩余容量定义为：cf(u,v)=c(u,v)-f(u,v)
  • 增广路经
    • 所谓增广路径是指在Gf中一条从s到t的简单路径 
    • 在一条增广路径P中可以增加流的最大量称为增广路径P的剩余容量
      
  • 截
    • 流网络的截(S,T)是顶点V的一种划分，S∪T=V
    • 通过截的流=流出总正流－流入总正流
    • C(S,T)：截(S,T)的容量，即从S到T的容量之和。
    • 最小截：所有截中容量最小的截
    • 穿越截(S,T)的净流f(S,T)=|f| （网络流量值）
    • 如果f是源为s汇为t的流网络G中的一个流，那么以下条件相等：
      
    • 流网络的任意流f的值不能超过流网络中任意截的容量。
      • 推论：流网络的最大流=最小截的容量
  • 相关算法及时间
    • Edmonds-Karp算法
      • 是Ford-Fulkerson方法的一种具体实现
      • 算法时间：O(VE2)
    • 最大二分图匹配(Maximum Bipartite Matching)
      • 匹配
        • 图中所有顶点的度只有0或1，这就叫做对该无向图G=(V,E)的一个匹配。
        • 最大匹配，就是匹配图中，边数最多的一个匹配
      • 二分图
        • 把顶点集V划分为二个不相交的子集合L和R，L和R的内部没有边相连，所有的边都用来连接L和R，这样的图就是二分图。
      • 最大二分图匹配
        • 二分图中具有最多边的匹配称为最大二分图匹配。
      • 求二分图的最大匹配问题
        • 算法时间为O(VE’)=O(VE)