1. 为什么一门算法课的笔记值得单独整理

2020年那会儿，线上课程已经非常成熟，算法与数据结构这门课几乎每个计算机相关专业都会开。但真正让我决定把整学期的内容系统整理下来的，不是课程本身有多难，而是我发现身边太多人学完就忘、考完就丢，等到准备面试或者做项目时，连最基础的动态规划都写不利索。我自己也是踩过这个坑的人，所以这篇记录不是课程大纲的复述，而是把当时课上讲的内容、课后自己补的练习、以及后来在实际场景中反复用到的部分，重新梳理成一条能走得通的路径。

算法课的核心价值不在于记住多少个模板，而在于建立一种“看到问题就知道往哪个方向拆”的直觉。这种直觉靠临时抱佛脚是练不出来的，必须经过足够多的刻意练习和复盘。我整理这份记录的目的，是让后来者能少走一些弯路，知道哪些知识点是真正的地基，哪些是锦上添花，哪些当时没听懂但后来发现极其重要的内容。

这份记录适合三类人：正在学算法课但感觉云里雾里的同学、准备技术面试需要系统复习的求职者、以及工作中偶尔需要手写算法但基础不牢的开发者。我会尽量用大白话把每个核心概念讲清楚，同时给出当时课上没讲透但实际很重要的补充内容。

2. 课程知识框架的重新拆解

2.1 复杂度分析：一切算法的度量衡

课上讲复杂度分析时，很多同学觉得这是纯理论，跟写代码没关系。我当时也这么想过，直到后来做一个数据清洗任务，写了个嵌套循环，数据量一上来直接卡死，才意识到复杂度不是考试题，是实打实的性能红线。

复杂度分析的本质是回答一个问题：当输入规模增长时，运行时间或空间以什么速度增长。大O表示法描述的是上界，也就是最坏情况下算法不会比这个更差。常见的有O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)等。这里有个容易混淆的点：O(1)不代表只执行一次，而是执行次数与输入规模无关；O(log n)通常出现在每次操作能排除一半可能性的场景，比如二分查找。

实际分析时，我习惯按三步走：先看循环结构，单层循环通常是O(n)，嵌套循环要看内外层是否独立；再看递归调用，用递归树或主定理来估算；最后看是否有隐藏的循环，比如某些语言里字符串拼接在循环中会导致O(n²)的复杂度。这个习惯帮我避开了很多性能陷阱。

注意：复杂度分析要关注最坏情况，但实际工程中平均情况往往更有参考价值。比如快速排序最坏是O(n²)，但平均是O(n log n)，实际使用中几乎不会遇到最坏情况。

2.2 线性结构：数组、链表、栈与队列的取舍

数组和链表是两种最基础的线性结构，课上讲它们的时候，重点放在增删改查的操作复杂度上。数组支持O(1)随机访问，但插入和删除平均需要O(n)因为要移动元素；链表插入删除是O(1)如果已经持有目标节点的引用，但访问需要O(n)遍历。

这个对比看起来简单，实际选型时却经常被忽略。我见过一个场景：需要频繁在中间位置插入数据，同时又要频繁按索引读取。用数组插入太慢，用链表读取太慢。这时候其实可以考虑跳表或者块状链表，但课程里通常不会讲这些，需要自己根据场景去查。我的经验是，如果插入和读取频率差不多，且数据量在万级以下，直接用数组配合批量操作往往比想象中快，因为现代CPU的缓存局部性对数组非常友好，链表的节点分散在内存中反而会导致缓存命中率低。

栈和队列是操作受限的线性结构，但它们的应用场景极其广泛。栈的典型应用包括函数调用栈、括号匹配、表达式求值、深度优先搜索的非递归实现。队列则用于广度优先搜索、任务调度、消息缓冲。这里有个容易混淆的点：优先队列不是队列，它通常用堆实现，出队顺序由优先级决定而不是先进先出。

2.3 树与图：从层次关系到网络关系

