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树和红黑树。红黑树是工程中最常用的平衡BSTC的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矩阵链乘、背包DP01背包、完全背包、树形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(nk)O(nk)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(nm)遍历邻居是O(度数)。图的遍历有DFS和BFS两种。DFS用递归或栈实现适合找路径、判环、拓扑排序BFS用队列实现适合求最短路径无权图、层次遍历。我在做题时有个习惯先判断图是有权还是无权无权图求最短路直接用BFS有权图才考虑Dijkstra或Bellman-Ford。拓扑排序是对有向无环图DAG的线性排序使得每条边的起点都在终点之前。实现方式是BFS入度统计或者DFS逆后序。拓扑排序常用来判断有向图是否有环以及解决“课程安排”类问题。6.2 最短路径算法选型最短路径是图论的核心问题不同场景对应不同算法Dijkstra单源最短路边权非负时间复杂度O((nm) log n)优先队列优化Bellman-Ford单源最短路允许负权边时间复杂度O(nm)可以检测负环Floyd-Warshall多源最短路时间复杂度O(n³)适合小规模稠密图SPFABellman-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((nm) log n)。Kruskal适合稀疏图Prim适合稠密图。我在实际做题时更常用Kruskal因为并查集的代码很模板化不容易写错。7. 字符串算法从暴力匹配到KMP字符串匹配是算法课里实用性很强的部分。暴力匹配的时间复杂度是O(nm)而KMP算法可以做到O(nm)。KMP的核心是next数组也叫前缀函数它记录了模式串每个位置的最长相等前后缀长度。当匹配失败时模式串的指针不需要回退到开头而是根据next数组跳转到合适位置。我当初理解KMP花了整整两天最后是用“自己匹配自己”的方式想通的next数组本质上就是模式串自己和自己做匹配的结果。除了KMP还有Rabin-Karp哈希匹配、Trie树前缀树、AC自动机多模式匹配等字符串算法。Trie树在搜索引擎的自动补全、IP路由表中有广泛应用。AC自动机是TrieKMP的思想结合适合在一段文本中同时查找多个模式串。注意KMP的next数组有多种定义方式有的版本next[0]-1有的版本next[0]0。刷题时一定要看清楚题目或模板用的是哪种混用会导致结果错误。8. 常见问题与排查技巧实录8.1 算法题调试的通用思路算法题出错无非几种情况答案错误、超时、超内存、死循环。我一般的排查顺序是先看小数据用n1、n2的边界情况测试很多bug在边界暴露。打印中间状态在关键步骤打印变量值确认逻辑是否符合预期。对比暴力解写一个暴力解法随机生成小数据对拍快速定位错误。检查复杂度如果超时先算一下当前算法的时间复杂度确认是否理论就超了。检查递归深度递归题如果报栈溢出考虑改迭代或增加递归深度限制。8.2 常见错误速查表错误类型典型表现排查方法数组越界运行时错误检查循环边界和索引计算整数溢出结果负数或异常用long或Python大整数死循环程序卡住检查循环变量是否更新答案偏小漏解检查剪枝条件是否过严答案偏大重复计数检查去重逻辑超时运行时间过长优化复杂度或剪枝超内存内存溢出减少存储或滚动数组8.3 我踩过的三个典型坑第一个坑浮点数比较。在计算几何题里用比较浮点数是灾难必须用abs(a-b) eps。我当初因为这个WA了五次。第二个坑递归中的全局变量。回溯题里用全局变量存路径忘记在递归返回后撤销选择导致结果错乱。后来我养成了“选择-递归-撤销”三步写的习惯。第三个坑哈希表的键设计。在Python里用元组做键没问题但用列表做键会报错列表不可哈希。如果需要用列表做键先转成元组。9. 从课程记录到实战能力的转化算法课听完只是第一步真正把知识变成能力需要刻意练习。我的做法是每学完一个专题先做5道模板题巩固再做3道变体题拓展最后做1道综合题串联。模板题保证你会用变体题保证你理解综合题保证你能在复杂场景中识别出该用哪个算法。另外定期复盘比盲目刷题重要。我每周会花半天时间回顾本周做错的题分析错误原因是“知识点不会”还是“思路不对”还是“实现细节出错”。知识点不会就回去补课思路不对就研究别人的解法实现细节出错就整理成检查清单。算法能力的提升没有捷径但有方法。理解原理、刻意练习、定期复盘这三件事坚持三个月你会发现自己看问题的角度完全不一样了。我在实际工作中遇到性能瓶颈时脑子里会自动浮现“这里能不能用哈希优化”“这个循环能不能二分”“这个递归能不能改DP”这种条件反射就是算法课留下的最大财富。