资料https://mooc1.chaoxing.com/mooc-ans/coursedata?classId138902371courseId260345163type1utsenc74091711251f6f13a8b4c1f2360f0c3ccpi337151807openc0ae2f0ec24f98f30a68f4eec7c043ed3写在前面算法分析的基本步骤是 执行的频次有多少每次执行的开销是多少。比较复杂度区分理论复杂度和实际复杂度实际复杂度包括额外空间开销等【比如当数据量较小的时候用插入排序而不是归并需要递归额外空间开销等在CPU上执行更慢小数据上】stable or notstable插入归并计数LSD基数not stable堆排序67Intractability难解性PNPBrute-force search:暴力求解tractable可解的Intractable难解/不可解概念上理解即可不需要深入理解bipartite graph 的 perfect matchingdef边独立Disjoint Edges如果两条边没有共同的端点就称它们是独立的。匹配Matching图中一个任意两条边都没有共同端点的边集合。这意味着在匹配集合里任何一个顶点最多只能连接一条边即没有顶点被“脚踩两只船”。完美匹配Perfect Matching在匹配的基础上要求所有顶点都必须被连上即没有任何一个顶点被“剩下”。【本质是这样一个边的集合P满足没有点被剩下没有点同时连接着P中的多条边】找一个数的一个因子nontrivial factordifficlut误区统计是基于占用的比特位来计算的SAT布尔可满足性问题问题定义 (Search Problem)给定一个布尔方程组a system of boolean questions寻找一组使整个方程组都为真true的真值指派 (Satisfying Truth Assignment)。如果根本不存在这样的组合则报告无解。多项式时间定义 an^ba,b are constant常用复杂度及其英语注意nlogn也是poly2^n不是65Randomness划分随机的确定的算法随机性和stable是什么关系是两个完全不同的概念不stable的算法也可以是确定性的因为随机性必须要有概率、有shuffle这样的操作例子下面讲的算法除了随机快速排序pivot划分成左右两个子数组随机选择所以是随机的之外都是确定性算法uniform distribution:均匀分布Knuth shuffle随机排序的实现在这个过程中数组被切分为两部分左边是已经洗牌完毕的区域右边是还未处理的原始区域。每次迭代算法都把右边区域的第一个元素随机插入到左边已洗好的区域中。对比LVMC拉斯维加斯结果绝对正确但耗时看运气。特性拉斯维加斯算法 (Las Vegas)蒙特卡洛算法 (Monte Carlo)正确性100% 绝对正确可能出错概率可控运行时间随机、不固定平均很快最坏很慢绝对固定通常非常快核心关注点怎么用随机性规避最坏时间复杂度怎么用随机性在有限时间内逼近答案典型例子随机化快速排序 (Quicksort)、Quickselect之前作业里的渗透阈值模拟 (Percolation)13_45DynamicProgramming动态规划memoization动机问题解决过程中存在overlapping重复计算【重叠子问题】第一步确定什么是子问题或者说dp[i]代表什么状态转移从dp[n-x]得到dp[n]转移的方式很多包括但不限于加减乘除、min-max操作tip在构造状态转移方程的时候可以大胆假设dp[n-x]已经求好了把他当成已知条件专注于在dp[n-x]已经求好这一条件下的状态转移。边界处理最小子问题的默认值具体实现还要考虑3️⃣确定子问题的计算顺序 (Determine the subproblem order)核心动作决定是自底向上Tabulation填表还是自顶向下。如果是填表必须严格保证在计算当前状态时它所依赖的所有子状态都已经全部计算完毕。4️⃣计算最优值并缓存结果 (Compute optimal values while caching results)核心动作真正执行计算。Memoization (记忆化搜索)自顶向下递归查表防止重复计算。Tabulation (迭代填表)自底向上循环直接顺序推导。考虑回溯很多时候我们不仅需要最大价值比如 3天 或 50元还需要知道具体怎么凑出来的比如具体走哪条路、选了哪些物品。这需要用到Backtracing (回溯)。斐波那契数组递归实现归并实现线性时间常量空间只维护fg两个变量过程演示以 n5 为例 | 迭代次数 | f当前项 | g下一项 | |----------|-------------|-------------| | 初始 | 0 | 1 | | i0 | 1 | 1 | | i1 | 1 | 2 | | i2 | 2 | 3 | | i3 | 3 | 5 | | i4 | 5 | 8 |上图下方进一步优化【没有重点讲】房子喷漆问题题目给定一排n栋黑色房子每栋房子i粉刷成橙色可以获得利润profit(i)约束条件是不能粉刷相邻的两栋房子目标是最大化总利润。动态规划方法推导所有合法方案的可能性推导斐波那契数列变体不能粉刷相邻房子的方案数是 n 的指数级O (2ⁿ)增长极快。递归完成之后回溯找零钱问题【下面的选项B就是最经典的解法】动态规划可以保证全局最优但是贪心法不能保证动态规划在最短路径中的利用【DAG最短路径算法】由于 DAG 没有环因此我们可以先对图进行拓扑排序得到一个节点序列保证所有边u→v中u排在v前面。 进行拓扑排序的意义在于在计算distTo(v)时所有v的前驱节点u的distTo(u)都已经计算完成无需回溯。1️⃣标准但构建反向表比较繁琐2️⃣更简单实现特性Dijkstra 算法DAG 最短路算法核心驱动机制贪心策略每次从优先队列里挑当前距离最小的节点。严格遵循拓扑排序的顺序不需要维护优先队列。负权边支持❌ 无法正确处理负权边。能完美支持负权边只要无环即可。时间复杂度$O(E \log V)$使用二叉堆。$\Theta(E V)$线性时间效率极高。PS最长路径算法可轻松转化得到动态规划问题中的求最值规问题约到DAG最短路径问题本质还是要确定dp[i]的意义然后列出状态转移方程状态转移一般规约思路最短路径问题-最值求解问题图的边权-求最值的对象Seam Carving【图像缩放技术】动态规划DP在计算机视觉领域最精妙、最著名的实际应用之一智能图像缩放Content-aware resizing也被称为Seam Carving缝隙裁剪算法。算法核心如何把它映射成一张 DAG为了找到那条“最不重要”的缝隙算法直接把整张图片看作了一张网格图Grid Graph节点Vertices像素点图片的每一个像素 $(x, y)$ 就是图中的一个节点。边Edges向下的 3 种选择为了让裁剪出的缝隙从上到下保持连续不能这里挖一个像素那里挖一个像素否则画面会断裂算法规定每一个像素只能连向它正下方、左下方、右下方的 3 个邻居像素。SWSouth-West左下SSouth正下SESouth-East右下这构成了天然的有向无环图DAG因为边永远从上指向下绝不可能往回指。点权/边权Weight“能量函数Energy Function”怎么衡量一个像素“重不重要”看它周围的颜色变化剧烈程度通常利用 Sobel 算子求梯度。如果一个像素和周围像素颜色差异极大比如衣服和背景的交界处、人的五官说明它是边缘/重要信息能量值很高。如果一个像素和周围基本一样比如大片的蓝天、白墙说明它是冗余信息能量值很低。12_55【需要听老师讲题没弄懂】RLERLE是一种针对连续重复数据的无损压缩算法核心逻辑是把「连续重复的比特」用「重复次数 数据值」的方式来表示。新的编码长度取决于最大连续出现的长度压缩率 16/40 40%重要例题理解为什么要留一种编码作为“分隔符”模式串查找SA思想对所有后缀数组排序关注其中前缀部分等于P模式串的哪些因为整体经过排序所以他们前缀相同的肯定分布在一块SA就是要找到这个区间的左边界和右边界这个区间内就是前缀为P的。SA[s]存的是在后缀数组中排序为s的后缀所对应在T中的真实下标spst是利用二分法找左边界过程中的子区间的左右边界epet是利用二分法找右边界过程中的子区间的左右边界Algorithm SASearch(P, SA, T) // T: 长度为 n 的文本串, P: 长度为 m 的模式串 // SA: T 的后缀数组 1. sp - 1, st - n 1 找左边界 2. While sp st do 3. s - floor((sp st) / 2) 4. if P T[SA[s], SA[s] m - 1] 5. then sp - s 1 6. else st - s 7. ep - sp - 1, et - n 在剩余区间中找右边界 8. While ep et do 9. e - ceil((ep et) / 2) //ceil就是向上取整函数 10. if P T[SA[e], SA[e] m - 1] 11. then ep - e 12. else et - e - 1 13. return (sp, ep)Analysis输入变量中T是原文本P是待查找的模式串SA是已经按字典序排好序的后缀数组。因为SA是严格有序的所以原串中所有以P为前缀的后缀在SA数组里一定会紧紧挨在一起形成一个连续的区间[sp, ep]。整个算法的核心机制就是跑两次二分查找分别锁定这个区间的左右边界。1. 寻找左边界Line 1-6目标找到第一个以P为前缀的后缀的索引sp(Start Pointer)。机制在[1, n1]区间内二分。每次取中点s提取该后缀的前 $m$ 个字符与P进行字典序比较。如果P字典序更大第4行说明匹配项在右侧左指针推进sp - s 1否则说明目标在当前位置或更左侧右边界收缩st - s。最终sp会精准停在匹配区间的起始位置。2. 寻找右边界Line 7-12目标找到最后一个以P为前缀的后缀的索引ep(End Pointer)。机制在[sp-1, n]区间内二分。因为左边界已经确定为sp所以搜索起点直接复用。精妙之处第9行在计算中点e时使用了向上取整ceil。这里设计很精妙由于我们要找的是右边界当P刚好等于目标前缀时第10行左指针会直接跃迁到eep - e。如果向下取整当ep和et只差 $1$ 时会陷入死循环使用ceil完美规避了这个问题。如果不匹配说明找过了头右指针往回缩et - e - 1。我们可以用如下结构直观理解这两次二分的作用域SA 数组下标 对应的后缀 (假设 Pab) ------------------------------------ ... | ... [sp - 1] | aa... - 字典序小于 P [sp] | aba... - 第一段二分找到的左边界 ... | abb... [e] | abc... - 第二段二分游标在区间内跳跃 ... | abz... [ep] | abz... - 第二段二分找到的右边界 [ep 1] | ac... - 字典序大于 P ... | ...Effect算法最终返回一个元组(sp, ep)。这个返回值直接框定了所有成功匹配的后缀范围。如果sp ep说明文本T中根本不存在模式串P如果sp ep那么P在原串中出现的总次数就是ep - sp 1。通过这种两次二分的隔离机制无论P在原文本中出现了多少次单次搜索的时间复杂度都被极其稳定地限制在了 $O(m \log n)$完美利用了后缀数组的预处理价值。#include iostream #include string #include vector using namespace std; // 核心函数在文本 T 中利用后缀数组 SA 搜索模式串 P pairint, int SASearch(const string P, const vectorint SA, const string T) { int n T.length(); int m P.length(); // 1. 寻找左边界 (Start Pointer) int sp 0, st n; // C 为 0-index搜索区间为 [0, n) while (sp st) { int s sp (st - sp) / 2; // 默认向下取整 // 提取后缀的前 m 个字符如果后缀长度不足 msubstr 会自动截取到末尾 string suffix_prefix T.substr(SA[s], m); if (P suffix_prefix) { sp s 1; } else { st s;//当Psuffix_prefix时默认改区间右边界st从而保证最终收敛到全局左边界 } } // 2. 寻找右边界 (End Pointer) int ep sp - 1, et n - 1; while (ep et) { // 向上取整的整型实现加上 1 使得偏向右侧中点 int e ep (et - ep 1) / 2; string suffix_prefix T.substr(SA[e], m); if (P suffix_prefix) { ep e; } else { et e - 1; } } return {sp, ep}; }11_51StringSorts 20后面是自学的索引计数排序计数排序是一种非比较排序它的时间复杂度是O(n k)特别适合固定长度的整数数据这也为后面的LSD打下了基础统计频次开一个计数数组统计每个数值出现多少次求前缀和把计数数组变成「每个值最后应该排在哪个下标位置」回填这里的描述和课件相反课件是正序从原数组从后往前遍历按前缀和给的位置放元素放一个就前缀和减一保证稳定。LSD 基数排序从右向左逐字节地进行排序因此取R 2562^8对每字节的内部排序用计数排序这个方法复杂度是On256所以总共的时间复杂度是 字节数*n优势LSDLeast Significant Digit基数排序特别适合固定长度的整数数据本质上是内部的计数排序特别适合。对于 32 位整数它只需执行约 4 次计数排序每次处理 8 位注意LSD只是强调了排序的顺序从右向左排但是对每一位可以用任意的stable算法来进行排序。正式是用计数排序来操作MSD对比LSD 是从右往左、一轮轮处理所有数据MSD 是从左往右先按最高位把数据分到不同的 “桶” 里再对每个桶递归处理下一位。这就像查字典先按首字母分成 26 个组再对每个组按第二个字母细分以此类推。和 LSD 的计数排序逻辑几乎一样但有两点关键区别它只处理当前子数组[lo..hi]而不是整个数组计数排序完成后数组按第d位分成了R个 “桶”每个桶里的元素当前位相同复杂度对于固定长度字符串总复杂度仍是O(w·n)和 LSD 一样是线性时间但在实际中MSD 会提前终止短的字符串或相同前缀的子数组平均性能可能更好对比例题关键看MSD的递归深度3way string quicksort递归处理传递参数当前排序按照哪一位d排序组内范围lo-hi按当前字符分三堆小、等、大 →小和大继续按这一位排相等的直接排下一位d复杂度10_44 Shortest Paths就是SPT讲到p40好像就没讲了PSST是生成树SPT 和 MST 关系完全两回事没有必然包含 / 等价关系先记全称SPTShortest Path Tree 最短路径树单源到所有点最短路MSTMinimum Spanning Tree 最小生成树整张图连通总边权最小车载系统属于single destinationfrom every vertex to one destination因为司机中途走错路了可以马上更新路径起点当前车辆位置随时变终点用户设置的目的地固定edgeTo[1]:到1的路径上的最后那条边方便从1回溯结论从一个起点 s 到所有节点的最短路径一定会构成一棵「有向树」绝对不会是普通图更新最短路径的过程叫做“松弛”【relaxing】松弛操作试图通过边 u→v优化从起点到 v 的最短路径。relax all edgesincidentfrom v.松弛所有从 v 出发的边。incidenttothe vertex指向这个顶点Bellman-Fold// 外层循环执行 V-1 轮i从1到G.V()-1共V-1次 //第 k 轮循环从 1 开始后可以保证所有最多经过 k 条边的最短路径都已经被算出来。 for (int i 1; i G.V(); i) // 中层循环遍历每个顶点 v for (int v 0; v G.V(); v) // 内层循环遍历顶点 v 的所有邻接边 e即对每条边执行松弛 for (DirectedEdge e : G.adj(v)) relax(e); // 执行松弛操作算法的每一轮 “松弛”本质上是在确定路径上第 k 步能到达的最远距离。第 1 轮松弛我们能找到所有只经过 1 条边的最短路径。第 2 轮松弛我们能找到所有经过 2 条边的最短路径。...第 k 轮松弛可以保证所有最多经过 k 条边的最短路径都已经被算出来。因为最短路径最多只有 V−1 条边所以我们只需要执行 V−1 轮。代码实现中的优化1️⃣如果节点 v 的最短距离 distTo[v] 在第 i 轮没有变化那么第 i1 轮完全不需要松弛 v 的任何出边。因为他一定不会带给相邻节点变化2️⃣队列实现贝尔曼福德算法要求有环可以只要环的权值之和是正的解释因为如果非正那么转一圈权值更小了永远找不到最短路径如果是非负权环那么最短路径一定不包含环不然去掉环权重更小对比迪杰斯特拉要求所有权值非负迪杰斯特拉Dijkstra 是典型的贪心算法每次从未标记顶点中选择distTo值最小的顶点v将其加入S然后松弛所有从v出发的边更新邻居的distTo和edgeTo。对比Dijkstra累加路径关心从起点走过来一共多远Prim只看单边关心连进集合最便宜的一条边类方法说明见下复杂度分析delMin的复杂度是logVd叉堆V节点的复杂度是dlogVd是常数的话就是logV类方法说明IndexMinPQ接口方法作用对应 Dijkstra 中的场景IndexMinPQ(int n)创建一个索引范围为0,1,...,n-1的优先队列初始化容量为图的顶点数 Vvoid insert(int i, Key key)将键key与索引i关联并插入队列第一次访问顶点i时插入其距离值int delMin()删除值最小的键并返回其关联的索引取出当前距离源点最近的未标记顶点void decreaseKey(int i, Key key)将索引i对应的键值更新为更小的key松弛边时更新顶点i的最短距离boolean isEmpty()判断队列是否为空判断所有顶点是否都已标记处理完成维护两个数组distTo和edgeTo【物理意义distTo[w]从s经过当前所有的已标记的点能到w的最短路径以及这个路径上离w最近的节点(edgeTo)】Dijkstra 是典型的贪心算法每次从未标记顶点中选择distTo值最小的顶点v将其加入S然后松弛所有从v出发的边更新邻居的distTo和edgeTo。这里的 “局部最优”就是 “当前离源点最近的未标记顶点”。贪心的全局最优保证不是所有贪心策略都能保证全局最优但 Dijkstra 在非负权图上可以做到。证明induction【数学归纳法】induction basedistTo[s] 0成立假设现在已标记的点成立证明新加入的点也成立一、核心区别维度SPT 最短路径树MST 最小生成树目标固定一个源点保证源到每个点路径最短不固定源点保证整棵树所有边权总和最小关注点单点到各点路径长度整张图全局总权重结构以源为根的有向 / 无向树无向连通生成树无根概念0943TreesSTMSTsquare平方square root平方根ST的三个核心性质【解题重点】Kruskal带权无向连通图贪心策略从小到大选边不构成环就选直到连通所有点。本质按边权升序排序依次加边用并查集判环。复杂度分析复杂度主要来自两部分对所有边排序 ElogE查找归并 近似常数合起来接近 OElogE开销分析ElogEPrimPrim从一个起点开始每次贪心地选「连接已选集合、权值最小的那条边」把新节点拉进来直到所有点都加入。Lazy版PrimEager对比Lazy 在visit里只是无脑把边加入队列pq.insert(e)不管好坏。Eager 在visit里做了择优判断。它维护了distTo[]数组记录每个点到 MST 的当前最小距离。如果新发现的边权e.weight()比之前记录的更小weight distTo[w]才更新队列decreaseKey。如果新边权更大直接忽略不加入队列。0904GraphPriority Queue 【底层是堆】swimsink选择关键看变化之后影响了上面父节点还是下面子节点如果让当前节点和父节点的关系变得不确定 就要swim反之与孩子节点就要sinkdelMin操作复杂度logn【其中n是堆的节点的数量】insert也是lognMergesort【第三次作业2.2】