树结构是算法课的重点，二叉树、二叉搜索树、平衡树、堆、字典树、并查集都属于这个范畴。二叉树的前中后序遍历是基础中的基础，但很多人学完之后只记得递归写法，迭代写法一写就错。我的建议是至少把中序遍历的迭代版本背下来，因为它在很多场景下需要改造，比如验证二叉搜索树、找第k小的元素。

二叉搜索树的核心性质是左子树所有节点小于根，右子树所有节点大于根。这个性质让查找、插入、删除都能在O(log n)平均时间内完成，但前提是树是平衡的。如果按有序序列插入，二叉搜索树会退化成链表，复杂度变成O(n)。这就是为什么实际工程中更常用红黑树或AVL树，它们能自动保持平衡。

堆是一种特殊的完全二叉树，分大顶堆和小顶堆。堆的核心操作是插入和弹出堆顶，复杂度都是O(log n)。堆的典型应用是优先队列、堆排序、求Top K问题。这里有个实用技巧：求最大的K个元素用小顶堆，求最小的K个元素用大顶堆，因为堆的大小只需要维持K，空间复杂度是O(K)而不是O(n)。

图结构比树更复杂，因为图可以有环、可以有多个连通分量、边可以有方向或权重。图的存储方式主要有邻接矩阵和邻接表。邻接矩阵适合稠密图，判断两点是否相邻是O(1)，但空间是O(n²)；邻接表适合稀疏图，空间是O(n+e)，但判断相邻需要遍历链表。实际场景中稀疏图更常见，所以邻接表用得更多。

图的遍历分深度优先和广度优先。DFS用栈或递归实现，适合找路径、判断连通性、拓扑排序；BFS用队列实现，适合找最短路径（无权图）、层次遍历。这里有个细节：BFS找最短路径只适用于无权图，有权图需要用Dijkstra或Bellman-Ford等算法。

2.4 排序与查找：最常用也最容易翻车的部分

排序算法课上会讲很多种：冒泡、选择、插入、归并、快速、堆排序、计数排序、基数排序、桶排序。但实际写代码时，绝大多数情况直接调用语言内置的排序函数就行。那为什么还要学？因为面试会问，而且理解排序算法的思想能帮你解决其他问题。

快速排序是重点中的重点，它的核心是分区操作。选一个基准元素，把小于它的放左边，大于它的放右边，然后递归处理左右两部分。快排的平均复杂度是O(n log n)，最坏是O(n²)，但通过随机选择基准可以极大降低最坏情况出现的概率。归并排序的复杂度稳定在O(n log n)，但需要额外O(n)空间。堆排序原地排序且复杂度稳定在O(n log n)，但常数因子较大，实际运行往往比快排慢。

查找算法里，二分查找是必须掌握的。它的前提是数据有序，每次比较中间元素，排除一半的搜索空间。二分查找的边界条件极其容易写错，我自己的经验是统一用左闭右开区间，循环条件是left < right，这样不容易出现死循环或漏查。二分查找的变体很多：找第一个等于目标的位置、找最后一个等于目标的位置、找第一个大于目标的位置，这些在标准库函数里都有对应实现，但面试时经常要求手写。

哈希表是另一种查找结构，它通过哈希函数把键映射到数组下标，理想情况下查找、插入、删除都是O(1)。哈希表的核心问题是哈希冲突，解决方法有链地址法和开放地址法。链地址法把冲突的元素放在同一个桶的链表里，开放地址法则按某种探测序列找下一个空位。实际使用中，哈希表的性能取决于哈希函数的质量和负载因子，负载因子过高时需要扩容。

3. 那些课上没讲透但实际很重要的补充

3.1 递归的思维模型与栈溢出防范

递归是算法课里最让人又爱又恨的东西。爱的是它写起来简洁优雅，恨的是调试困难、容易栈溢出、性能有时不如迭代。课上通常只讲递归的定义和几个例子，但实际用起来有几个关键点需要自己补。

递归的核心是找到递推关系和终止条件。递推关系描述问题如何分解成更小的子问题，终止条件描述最小子问题如何直接求解。写递归时，我习惯先写终止条件，再写递推逻辑，这样不容易漏掉边界情况。另一个技巧是画递归树，把每一层调用的参数和返回值标出来，能直观看到是否有重复计算。

