1. 算法课程到底在学什么：从标题拆解核心知识版图
“2020算法课程记录”这个标题看起来平平无奇，像是一份随手记的笔记归档，但真正翻过算法课的人都知道，这四个字背后藏着一整条从数学基础到代码落地、从面试笔试到工程优化的完整链路。我当年第一次系统整理算法笔记的时候，踩过最大的坑就是“什么都记，什么都记不全”——动态规划的推导过程抄了三页纸，结果滑动窗口的边界条件反而漏了。后来复盘才发现，算法课程的核心不是把每个公式背下来，而是建立一套“看到问题就知道往哪个方向拆”的条件反射。
这份记录适合谁看？如果你是刚接触算法的新手，它能帮你把零散的知识点串成线；如果你已经刷过几十道题但总觉得不成体系，它能帮你补上“为什么这样设计”的底层逻辑；如果你正在准备技术面试，这里面的复杂度分析和边界处理思路可以直接拿去用。我个人的经验是，算法课的价值不在于老师讲了什么，而在于你课后怎么把“听懂了”变成“写得出”。
先给一个全局视角。一门标准的算法课程，通常覆盖以下几大模块：复杂度分析（时间与空间）、基础数据结构（数组、链表、栈、队列、哈希表）、树与图（二叉树、堆、并查集、图的遍历）、经典算法思想（分治、贪心、动态规划、回溯）、排序与查找（快排、归并、二分）、字符串处理（KMP、Trie）以及高级专题（位运算、数学、计算几何）。这些模块不是孤立的，比如动态规划经常要借助哈希表做记忆化，图的最短路径又依赖优先队列。我在整理笔记时习惯画一张“知识依赖图”，把每个算法标注出它依赖的前置知识，这样复习的时候就不会出现“学DP发现递归没搞懂”的尴尬。
提示：不要按教材目录顺序线性复习，按“依赖关系”复习效率至少提升一倍。先确认递归和复杂度分析过关，再碰分治和DP。
2. 复杂度分析：一切算法讨论的地基
2.1 为什么大O表示法让新手又爱又恨
复杂度分析是算法课的第一道门槛，也是最多人“以为自己懂了”的地方。大O表示法描述的是算法运行时间随输入规模增长的趋势，而不是具体跑了多少毫秒。我见过太多人把O(n)和O(2n)当成两个不同的复杂度，实际上它们都是O(n)，因为常数系数在渐进分析中被忽略了。
但这里有个实操中的坑：常数系数在工程中往往很重要。比如两个都是O(n log n)的排序算法，归并排序的常数系数通常比快排大，因为归并需要额外的数组拷贝。所以在数据量不大（比如n小于100）的时候，插入排序这种O(n²)的算法反而可能更快。我在一次性能优化中把一个小数组的排序从快排换成插入排序，耗时直接降了40%。这就是“理论复杂度”和“实际性能”的差异。
常见复杂度从优到劣的排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。你需要做到看到一段代码就能大致判断它的复杂度。比如双重循环不一定就是O(n²)，如果内层循环的边界依赖于外层变量，可能是O(n log n)甚至O(n)。
2.2 空间复杂度：被忽视的另一半
很多人刷题只看时间，结果面试官一问“你的空间复杂度是多少”就卡壳。空间复杂度计算的是算法额外占用的内存，不包括输入本身。递归算法的空间复杂度要算上调用栈的深度，这一点特别容易漏。
举个例子，归并排序的时间复杂度是O(n log n)，空间复杂度是O(n)，因为合并过程需要临时数组。而快排的平均空间复杂度是O(log n)，来自递归栈的深度。如果你用递归写快排但数据已经有序，递归深度会退化到O(n)，这时候不仅时间变差，空间也会爆。
注意：面试中如果要求“原地排序”，意味着空间复杂度必须是O(1)，这时候归并排序就不适用了，得考虑堆排序。
2.3 均摊复杂度：一个容易被误解的概念
动态数组（比如Python的list、Java的ArrayList）的append操作，单次最坏情况是O(n)——当数组满了需要扩容拷贝。但均摊到每次操作，复杂度是O(1)。这个“均摊”的概念在算法课里经常一笔带过，但它是理解很多数据结构性能的关键。
我用一个生活类比来解释：你每个月发工资那天要花2小时整理账单，其他29天每天只花1分钟记一笔。单看整理那天很耗时，但平均到每天，额外开销微乎其微。均摊复杂度就是算这个“平均账”。
3. 数据结构：算法操作的容器选择
3.1 数组与链表：最基础也最容易选错
数组和链表的取舍是算法课的第一个设计决策点。数组支持O(1)随机访问，但插入和删除平均需要O(n)的移动；链表插入删除是O(1)（已知位置的前提下），但访问第k个元素需要O(n)遍历。
我在实际做题时总结了一个简单的判断标准：如果操作以“读”为主，用数组；如果操作以“增删”为主，用链表。但现实往往更复杂，比如你需要频繁在中间插入又需要随机访问，这时候可以考虑跳表或者平衡树，虽然实现复杂度上去了，但性能折中得比较好。
还有一个细节：链表的O(1)插入是有前提的——你得已经持有那个位置的指针。如果还要先查找位置，那整体还是O(n)。新手最容易在这里犯逻辑错误，以为“链表插入就是O(1)”而忽略了查找开销。
3.2 栈与队列：看似简单，变体极多
栈（后进先出）和队列（先进先出）是算法课里最基础的数据结构，但它们的变体在难题中出场率极高。单调栈用来解决“下一个更大元素”类问题，单调队列用来求滑动窗口最大值，优先队列（堆）用来做Top K和Dijkstra算法。
我当初学单调栈的时候，死活想不明白为什么能在O(n)时间内找到每个元素的下一个更大值。后来画了一张图，把“被弹出栈的元素”标记出来，才发现每个元素最多进栈一次、出栈一次，所以总操作次数是2n。这种“每个元素只被处理常数次”的思路，是很多O(n)算法的核心。
优先队列的底层通常是二叉堆，插入和删除堆顶都是O(log n)，取堆顶是O(1)。建堆的时间复杂度是O(n)而不是O(n log n)，这个结论很多人不知道，因为从最后一个非叶子节点开始下沉调整，总操作次数有一个收敛的级数求和。
3.3 哈希表：用空间换时间的典范
哈希表是算法课里“用空间换时间”思想的最佳代表。理想情况下，插入、删除、查找都是O(1)。但“理想情况”需要好的哈希函数和合理的负载因子。
我踩过的一个坑是：在Python里用字典存大量数据时，如果键的哈希函数设计不好（比如所有键哈希值相同），字典会退化成链表，操作变成O(n)。虽然Python的字典实现已经做了随机化处理来缓解这个问题，但在其他语言里（比如早期Java的HashMap），哈希碰撞攻击是真实存在的。
负载因子是哈希表中元素数量与桶数量的比值。一般当负载因子超过0.75时就需要扩容，扩容操作是O(n)的，但均摊下来每次插入还是O(1)。这个和动态数组的扩容逻辑类似。
提示：刷题时如果只需要判断“存在性”，用哈希集合；如果需要存储键值对，用哈希映射。不要用数组模拟哈希表，除非你能确定键的范围很小。
3.4 树结构：从二叉树到平衡树
二叉树是算法课的重点，也是面试中出场率最高的数据结构之一。二叉搜索树（BST）的中序遍历是有序的，这个性质可以用来解决很多“第K小”“范围查询”类问题。但普通BST在极端情况下会退化成链表，所以有了AVL树和红黑树。
红黑树是工程中最常用的平衡BST，C++的map、Java的TreeMap底层都是红黑树。它的平衡条件比AVL树宽松，插入删除时的旋转次数更少，所以更适合频繁修改的场景。AVL树则更严格平衡，查找略快，适合读多写少的场景。
堆是一种特殊的完全二叉树，分为大顶堆和小顶堆。堆的核心操作是“上浮”和“下沉”，用来维护极值。堆排序就是利用大顶堆反复取最大值实现的，时间复杂度O(n log n)，空间O(1)。
并查集是一种用于处理不相交集合的数据结构，支持“合并”和“查找”两种操作。通过路径压缩和按秩合并，可以把操作复杂度降到接近O(1)。我在做“岛屿数量”“朋友圈”类题目时，并查集比DFS更直观。
4. 经典算法思想：解题的思维武器库
4.1 分治：把大问题切成小问题
分治的核心思想是“分解-解决-合并”：把原问题分解成若干个规模更小的子问题，递归求解后再合并结果。归并排序和快速排序都是分治的典型应用。
分治能成立的前提是子问题相互独立且与原问题形式相同。如果子问题之间有重叠，那就该用动态规划而不是分治了。我在初学时分不清分治和DP，后来总结了一句话：分治是“各管各的”，DP是“互相参考”。
分治的时间复杂度通常用主定理（Master Theorem）来分析。比如归并排序的递推式是T(n) = 2T(n/2) + O(n)，根据主定理属于第二种情况，结果是O(n log n)。主定理有三种情况，对应不同的递推式形式，建议把公式记牢。
4.2 贪心：每一步都选当前最优
贪心算法在每一步选择中都采取当前状态下最优的决定，期望最终得到全局最优。但贪心不是万能的，它需要问题满足“贪心选择性质”和“最优子结构”。
经典的贪心问题包括：活动选择（按结束时间排序）、霍夫曼编码（每次合并最小的两个）、最小生成树的Kruskal和Prim算法。贪心策略的证明往往是难点，常用的证明方法有“交换论证”和“归纳法”。
我个人的经验是：如果一个问题看起来可以用贪心，先试着找反例。找得到反例就说明贪心不对，得换DP；找不到反例再尝试证明。不要一上来就硬证，浪费时间。
4.3 动态规划：从记忆化搜索到递推
动态规划是算法课里最让人头疼也最重要的部分。它的核心是“状态定义”和“状态转移方程”。状态定义决定了你能不能用DP，转移方程决定了DP对不对。
我学DP的路径是：先写递归暴力解，然后加记忆化（自顶向下），最后改成递推（自底向上）。这三步走下来，大部分DP问题都能理清楚。比如斐波那契数列，暴力递归是指数级，加记忆化变O(n)，改成递推也是O(n)但空间可以优化到O(1)。
DP的常见类型包括：线性DP（最长递增子序列）、区间DP（矩阵链乘）、背包DP（01背包、完全背包）、树形DP（树上最大独立集）、状态压缩DP（旅行商问题）。每一类都有固定的套路，但状态定义需要具体问题具体分析。
注意：DP的空间优化往往通过“滚动数组”实现，比如01背包从二维降到一维时，内层循环必须倒序遍历，否则会重复使用同一物品。
4.4 回溯：暴力搜索的优雅写法
回溯算法本质上是一种带剪枝的暴力搜索，适合解决组合、排列、子集、棋盘类问题。它的模板很固定：选择-递归-撤销选择。
回溯的时间复杂度通常很高（指数级），所以剪枝是提升效率的关键。常见的剪枝策略包括：排序后跳过重复元素、提前判断当前路径是否可能达到目标、使用位运算加速状态判断。
我在做N皇后问题时，最初用二维数组判断冲突，每次都要扫描行列和对角线，效率很低。后来改用三个布尔数组分别记录列、主对角线、副对角线的占用情况，判断冲突变成O(1)，整体速度快了十几倍。这个优化思路在回溯题里非常通用。
5. 排序与查找：最常用的算法工具
5.1 排序算法全家福与选型指南
排序是算法课里最“接地气”的部分，因为工程中几乎每天都在用。常见的排序算法有十种左右，但真正需要熟练掌握的是快排、归并、堆排和插入排序。
| 排序算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用，数据随机分布 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 需要稳定排序，链表排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 空间受限，求Top K |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小数组，近乎有序 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 | 整数且范围小 |
快排的优化技巧包括：随机选基准避免最坏情况、三数取中、小区间切换插入排序。我在实际测试中发现，当子数组长度小于16时，插入排序比快排快，所以很多标准库的快排实现都有这个切换阈值。
归并排序的稳定性和O(n log n)的最坏保证是它的优势，但O(n)的额外空间是代价。在链表排序中，归并排序不需要额外空间（因为链表节点可以原地重连），所以是链表排序的首选。
5.2 二分查找：看似简单，边界要命
二分查找的思路极其简单，但写出一个完全正确的二分查找并不容易。边界条件、中点计算、循环终止条件，任何一个细节出错都会导致死循环或漏解。
我总结的二分查找模板是：
def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1这个模板的关键点：left <= right保证区间为空时退出，mid = left + (right - left) // 2避免整数溢出，left = mid + 1和right = mid - 1保证区间收缩。
二分查找的变体包括：查找第一个等于目标的位置、查找最后一个等于目标的位置、查找第一个大于等于目标的位置。这些变体的区别在于相等时的处理逻辑，建议分别记忆。
提示：二分查找不仅适用于有序数组，还适用于“单调函数求零点”类问题。只要你能定义一个单调的判定函数，就可以二分答案。
6. 图论算法：从遍历到最短路径
6.1 图的存储与遍历
图有两种基本存储方式：邻接矩阵和邻接表。邻接矩阵适合稠密图，空间O(n²)，判断两点是否相邻是O(1)；邻接表适合稀疏图，空间O(n+m)，遍历邻居是O(度数)。
图的遍历有DFS和BFS两种。DFS用递归或栈实现，适合找路径、判环、拓扑排序；BFS用队列实现，适合求最短路径（无权图）、层次遍历。我在做题时有个习惯：先判断图是有权还是无权，无权图求最短路直接用BFS，有权图才考虑Dijkstra或Bellman-Ford。
拓扑排序是对有向无环图（DAG）的线性排序，使得每条边的起点都在终点之前。实现方式是BFS+入度统计，或者DFS+逆后序。拓扑排序常用来判断有向图是否有环，以及解决“课程安排”类问题。
6.2 最短路径算法选型
最短路径是图论的核心问题，不同场景对应不同算法：
- Dijkstra：单源最短路，边权非负，时间复杂度O((n+m) log n)（优先队列优化）
- Bellman-Ford：单源最短路，允许负权边，时间复杂度O(nm)，可以检测负环
- Floyd-Warshall：多源最短路，时间复杂度O(n³)，适合小规模稠密图
- SPFA：Bellman-Ford的队列优化版，平均快但最坏仍是O(nm)
Dijkstra的核心是贪心：每次从优先队列取出距离最小的未访问节点，松弛它的邻居。注意Dijkstra不能处理负权边，因为贪心策略在负权下会失效。
Floyd-Warshall的代码极其简洁，三重循环五行搞定，但理解它的DP思想很重要：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])，表示从i到j经过中间节点k的最短距离。
6.3 最小生成树：连接所有点的最低成本
最小生成树（MST）是在连通加权无向图中找一棵包含所有顶点且边权之和最小的树。两种经典算法：
- Kruskal：按边权排序，依次加入不形成环的边，用并查集判环。时间复杂度O(m log m)。
- Prim：从一个顶点开始，每次加入距离当前树最近的顶点，用优先队列维护。时间复杂度O((n+m) log n)。
Kruskal适合稀疏图，Prim适合稠密图。我在实际做题时更常用Kruskal，因为并查集的代码很模板化，不容易写错。
7. 字符串算法：从暴力匹配到KMP
字符串匹配是算法课里实用性很强的部分。暴力匹配的时间复杂度是O(nm)，而KMP算法可以做到O(n+m)。
KMP的核心是next数组（也叫前缀函数），它记录了模式串每个位置的最长相等前后缀长度。当匹配失败时，模式串的指针不需要回退到开头，而是根据next数组跳转到合适位置。我当初理解KMP花了整整两天，最后是用“自己匹配自己”的方式想通的：next数组本质上就是模式串自己和自己做匹配的结果。
除了KMP，还有Rabin-Karp（哈希匹配）、Trie树（前缀树）、AC自动机（多模式匹配）等字符串算法。Trie树在搜索引擎的自动补全、IP路由表中有广泛应用。AC自动机是Trie+KMP的思想结合，适合在一段文本中同时查找多个模式串。
注意：KMP的next数组有多种定义方式，有的版本next[0]=-1，有的版本next[0]=0。刷题时一定要看清楚题目或模板用的是哪种，混用会导致结果错误。
8. 常见问题与排查技巧实录
8.1 算法题调试的通用思路
算法题出错无非几种情况：答案错误、超时、超内存、死循环。我一般的排查顺序是：
- 先看小数据：用n=1、n=2的边界情况测试，很多bug在边界暴露。
- 打印中间状态：在关键步骤打印变量值，确认逻辑是否符合预期。
- 对比暴力解：写一个暴力解法，随机生成小数据对拍，快速定位错误。
- 检查复杂度：如果超时，先算一下当前算法的时间复杂度，确认是否理论就超了。
- 检查递归深度：递归题如果报栈溢出，考虑改迭代或增加递归深度限制。
8.2 常见错误速查表
| 错误类型 | 典型表现 | 排查方法 |
|---|---|---|
| 数组越界 | 运行时错误 | 检查循环边界和索引计算 |
| 整数溢出 | 结果负数或异常 | 用long或Python大整数 |
| 死循环 | 程序卡住 | 检查循环变量是否更新 |
| 答案偏小 | 漏解 | 检查剪枝条件是否过严 |
| 答案偏大 | 重复计数 | 检查去重逻辑 |
| 超时 | 运行时间过长 | 优化复杂度或剪枝 |
| 超内存 | 内存溢出 | 减少存储或滚动数组 |
8.3 我踩过的三个典型坑
第一个坑：浮点数比较。在计算几何题里用==比较浮点数是灾难，必须用abs(a-b) < eps。我当初因为这个WA了五次。
第二个坑：递归中的全局变量。回溯题里用全局变量存路径，忘记在递归返回后撤销选择，导致结果错乱。后来我养成了“选择-递归-撤销”三步写的习惯。
第三个坑：哈希表的键设计。在Python里用元组做键没问题，但用列表做键会报错（列表不可哈希）。如果需要用列表做键，先转成元组。
9. 从课程记录到实战能力的转化
算法课听完只是第一步，真正把知识变成能力需要刻意练习。我的做法是：每学完一个专题，先做5道模板题巩固，再做3道变体题拓展，最后做1道综合题串联。模板题保证你会用，变体题保证你理解，综合题保证你能在复杂场景中识别出该用哪个算法。
另外，定期复盘比盲目刷题重要。我每周会花半天时间回顾本周做错的题，分析错误原因是“知识点不会”还是“思路不对”还是“实现细节出错”。知识点不会就回去补课，思路不对就研究别人的解法，实现细节出错就整理成检查清单。
算法能力的提升没有捷径，但有方法。理解原理、刻意练习、定期复盘，这三件事坚持三个月，你会发现自己看问题的角度完全不一样了。我在实际工作中遇到性能瓶颈时，脑子里会自动浮现“这里能不能用哈希优化”“这个循环能不能二分”“这个递归能不能改DP”，这种条件反射就是算法课留下的最大财富。
