我学完 INT102 这门算法课之后最大的感受不是“我会背多少种算法名字”而是终于能把散落的知识点串成一张网。这门课的内容横跨复杂度分析、排序、查找、字符串匹配、图论、动态规划、贪心、启发式搜索甚至延伸到机器学习、计算机视觉、控制算法里反复出现的核心方法。我把整门课整理成了一份《INT102 算法笔记》不按课程章节顺序而是按“解决哪类问题、怎么思考、怎么写代码”重新组织。这份笔记适合正在修算法课的学生、准备求职算法面试的人以及想从“会调轮子”进阶到“懂底层思路”的工程师。很多人问我笔记为什么值得重新整理一遍因为算法课有一个特点老师讲的时候你全懂过两周全忘。根源在于知识是跟着章节走的而实际问题是跨章节出现的。你刷题时遇到一个“跳跃游戏2”既要贪心又要维护区间边界遇到“朋友圈”关系既要并查集又要考虑图的连通性。如果笔记还是按“第3章 贪心算法”“第7章 图论”来组织你脑子里就是一个个孤岛做题时根本调不出对应的方法。所以我这份笔记的核心思路是拿“问题类型”当骨架拿“代码模板和边界条件”当血肉拿“复杂度与适用场景”当判断依据最终形成一套能直接动手的解题框架。1. 内容整体设计与思路拆解1.1 从课程大纲到个人笔记我为什么重新组织知识体系INT102 这门课本身其实已经覆盖了很全面的算法基础排序与查找、分治策略、贪心、动态规划、回溯、图遍历、最短路径、最小生成树、字符串匹配、NP 问题初步认知。这些内容如果按部就班学也能过考试但离“会用”还差一层。真实业务里不会有人告诉你“这里该用动态规划”只会给你一堆数据和需求让你自己判断。所以我做笔记时做了三件事第一把同一种思维模式的算法归到一起。比如分治和二分查找都是“缩小问题规模”我放在同一个模块下贪心和动态规划都是“多阶段决策”我会在笔记里做对比而不是分散在两个章节。第二每个算法模板都补上了“适用条件”和“边界陷阱”。课上可能只讲主流程但真正写代码时所有的 bug 几乎都出在边界上。比如二分查找里的等号归并排序的合并区间KMP 的 next 数组错位一位都是血泪教训。第三给每个算法补上了复杂度分析和场景联想。学归并排序时不仅要会写还要知道它稳定、适合外部排序也能顺手用来做逆序对计数学 KMP 时要联想到它也有 AC 自动机、字符串压缩等更高级的应用场景。有了场景联想知识才不是死的。1.2 算法到底是什么先建立正确的算法观学算法前先要搞清楚一个朴素问题“算法是什么意思”我的理解只有一句话把输入变成输出的一套有限、明确、可执行的步骤。听起来像废话但很多人一进算法课就被各种高深术语吓住反而忘了这个最朴素的定义。比如你写一个函数输入是数组输出是排序后的数组排序算法就是中间的步骤。这个步骤必须满足三个条件有限不能在极端情况下死循环、明确每一步做什么要清晰、可执行每一步都能被机器实现。这三个条件听着简单但实际写代码时经常踩快速排序在最坏情况下递归深度退化到 O(n)可能爆栈这就是“有限性”出了问题二分查找的终止条件写错可能陷入无限循环这就是“明确性”不达标。算法不是数学题它是工程问题的抽象解决方案。我每次做题前都会先问自己三个问题输入是什么输出是什么约束条件是什么比如时间限制、内存限制、数据规模把这三个问题想清楚了再谈套用什么算法。否则一上来就背模板方向反而是反的。2. 核心基础算法拆解排序、二分与字符串匹配2.1 排序算法怎么选冒泡、堆排、归并与工程内幕排序是算法课的“开场白”也是面试最常被问的基础。我笔记里保留了完整的排序家族但重点不是让你每种都手写而是让你明白它们各自的性格稳定不稳定、平均复杂度多少、最坏会不会退化、适不适合大规模数据。先看冒泡排序。它的代码特别简单但实际工程里几乎不会用因为平均和最坏复杂度都是 O(n²)。不过我很建议手写一遍因为它能直观体现“相邻比较交换”的排序思想也是很多优化思路的起点比如加一个swapped标志一轮没交换就提前结束。// 冒泡排序带提前退出优化 void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } }堆排序的核心是建堆和反复调整堆空间复杂度 O(1)时间稳定在 O(n log n)但它不稳定。归并排序稳定但需要额外 O(n) 空间。快速排序平均表现最好但最坏会退化到 O(n²)。面对这么多排序算法到底怎么选我整理了一张表算法平均复杂度最坏复杂度空间稳定性场景建议冒泡排序O(n²)O(n²)O(1)稳定教学用、n 很小选择排序O(n²)O(n²)O(1)不稳定交换次数少时插入排序O(n²)O(n²)O(1)稳定近乎有序的小数组堆排序O(n log n)O(n log n)O(1)不稳定超大数组且内存受限归并排序O(n log n)O(n log n)O(n)稳定稳定排序、链表排序、外部排序快速排序O(n log n)O(n²)O(log n)不稳定通用内排序首选计数排序O(nk)O(nk)O(k)稳定整数且范围不大基数排序O(d(nk))O(d(nk))O(nk)稳定多关键字排序工程里的排序其实是个“混合体”。C 的std::sort用的是内省排序先快速排序如果递归深度超过阈值就切换到堆排序在元素很少时改用插入排序。所以你在项目里直接sort就够了手写排序更多是为了应对面试和竞赛场景。注意比较类排序的时间下界是 O(n log n)这是由决策树模型决定的。如果你期望更快的排序必须依赖数据的额外性质比如计数排序借助整数范围基数排序借助位数维度。2.2 二分查找的边界陷阱与“除了二分还有什么”二分查找是算法笔记里最“短小精悍”的部分代码看起来只有几行但写对很难。它适用于单调有序的数据结构每次把搜索区间砍半O(log n) 的复杂度让它成为查找算法里的优等生。// 标准二分查找在升序数组中找 target返回下标找不到返回 -1 int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }这个写法里最容易被坑的是三个地方。第一循环条件到底写left right还是left right取决于你定义的搜索区间是闭区间还是半开区间我个人习惯全部用闭区间配合left mid 1和right mid - 1逻辑最不容易乱。第二mid的计算最好写成left (right - left) / 2避免left right溢出。第三退出循环之后left和right的位置关系是判断不命中还是不需要判断的关键。如果返回插入位置直接返回left就对了。“除了二分法还有什么算法”这个问题我在笔记里专门整理过。查找一个数如果数据无序、内存充足直接建哈希表 O(1) 平均复杂度如果数据存储在外面、但字段之间有大小关系可以用 B 树或 B 树如果数据是链表结构就只能顺序遍历。核心思路是没有银弹二分适合有序数组哈希适合等值匹配树表适合范围查询。你先把应用场景对齐再选算法才是正确顺序。2.3 KMP 到底在优化什么字符串匹配的智慧字符串匹配最朴素的做法是把模式串和文本串的每个位置都比一遍最坏复杂度 O(n·m)。KMP 算法通过预处理模式串的 next 数组把匹配失败后模式串的滑动量提前算好时间复杂度能降到 O(nm)。KMP 的难点不是代码本身而是理解 next 数组的含义。next[i]表示模式串P[0...i]的真前缀和真后缀的最长相等长度。每当我们匹配失败不用从头开始只需要把模式串跳到next[j]的位置继续比。vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } return next; } int kmpSearch(const string text, const string pattern) { int n text.size(), m pattern.size(); vectorint next buildNext(pattern); for (int i 0, j 0; i n; i) { while (j 0 text[i] ! pattern[j]) j next[j - 1]; if (text[i] pattern[j]) j; if (j m) return i - m 1; } return -1; }我当年记 KMP 最大的教训是混淆了“失配回退”和“暴力回退”。暴力匹配的失配是 i 和 j 一起回溯KMP 的失配只有 j 跳转i 永远往前走。抓住这一点代码就不容易写错。KMP 也是很多字符串进阶算法的基础比如 AC 自动机就是 KMP 的多模式匹配扩展。3. 从课堂到工程进阶算法的真实落地场景3.1 图论与搜索prim、匈牙利、A* 的选型思路图论是 INT102 里最实用的一部分因为现实世界里的网络、地图、社交关系都能建模成图。prim 算法解决的是最小生成树问题从一个点出发不断扩展连接当前集合与外部的最小边适合稠密图。它的兄弟是 Kruskal适合稀疏图。判断用哪个主要看边数稠密图用优先队列优化的 prim稀疏图用并查集实现的 Kruskal逻辑更直接。匈牙利算法是用来解决二分图最大匹配、最小点覆盖、最大独立集等一系列分配问题的经典方法。它的核心操作是不断寻找增广路径来扩大匹配。面试里如果你遇到“任务分配”“课程安排”这类建模成二分图的题目匈牙利算法能写出来是加分项。A* 算法和 BFS 的优缺点我笔记里也专门做过对比。BFS 是盲目式搜索老老实实按照层次往外扩展保证找到最短路径但搜索空间大A* 是启发式搜索在队列优先级里加入f g h其中g是起点到当前点的实际代价h是当前点到终点的估计代价。当h始终不大于真实代价时A* 能像 Dijkstra 一样保证最优解但通常搜得更快。选型思路很简单如果地图规模小或者要求严格最短BFS 可以如果地图大、希望节省时间A* 更合适。3.2 机器学习与计算机视觉里的算法影子很多人以为“算法”只存在于课本和真题里其实机器学习、计算机视觉、自动驾驶里的算法遍地都是。我写笔记时专门加了一章讲课堂算法如何映射到这些前沿方向。拿检测算法 YOLO 来说它本质上是在做大量密集的回归和分类背后的思想是“边界框 置信度”的搜索优化MaxxViT-v2 这类视觉分类模型核心是多尺度、局部全局注意力机制用到的也是特征选择和信息压缩的思想Sobel 边缘检测是图像处理里最经典的卷积算子它体现了“用局部算子衡量像素变化率”的微积分思想和一阶导数的离散化是同一件事SGBM 双目立体匹配算法本质上是沿着极线做动态规划把视差估计变成一个匹配代价最小化问题这一步直接用到了立体匹配里的排序和最优路径思想Botsort 多目标跟踪算法里融合了卡尔曼滤波和匈牙利匹配卡尔曼滤波负责预测下帧位置匈牙利算法负责把检测框和轨迹匹配起来其实就是一个预测-匹配-更新的循环。3dgs3D 高斯泼溅是近两年计算机视觉里特别热的方向它最经典的论文用一组 3D 高斯分布来高效表示场景然后通过可微渲染生成新视角图像。它的底层逻辑是“用参数化模型逼近真实数据分布”这个抽象能力和传统算法里的数值逼近、优化思想是一脉相承的。我建议学算法时不要只盯着刷题。遇到一个视觉项目、控制项目先把里面“数据是怎么流动的、损失函数是怎么定义、哪个模块在最小化什么代价”拆出来你会发现课堂算法全在暗处助攻。3.3 启发式算法与优化粒子群、蚁群、模拟退火、NSGA-II、EM、混合整数线性规划现实中很多优化问题没有解析解或者解空间太大直接枚举根本不可能。这时候就要靠启发式算法它不保证最优但能在可接受的时间里找到一个很好用的次优解。这类算法在课程里可能只是提了一嘴但工程里非常常见。粒子群算法的原理可以这样理解有一群粒子在解空间里飞每个粒子记住自己的历史最优位置同时共享整个群体的全局最优位置然后靠这两个信息调整飞行速度。核心公式是速度更新v w*v c1*r1*(pbest-x) c2*r2*(gbest-x)位置更新x x v。w是惯性权重影响全局搜索和局部搜索的平衡。实测下来粒子群算法对初值不太敏感但容易陷入局部最优解决办法是调大惯性权重或者引入变异。蚁群算法模拟蚂蚁通过信息素找路径的过程信息素浓度越高后续蚂蚁越容易被吸引形成正反馈。它特别适合路径规划、旅行商问题、网络路由等组合优化场景。模拟退火算法则是模拟金属降温过程温度高时允许一定概率接受更差解从而跳出局部最优温度逐渐降低最终稳定在较好解。NSGA-II 是多目标优化里的经典算法它能同时优化多个互相矛盾的指标比如成本和性能核心是“快速非支配排序 拥挤度距离”的精英保留策略。EM 算法则是处理含有隐变量问题的标准工具比如高斯混合模型聚类它只需要交替执行 E 步求期望和 M 步极大化就能一步步逼近参数原理上很优雅。混合整数线性规划MILP是运筹优化的主流模型变量一部分是整数、一部分是连续值求解器比如 Gurobi、CBC已经非常成熟很多时候做排产、调度、资源分配直接建模比写自定义贪心更稳。4. 经典思路的实战练习贪心、动态规划与剪枝4.1 贪心算法的实战跳跃游戏 2 为例贪心算法是每步都取当前看起来最优的选择希望通过局部最优达到全局最优。它不是什么时候都对但一旦适用代码往往很短很漂亮。“跳跃游戏 2”就是一个特别典型的例子。题目要求给定一个非负整数数组初始在第一个位置每个元素代表你在该位置可以跳跃的最大长度目标是到达最后一个位置问最少跳跃次数。关键思路是不要想下一步跳到哪里而是维护当前这一跳能覆盖到的最大范围。遍历当前位置能跳到的所有点不断更新这一跳能覆盖的最远距离。当走完当前覆盖范围时跳跃次数加一进入下一跳。int jump(vectorint nums) { int n nums.size(); int jumps 0; int curEnd 0; int curFarthest 0; for (int i 0; i n - 1; i) { curFarthest max(curFarthest, i nums[i]); if (i curEnd) { jumps; curEnd curFarthest; if (curEnd n - 1) break; } } return jumps; }我最初做这道题总想提前规划到某个最优落点但那样反而复杂。贪心的核心是“每一步只保证当前区间内可达性最大化”不去关心具体落在哪个位置。这个思路在很多区间问题里都通用比如会议室安排按结束时间排序然后优先选最早结束的会议就是最基础的贪心。注意贪心算法的难点其实在于证明为什么局部最优能推出全局最优。做题时可以先假设贪心策略写一版再用暴力或动态规划做小数据对拍验证。如果全部通过才能放心提交。4.2 动态规划的状态设计从斐波那契到背包动态规划和贪心最大的区别是贪心只保留一个最优状态动态规划保留一组状态然后用状态转移方程推导后续结果。课程里讲 DP 时会从斐波那契数列开始但真正难的是状态设计。设计 DP 的步骤我总结成三句话状态定义、状态转移、边界条件。以 0/1 背包为例dp[i][j]表示前i个物品背包容量为j时能装下的最大价值。状态转移是不放第i个物品就是dp[i-1][j]放就是dp[i-1][j-w[i]] v[i]两者取最大。边界条件是dp[0][j] 0容量为 0 时价值为 0。for (int i 1; i n; i) { for (int j 0; j capacity; j) { dp[i][j] dp[i - 1][j]; if (j w[i]) { dp[i][j] max(dp[i][j], dp[i - 1][j - w[i]] v[i]); } } }写 DP 最常见的错误是状态定义不清晰。如果你说不清楚dp代表什么后面的转移方程一定写不对。我建议每个 DP 题都用一句话描述“dp[i][j]的含义”多花一分钟把定义写清楚后面能省十分钟。动态规划的优化也很重要。空间上可以把二维数组压缩成一维比如 0/1 背包里倒序遍历容量完全背包里正序遍历容量时间上可以用单调队列优化多重背包、用斜率优化某些凸代价的线性 DP。这些进阶技巧不用一次全学但至少要知道 DP 不是只能暴力转移。4.3 剪枝与回溯组合算法为什么必须剪枝回溯算法相当于深度优先搜索撤销状态专门用来枚举所有可能性。组合问题、排列问题、迷宫问题、数独问题本质都是回溯。问题是直接枚举所有状态数据规模一大就超时剪枝就成了必须做的事。剪枝的核心是“去掉一定不会产生答案的分支”。以组合总和问题为例排序后如果当前元素已经大于剩余目标值后面的元素就不用再试了如果路径长度已经超过要求直接返回。这两行“看似无关紧要”的优化往往能指数级提速。void dfs(vectorint candidates, int index, int target, vectorint path, vectorvectorint res) { if (target 0) { res.push_back(path); return; } for (int i index; i candidates.size(); i) { if (candidates[i] target) break; // 剪枝条件 if (i index candidates[i] candidates[i - 1]) continue; // 去重 path.push_back(candidates[i]); dfs(candidates, i 1, target - candidates[i], path, res); path.pop_back(); } }组合算法里剪枝的常见技巧包括可行性剪枝当前路径已经非法、最优性剪枝当前结果不可能优于已有答案、重复性剪枝同一层跳过相等元素。这三种剪枝的组合使用能把很多看起来无解的问题从超时边缘救回来。4.4 分治的编码套路把大问题切成同构的小问题分治是“递归”的工程化表达拆解、解决、合并。归并排序就是最标准的分治案例先拆成两个子数组分别排序再把两个有序数组合并。合并过程需要额外空间所以归并排序空间 O(n)但它稳定还能顺手求逆序对。代码套路其实很固定void mergeSort(vectorint arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); }二分查找本质也是分治只是每次只进入一个子区间快速排序同样是分治但它的难点在 partition 函数要保证基准元素两边的划分正确。学分治时我不建议死记模板而是多练习“如何找到中点”以及“如何保证两个子问题互不重叠”。5. 避坑实录与学习心得5.1 学习算法时最常踩的五个坑与排查方法在整理《INT102 算法笔记》的过程中我把自己和身边同学的典型错误汇总成了一个小表每次做题卡住就先自查一遍常见问题典型表现排查思路边界条件错误数组越界、死循环、漏处理空数组先测最小输入、空输入、单元素输入循环变量写错快排 partition 后左右下标错位用三个元素的极端数组手动走一遍复杂度误判以为 O(n²) 能过 10^7 数据先算上限n 个数据O(n²) 最多跑 10^4 左右完全套模板模板里有某个参数没理解就硬用把模板的每一行都加注释写清含义不构造反例自己写的贪心策略在一些测试点挂掉专门写暴力解法做小数据对拍我特别想说“对拍”这个方法。学算法时怀疑自己的思路不对不要只手动想反例直接写一个暴力解比如全排列枚举和一个优化解然后随机生成小规模数据跑对比。只要发现一组数据两者结果不同就拿到了一个精确的测试用例。这个方法在学排序、贪心、动态规划时都是神器。5.2 算法流程图用图画帮助记忆很多算法如果用文字描述会显得很长但画成流程图就一目了然。我这里说的不是严格意义上的软件工程图而是自己在白纸上画“步骤分支图”。比如二分查找我会画一条数轴标出 left、mid、right然后把“mid 比 target 大”“mid 比 target 小”两个分支画出来标上谁移动。KMP 就画一个模式串滑动示意图把每个失配位置的回退过程画出来配合 next 数组连上箭头。画流程图的意义是逼自己梳理“每一个分支的出口在哪里”。很多代码 bug 是分支漏算造成的画完图基本就能发现。笔记里每一类算法都配了手绘流程复习时扫一眼图比从头看代码快得多。5.3 学完 INT102 之后还能往哪走INT102 只是算法路的起点。如果你还想深挖我建议按兴趣选几个方向数据结构进阶方向红黑树、B 树、跳表、并查集变种把底层容器彻底搞懂写业务代码时能更好选型。算法设计与分析方向摊还分析、在线算法、近似算法、随机化算法这些是研究生阶段的核心也是很多高难度面试题的后台理论。信息学奥赛信奥方向CSP/NOIP 系列赛基本就是在考察算法模板和数论、组合数学的灵活运用INT102 打底后可以直接刷信奥题目。前沿领域结合方向计算机视觉里的 3DGS、目标检测、多目标跟踪机器人里的 PID、卡尔曼滤波、路径规划推荐系统里的矩阵分解和排序学习处处都是算法的新舞台。我个人体会是学算法最忌讳“雨露均沾但浅尝辄止”。与其每道题只看一眼答案不如把一道经典题吃透把它的变种、边界、复杂度全部摸清。INT102 这门课是一个很完整的框架你真正内化的不是那些算法名字而是“拿到一个问题知道该用什么工具、怎么验证、怎么优化”的思考能力。这份《INT102 算法笔记》就是我内化过程的产物现在分享出来希望它也能帮你少走一些弯路。