栈溢出是递归最常见的坑。每次递归调用都会在调用栈上压入一个栈帧，栈帧包含参数、局部变量和返回地址。当递归深度过大时，栈空间耗尽就会溢出。Python默认递归深度限制是1000，Java的栈大小取决于JVM配置，C++通常更小。防范栈溢出的方法有：改用迭代、增加栈大小、使用尾递归优化（但很多语言不支持）、或者把递归改成显式栈。

提示：如果递归深度可能超过几百层，优先考虑迭代实现。尾递归在Python和Java中不会自动优化，不要依赖它来避免栈溢出。

3.2 动态规划的状态定义与转移方程

动态规划是算法课里最难啃的部分，没有之一。它的核心思想是把大问题拆成重叠的子问题，保存子问题的解避免重复计算。但难就难在怎么定义状态、怎么找转移方程。

我总结了一个实用的思考路径：先确定问题的“阶段”，也就是问题可以按什么顺序分解；再确定“状态”，也就是每个阶段需要记录哪些信息才能推导出后续阶段；然后找“决策”，也就是每个状态下有哪些选择；最后写“转移方程”，描述当前状态如何由之前的状态推导出来。

以经典的背包问题为例。0-1背包问题中，每个物品只能选或不选，状态可以定义为“前i个物品在容量j下的最大价值”。转移方程是：不选第i个物品时价值等于前i-1个物品在容量j下的最大价值；选第i个物品时价值等于前i-1个物品在容量j减去第i个物品重量下的最大价值加上第i个物品的价值。两者取较大值。

动态规划的优化方向通常有两个：空间优化和时间优化。空间优化常见的是滚动数组，因为转移方程只依赖上一行的状态，所以二维数组可以压缩成一维。时间优化常见的是单调队列优化、斜率优化等，但这些属于进阶内容，课程里通常不会深入。

3.3 贪心算法的适用条件与反例

贪心算法每一步都选当前看起来最优的解，希望最终得到全局最优。它的优点是简单高效，缺点是适用范围有限。课上讲贪心时通常会举活动选择、霍夫曼编码、最小生成树等例子，但很少讲什么时候贪心会失效。

贪心算法正确的条件是问题具有“贪心选择性质”和“最优子结构”。贪心选择性质指全局最优解可以通过一系列局部最优选择达到；最优子结构指问题的最优解包含子问题的最优解。这两个条件说起来抽象，实际判断时可以用反例法：尝试构造一个小规模的反例，如果贪心策略得到的不是最优解，那贪心就不适用。

一个经典的反例是找零钱问题。假设硬币面额是1、3、4，要找6元。贪心策略会先选4元，再选1元，再选1元，共3枚硬币。但最优解是选两个3元，共2枚硬币。所以这个面额组合下贪心不成立。但如果面额是1、5、10、25这种典型货币体系，贪心就是正确的。

3.4 位运算的实用技巧

位运算在算法课里通常只占一小节，但实际刷题和面试中出现的频率很高。位运算包括与、或、异或、取反、左移、右移。它们直接操作二进制位，速度极快。

几个实用的位运算技巧：判断奇偶用n & 1，比n % 2快；交换两个数用异或三次，不需要临时变量；取最低位的1用n & -n；清除最低位的1用n & (n-1)；判断是否是2的幂用n > 0 && (n & (n-1)) == 0。这些技巧在状态压缩、位图、权限系统里经常用到。

位运算的一个典型应用是状态压缩。当状态数量不多时，可以用一个整数的二进制位表示集合。比如有8个任务，每个任务完成与否可以用一个8位整数表示，第i位为1表示第i个任务已完成。这样状态转移就变成了位运算，效率很高。

4. 从课堂练习到实际应用的转化路径

4.1 刷题策略：数量与质量的平衡

