1. 算法课到底在教什么从“北邮算法课笔记”说开去如果你正在翻看一份来自某高校算法课的笔记大概率你面对的不是零散的代码片段而是一整套从复杂度分析到图论、动态规划、贪心、分治、回溯的完整知识体系。这类笔记之所以在技术圈里反复被传阅核心原因只有一个算法课讲的是“怎么把一个问题拆成可计算的步骤”而这恰恰是面试、竞赛、工程优化三件事的共同底层能力。我自己前前后后整理过三版算法笔记也帮身边不少同学做过考前突击和面试复盘。踩过的坑很一致第一版抄板书抄完看不懂第二版抄代码抄完不会写第三版才想明白算法笔记真正要记的不是代码本身而是“这个算法为什么成立、什么时候用、边界在哪、复杂度怎么算”。这份“北邮算法课笔记”如果只停留在记录伪代码那它的价值会打对折但如果把它当成一份可复现的学习路径图它能帮你省下至少两三个月的盲目刷题时间。这篇文章适合三类人正在上算法课、需要把课堂内容转化成自己能用的知识体系的学生准备技术面试、想把常见算法题型系统过一遍的求职者以及写了几年代码、但遇到性能瓶颈时只会“加缓存”的工程师。我会围绕这类算法笔记的整理逻辑、核心知识点拆解、实操复现方式、常见踩坑点四个方向展开尽量把“笔记里没写清楚但实际很重要”的部分补上。2. 算法笔记的整体设计思路为什么不能只抄代码2.1 笔记的三种层次与对应价值我观察过很多人的算法笔记大致可以分成三个层次。第一个层次是“板书搬运”把老师写的定义、定理、伪代码原样抄下来。这种笔记的优点是完整缺点是脱离课堂语境后几乎无法独立阅读因为你不知道哪个条件是重点、哪个推导是考点。第二个层次是“代码仓库”每道题附一份可运行代码配上输入输出样例。这种笔记适合复习具体题目但题目一换就失效因为缺少对算法思想的抽象。第三个层次是“决策手册”针对每一类问题记录识别信号是什么、候选算法有哪些、各自复杂度如何、边界条件怎么处理、常见变形有哪些。这种笔记才是真正能带进考场和面试现场的东西。提示如果你手里的算法笔记还停留在第一层不要急着补代码先给每个算法补一行“什么情况下优先考虑它”。这一行往往比二十行代码更值钱。2.2 为什么按“问题类型”组织比按“算法名称”组织更有效大多数教材是按算法名称来分章的排序、查找、图论、动态规划。但实际解题时你面对的是一个具体问题而不是一个算法名字。所以我在整理笔记时会把结构反过来先列问题类型再挂载算法。比如“最优化问题”下面挂动态规划和贪心“状态转移问题”下面挂动态规划和记忆化搜索“连通性问题”下面挂并查集和图的遍历。这样组织的好处是当你拿到一道新题时第一反应是判断它属于哪类问题而不是回忆自己背过哪些算法名字。这种组织方式还有一个隐性收益它能帮你发现算法之间的重叠。比如最短路径问题Dijkstra、Bellman-Ford、Floyd-Warshall 三个算法分别对应不同的边权条件和图规模放在一起对比记忆比分开背要牢固得多。我在笔记里专门做了一张对照表把每个算法的适用条件、时间复杂度、空间复杂度、能否处理负权边、能否处理负环列清楚复习时只看这张表就能快速回忆。2.3 复杂度分析必须放在最前面而不是附录很多人的笔记把复杂度分析放在最后当补充这是本末倒置。复杂度分析是算法课的“语法”不懂语法就没法判断一个算法能不能用。我在笔记的第一章永远留给复杂度大O的定义、常见复杂度量级的增长速度对比、主定理的三种情况、摊还分析的基本思路。这些内容看起来抽象但它们是后面所有算法分析的脚手架。举个具体例子为什么快速排序平均复杂度是O(n log n)最坏是O(n²)如果你不理解递归树和期望分析就只能死记结论。但如果你在笔记里画过递归树知道每一层的划分代价是O(n)、平均划分深度是O(log n)这个结论就是自然推出来的。我在笔记里给每个递归算法都配了一张递归树草图标注每层的代价和层数这样复杂度就不是背出来的而是算出来的。3. 核心知识模块拆解从数据结构到算法范式3.1 基础数据结构数组、链表、栈、队列、哈希表这部分看起来简单但恰恰是面试和工程中最容易出问题的地方。我在笔记里对每个数据结构都记录了四个维度底层存储方式、核心操作复杂度、典型应用场景、常见陷阱。以哈希表为例底层是数组加链表或开放寻址平均查找O(1)但最坏情况会退化到O(n)。典型应用是去重、计数、缓存常见陷阱是哈希函数设计不当导致冲突集中以及扩容时的重新哈希开销。注意很多人记哈希表只记“O(1)查找”但实际工程中哈希冲突和扩容才是性能杀手。我在笔记里专门记了一条如果键的分布不均匀考虑加盐或换哈希函数不要盲目相信平均复杂度。链表部分我重点记了“哨兵节点”技巧。单链表删除节点时如果没有哨兵需要单独处理头节点代码会变得很啰嗦。加一个虚拟头节点后所有删除操作统一处理这是我在实际写代码时反复受益的一个细节。栈和队列部分则重点记了“单调栈”和“单调队列”这两个变形它们在滑动窗口最值、下一个更大元素等问题里出现频率极高。3.2 树与图遍历、最短路径、最小生成树树和图是算法课的重头戏也是笔记最容易记乱的部分。我的做法是把树和图分开记但用同一套遍历框架串联。树的遍历有前序、中序、后序、层序四种图的遍历有深度优先和广度优先两种。表面上看是六种遍历但本质上只有两种深度优先和广度优先。前中后序只是深度优先在二叉树上的不同访问时机。最短路径部分我在笔记里做了严格的分类讨论。单源最短路径且无负权边用Dijkstra配合优先队列复杂度是O((VE) log V)。单源最短路径且有负权边用Bellman-Ford复杂度O(VE)还能检测负环。多源最短路径且图规模小用Floyd-Warshall复杂度O(V³)代码极简。这个分类逻辑比单纯背算法名字有用得多因为面试时面试官往往会故意给一个带负权边的图看你会不会错误地选择Dijkstra。最小生成树部分Prim和Kruskal的区别我记了一句话Prim适合稠密图Kruskal适合稀疏图。Prim从一个点开始不断扩展复杂度O(V²)或O(E log V)Kruskal按边排序后并查集合并复杂度O(E log E)。实际做题时如果边数远小于V²优先Kruskal如果边数接近V²Prim更稳。3.3 动态规划状态定义、转移方程、边界处理动态规划是算法课里最难教也最难学的部分。我在笔记里把DP拆成四步定义状态、写转移方程、确定初始化、确定遍历顺序。这四步里状态定义是最关键的也是最容易出错的。一个好的状态定义应该满足“无后效性”即当前状态一旦确定后续决策不受之前如何到达该状态的影响。以背包问题为例0-1背包的状态定义是“前i个物品、容量为j时的最大价值”转移方程是“选或不选第i个物品取较大值”。完全背包的状态定义类似但转移方程里“选第i个物品”后仍然可以继续选所以遍历顺序变成正序。这个正序和逆序的区别我在笔记里用一句话总结0-1背包逆序遍历容量完全背包正序遍历容量。这句话帮我省下了大量推导时间。提示DP的边界处理往往比转移方程更容易出错。我在笔记里要求自己对每个DP都写出“dp[0]或dp[0][0]的实际含义”并且用一个小样例手动跑一遍。很多错误在手动跑的过程中就会暴露。3.4 贪心与分治适用条件与反例记录贪心算法的笔记重点不是记算法本身而是记“为什么贪心是对的”。我在笔记里对每个贪心算法都记录了交换论证或归纳证明的思路。比如区间调度问题按结束时间排序的贪心策略之所以正确是因为存在一个最优解包含最早结束的区间。这个证明思路比代码更重要因为面试时面试官经常会问“为什么这样贪心是对的”。分治部分我重点记了归并排序和快速排序的对比。归并排序是稳定排序时间复杂度稳定O(n log n)但需要额外空间快速排序不稳定平均O(n log n)最坏O(n²)但原地排序空间开销小。这个对比在工程选型时非常实用。我还记了一个细节归并排序的合并操作可以顺便用来求逆序对这是很多题目的隐藏考点。4. 实操复现如何把笔记变成可运行的代码4.1 环境准备与代码模板算法笔记里的代码要能跑起来才有意义。我建议用Python或C来复现Python适合快速验证思路C适合分析底层性能。环境上不需要太复杂一个能编译运行的单文件环境就够了。我在笔记里为每类算法准备了一个代码模板比如并查集的模板包含路径压缩和按秩合并图的邻接表模板包含加边和遍历。# 并查集模板路径压缩 按秩合并 class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return True这个模板我用了很多年路径压缩保证查找接近常数时间按秩合并避免树退化成链。笔记里我特意标注了如果只写路径压缩不写按秩合并复杂度是O(log n)两个都写接近O(α(n))α是反阿克曼函数增长极慢。4.2 关键算法的参数计算与选择过程以Dijkstra算法为例笔记里不能只写“用优先队列”还要写清楚为什么用优先队列、什么时候用普通队列、什么时候用数组。Dijkstra的核心是每次取出当前距离最小的未访问节点朴素实现是遍历所有节点找最小值复杂度O(V²)用优先队列最小堆可以把取最小值降到O(log V)总复杂度O((VE) log V)。当图是稠密图时E接近V²优先队列版本反而可能更慢因为堆操作常数大。这个取舍我在笔记里用一张表列清楚。实现方式时间复杂度适用场景注意事项邻接矩阵遍历O(V²)稠密图V较小代码简单无堆开销邻接表优先队列O((VE) log V)稀疏图V较大需处理重复入堆邻接表斐波那契堆O(E V log V)理论最优实现复杂常数大注意优先队列版本的Dijkstra会有重复入堆的问题取出节点时要判断是否已访问否则会重复处理。这个细节很多模板里没写但实际写的时候不加判断就会出错。4.3 动态规划的填表过程与调试方法DP的调试是最让人头疼的因为出错时往往不知道是状态定义错了还是转移方程错了。我的方法是先写记忆化搜索版本再改写成递推版本。记忆化搜索直接对应递归定义容易写对递推版本效率更高但遍历顺序容易搞错。两者对照能快速定位问题。以最长递增子序列为例记忆化搜索版本是“以第i个元素结尾的最长递增子序列长度”递推版本是两层循环外层遍历元素内层遍历之前的元素。我在笔记里把两个版本都写出来并标注了递推版本的遍历顺序为什么是从前往后。这个对照过程比单纯背代码有效得多。# 最长递增子序列递推版本 def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这段代码的时间复杂度是O(n²)空间复杂度O(n)。笔记里我还补充了O(n log n)的贪心二分版本但标注了“面试时先写O(n²)版本再优化”因为O(n²)版本更容易写对优化版本容易在边界上出错。5. 常见问题与排查技巧实录5.1 复杂度分析常见错误第一个常见错误是把循环嵌套的复杂度直接相乘。两层循环不一定是O(n²)如果内层循环的边界依赖外层变量实际复杂度可能更小。比如下面这段代码内层循环次数是n (n-1) ... 1 n(n1)/2仍然是O(n²)但常数是1/2。如果内层是log n次总复杂度就是O(n log n)。第二个常见错误是忽略递归调用的复杂度。归并排序的递归树有log n层每层合并代价O(n)总复杂度O(n log n)。如果只看到“递归调用两次”可能会误以为是O(n)。我在笔记里要求自己对每个递归算法都画出递归树标注每层代价和层数。第三个常见错误是混淆平均复杂度和最坏复杂度。快速排序平均O(n log n)最坏O(n²)面试时如果只说O(n log n)而不提最坏情况会被认为理解不完整。我在笔记里对每个算法都同时记录平均和最坏复杂度并标注最坏情况出现的条件。5.2 边界条件与特殊输入处理算法题出错十有八九是边界没处理好。我在笔记里整理了一份边界检查清单空输入、单元素输入、全相同元素、已排序输入、逆序输入、包含负数、包含零、溢出风险。每次写完代码对照清单过一遍能排除大部分低级错误。以二分查找为例边界条件尤其多。左闭右闭、左闭右开、循环条件是小于还是小于等于、中点计算是否溢出、更新边界时是否加一减一这些细节稍不注意就会写出死循环或漏查。我在笔记里固定了一种写法左闭右开循环条件while left right中点mid left (right - left) // 2更新时left mid 1或right mid。这种写法逻辑统一不容易出错。提示二分查找的变体非常多找第一个等于目标的位置、找最后一个等于目标的位置、找第一个大于目标的位置每种变体的边界更新都不同。我在笔记里把每种变体都写了一个模板并标注了关键区别。5.3 动态规划的状态转移排查DP出错时我通常按以下顺序排查第一状态定义是否满足无后效性第二转移方程是否覆盖了所有决策第三初始化是否正确第四遍历顺序是否保证依赖状态已经计算。这四个问题里遍历顺序最容易被忽略。以完全背包为例如果容量遍历用逆序就变成了0-1背包因为逆序保证每个物品只被选一次。这个区别我在笔记里用一句话总结逆序0-1正序完全。但这句话只适用于一维DP数组如果是二维DP数组遍历顺序又不一样。所以我在笔记里强调不要死记结论要理解为什么。5.4 常见问题速查表问题现象可能原因排查方法解决方案程序超时复杂度过高分析循环嵌套和递归深度换算法或加剪枝结果错误边界未处理用空输入、单元素测试补边界判断死循环循环条件或更新错误打印循环变量检查更新逻辑栈溢出递归深度过大估算递归深度改迭代或加记忆化答案偏小初始化过小检查dp初始值调整为负无穷或0答案偏大初始化过大检查dp初始值调整为正无穷或0这张表是我从多次调试中总结出来的放在笔记最后当速查用。实际做题时大部分问题都能在这张表里找到对应行。6. 笔记的迭代与长期维护6.1 如何给笔记做减法笔记越记越厚是常态但真正有价值的是越记越薄。我的做法是每过一个月把笔记里已经形成肌肉记忆的内容删掉只保留容易忘、容易错、需要查的部分。比如并查集的路径压缩写法写多了自然记住就不需要留在笔记里但按秩合并的细节容易忘就保留。这样笔记会越来越精炼复习时效率更高。6.2 用题目反哺笔记单纯看笔记容易产生“我都会了”的错觉实际做题时才发现漏洞。我的习惯是每做一道题如果发现笔记里没有覆盖某个细节就立刻补进去。比如做了一道“课程表”的题发现拓扑排序的入度更新容易写错就在笔记里补一条“入度减到零时入队不要提前入队”。这种从实战中来的补充比抄板书有价值得多。6.3 定期重写核心模板算法模板会随着理解加深而进化。我每隔半年会重写一遍核心模板比如并查集、Dijkstra、线段树。重写时不是照抄旧版而是凭记忆写写完再对照旧版找差异。差异处往往就是理解薄弱的地方。这个方法帮我发现过好几个隐藏的错误理解比如线段树的懒标记下推时机我之前一直记错了重写时才暴露出来。7. 从笔记到实战面试与工程中的算法应用7.1 面试中的算法考察逻辑面试考算法考的不是你会不会背题而是你能不能把一个问题抽象成已知模型。我在笔记里专门记了一节“问题转化”看到“最短”“最少”“最优”想动态规划或贪心看到“所有可能”“组合”想回溯或搜索看到“连通”“分组”想并查集或图遍历看到“区间”“覆盖”想排序加贪心。这个转化清单帮我在面试时快速定位方向而不是盲目尝试。面试还有一个隐性考察点是沟通。我在笔记里记了一条写代码前先说出思路和复杂度写完后再主动检查边界。这个习惯让面试官看到你的思考过程即使代码有小问题也能通过沟通弥补。7.2 工程中的算法优化案例工程中直接用算法课原题的场景不多但算法思想无处不在。比如数据库索引的B树本质是多路平衡搜索树缓存淘汰的LRU本质是哈希表加双向链表任务调度的优先级队列本质是堆。我在笔记里专门记了一节“工程中的算法影子”把常见系统和算法对应起来。这样复习算法时能同时理解它在工程中的位置。提示如果你觉得算法课内容离工程太远试着找一个你熟悉的系统分析它用了哪些数据结构。这个练习比刷十道题更能建立算法直觉。7.3 持续练习的节奏建议算法能力是练出来的不是看出来的。我的建议是保持每周三到五道题的节奏重点不是数量而是每道题都走完“独立思考、写代码、调试、看题解、补笔记”这个完整流程。我在笔记里记录了自己的练习轨迹发现进步最快的阶段不是刷题最多的阶段而是每道题都写笔记的阶段。因为写笔记强迫你把思路整理清楚而整理清楚才是真正的理解。最后分享一个我自己的小习惯每次复习笔记时随机抽一个算法合上笔记在白纸上写出核心思路、复杂度、边界条件和一段伪代码。写不出来就说明还没掌握回去重看。这个方法比反复阅读有效得多因为输出才是最好的输入。