算法课结束后，很多人会去刷题平台练习。但刷题不是越多越好，我见过刷了上千题但面试依然挂掉的人，也见过只刷了两百题就拿到多个offer的人。区别在于刷题的方式。

我的建议是按主题刷，而不是按难度刷。先把一个主题的简单题刷几道，建立基本感觉；然后刷中等题，重点理解解题思路；最后挑战难题，但不要死磕，看题解理解思路也是一种学习。每个主题刷15到20道题就差不多了，关键是每道题都要复盘：为什么用这个数据结构？为什么用这个算法？有没有更优解？边界条件有哪些？

另一个重要策略是间隔重复。刷过的题过一周再刷一遍，过一个月再刷一遍。人的记忆遵循遗忘曲线，不复习的话很快就会忘。我自己的做法是维护一个错题本，记录每道题的思路、踩过的坑、以及最优解法，定期翻看。

4.2 面试中的算法考察逻辑

技术面试中的算法题不是考你背了多少模板，而是考察你的思维过程。面试官想看的是：你如何理解问题、如何分析复杂度、如何选择数据结构、如何写代码、如何测试边界情况。

回答算法题时，我习惯按这个流程走：先复述问题确保理解正确；然后问清楚输入输出的边界条件；接着说出暴力解法并分析复杂度；再提出优化思路并解释为什么更优；得到面试官认可后开始写代码；写完用几个测试用例手动跑一遍；最后分析时间和空间复杂度。

这里有个容易被忽略的点：沟通比写代码更重要。很多人拿到题就埋头写，写完了面试官也不知道你在想什么。正确的做法是边想边说，让面试官跟上你的思路。即使最后没写出最优解，清晰的思路也能加分。

4.3 工程实践中的算法应用

工作中直接用到的算法可能没有面试那么难，但场景更复杂。比如做推荐系统会用到图算法找相似用户，做搜索引擎会用到倒排索引和TF-IDF，做任务调度会用到优先队列和拓扑排序，做数据压缩会用到霍夫曼编码。

工程中应用算法有几个注意点：第一，要考虑数据规模，面试题的数据量通常很小，工程中的数据量可能大几个数量级，复杂度分析要更谨慎；第二，要考虑实际约束，比如内存限制、网络延迟、并发安全；第三，要考虑可维护性，过于复杂的算法可能难以调试和优化，有时候简单粗暴的方案反而更合适。

我自己的经验是，先把问题用最直观的方式解决，确保正确性，然后再根据性能瓶颈逐步优化。过早优化是万恶之源，这句话在算法应用上同样成立。

5. 学习资源与练习方法的个人建议

5.1 教材与在线资源的取舍

算法课的教材通常比较理论化，适合打基础但不适合快速上手。我建议配合在线资源一起看。经典的教材有《算法导论》《算法》《数据结构与算法分析》，但这些书都比较厚，适合当参考书而不是从头读到尾。

在线资源方面，可视化工具对理解算法执行过程很有帮助，比如能看到排序算法每一步的数组变化、图算法的遍历顺序。刷题平台按主题分类的题目列表适合针对性练习。视频课程适合入门，但不要只看不练，看懂了和写出来是两回事。

我的建议是：选一本教材作为主线，配合刷题平台练习，遇到不懂的概念再去找视频或文章补充。不要贪多，把一套资源吃透比泛泛浏览十套资源有用得多。

5.2 笔记整理与知识内化

整理笔记是算法学习中极其重要但容易被忽视的环节。我见过很多人刷了很多题，但知识点是散的，遇到新问题不知道怎么关联。整理笔记的过程就是建立知识网络的过程。

我的笔记结构是这样的：每个主题一个文件夹，里面包含核心概念的解释、典型题目的解法和思路、易错点总结、以及和其他主题的关联。比如“动态规划”文件夹里会有背包问题、最长公共子序列、编辑距离等经典问题的详细分析，还会标注这些问题和贪心、分治的区别。

笔记不是抄书，而是用自己的话重新组织。我习惯在笔记里写“如果让我给一个完全不懂的人讲这个知识点，我会怎么说”，这种输出倒逼输入的方式能极大加深理解。

5.3 模拟面试与代码复盘

如果学习算法的目的是通过面试，那模拟面试是必不可少的环节。自己刷题和面试时写代码是两种完全不同的体验。面试时有时间压力、有面试官看着、需要边写边解释，这些都会影响发挥。

模拟面试可以找同学互相出题，也可以用在线平台的模拟面试功能。重点不是题目做没做出来，而是练习沟通和表达。每次模拟面试后要复盘：哪里卡住了？是思路问题还是代码问题？表达是否清晰？时间分配是否合理？

代码复盘是另一个关键环节。写完代码后不要直接提交，先自己检查一遍：变量名是否清晰？边界条件是否处理？有没有冗余代码？能不能优化？这个习惯能帮你减少很多低级错误。

6. 常见误区与避坑经验

6.1 死记模板不理解原理

算法学习中最常见的误区就是死记硬背模板。比如背了快速排序的代码，但不知道为什么分区要那样写；背了二分查找的模板，但换个变体就不会了。这种学习方式在遇到新问题时完全失效。

正确的做法是理解每个算法背后的思想。快速排序的核心是分治，二分查找的核心是排除法，动态规划的核心是空间换时间。理解了思想，即使忘了具体代码，也能推导出来。我自己的检验标准是：能不能在白板上从零推导出这个算法，而不是默写。

6.2 只刷题不总结

刷题不总结等于白刷。每道题做完后至少要问自己三个问题：这道题考察什么知识点？我的解法时间复杂度是多少？有没有更优的解法？如果这三个问题答不上来，说明这道题还没真正掌握。

我建议维护一个错题本，记录每道做错或不会的题。错题本不是抄题目和答案，而是记录当时的思路、卡住的地方、以及正确的思路。定期翻看错题本，比刷新题更有价值。

6.3 忽视代码质量

很多人刷题时只关注能不能通过，不关注代码质量。变量名用a、b、c，没有注释，边界条件靠试。这种习惯带到面试中会扣分，带到工作中会埋雷。

好的代码应该具备：清晰的变量命名、合理的函数拆分、完整的边界处理、必要的注释。刷题时刻意练习这些，形成肌肉记忆，面试和工作中才能自然写出来。

6.4 追求难题忽视基础

有些人喜欢挑战难题，觉得简单题没意思。但算法面试中大部分题目是中等难度，考察的是基础知识的灵活运用。基础不牢，难题也做不出来。

我的建议是先把简单题和中等题刷透，确保每道题都能独立写出最优解，再挑战难题。难题往往需要组合多个知识点，基础扎实了，难题自然有思路。

7. 从2020到现在的持续影响

回头看2020年那学期的算法课，最大的收获不是学会了多少个算法，而是建立了一种分析问题的思维方式。遇到新问题时，我会先分析它的结构，判断它属于哪类问题，然后选择合适的工具去解决。这种思维方式在后来的学习、面试和工作中都持续发挥作用。

算法知识本身会遗忘，但思维方式会留下来。即使忘了KMP算法的具体实现，遇到字符串匹配问题时也知道有比暴力匹配更优的方案；即使忘了红黑树的旋转规则，也知道平衡树是为了解决二叉搜索树退化的问题。这种“知道有什么工具、知道什么时候用什么工具”的能力，比记住具体代码重要得多。

如果你正在学算法课，我的建议是不要只盯着考试和面试，试着去理解每个算法背后的设计哲学。分治、贪心、动态规划、回溯，这些思想不仅用于算法，也用于解决生活中的复杂问题。把算法当成一种思维训练，而不是一门考试科目，学习过程会轻松很多，收获也会大很多。

最后分享一个我至今保持的习惯：每学完一个算法，就试着用生活化的例子给别人讲一遍。比如把动态规划讲成“做计划时把大目标拆成小目标，记录每个小目标的最优方案，避免重复计算”。能讲清楚，才算真正学会。这个习惯帮我内化了很多当时觉得抽象的知识点，也让我在后来的技术分享中能更自如地表达。