算法面试是很多程序员绕不开的硬仗。如果只选一门系统课来补基础斯坦福算法专项课程是非常值得优先考虑的目标。这次要展开的是该专项的第一部分分治、排序与随机化算法完整课程主讲人是斯坦福大学的 Tim Roughgarden 教授视频配有中文配音跟学门槛比裸看英文原版低了不少。这套课程的核心价值不在于给你一堆可以背的排序模板而是把每个算法背后“为什么这样设计”讲透。比如归并排序为什么能稳定地达到 O(n log n)快速排序的期望复杂度为什么是 O(n log n)但最坏情况又会退化成 O(n²)随机化算法又是怎么把“最坏情况”变成“大概率表现良好”这些问题都是面试高频考点也是很多工程师平时写业务代码时没有细想过的盲区。课程从数学推导开始一步步往下走看完之后自己动手实现归并、快排、随机化选择算法心里会踏实很多。本文会按照课程的知识脉络做一个完整梳理先看课程整体讲什么再分别拆解分治法、排序算法、随机化算法三个板块每个板块给出关键结论和可直接运行的代码示例最后整理一套配套学习方法、验证流程和常见问题排查清单。如果你是准备算法面试、刚转编程方向或者想系统补一遍算法基础这篇文章可以收藏备用。1. 课程核心信息速览信息项说明课程名称斯坦福算法专项课第一部分分治·排序·随机化主讲人Tim Roughgarden斯坦福大学计算机科学系教授课程内容分治策略、排序算法、随机化算法视频版本配中文配音难度定位本科高年级到研究生入门对刚接触算法的读者有一定挑战编程前置掌握任意一门编程语言的基本语法即可课程以伪代码推导为主数学前置基础代数、对数运算、简单递推式概念学习周期因人而异建议按每周 3 到 5 小时规划学习工具纸笔推导、IDE、复杂度分析练手、LeetCode 对应专题主要产出能独立推导并实现归并排序、快速排序、随机化选择算法能用主定理分析分治类算法这张表把课程关键信息压缩成一份快速判断清单。这门课不是教学某个具体编程语言的课程核心是算法设计与分析方法。有人说它是“数学课加编程课”的混合体更准确的理解是它把工程直觉和数学严谨性放在同等重要的位置。你不需要死记大量实现细节但必须理解复杂度结论是怎么来的。2. 这门课适合谁适用场景与学习边界2.1 适合哪些人第一类准备大厂算法面试的开发者。面试里最常见的手撕代码题很大一部分围绕排序、二分、分治和随机化展开。直接刷题容易陷入“背模板、换题就不会”的循环而这门课正好补上解题前的那一层原理推导。第二类自学过很多算法知识但缺乏体系感的人。很多人会写冒泡排序知道快速排序大概思想但说不清主定理是什么也解释不了随机化选择算法为什么平均复杂度是 O(n)。这门课把散落的知识串成一条主线学完之后你的知识结构会是树状的而不是零散点状。第三类转码或刚入门编程的在校学生。只要提前掌握一门语言的基本语法就可以跟着课程走。课程重点不在语言细节而在算法思维的建立这对后续学习数据结构和系统设计都有帮助。第四类想参加算法竞赛、希望提升复杂度分析能力的人。竞赛考察的不仅是“能不能写出来”更重要的是“有没有更优的复杂度”。分治和随机化是很多高级算法的地基这部分基础扎实后再去看图算法和动态规划会轻松很多。2.2 不太适合哪些情况完全没写过代码的情况不建议直接上手。如果连变量、循环、函数递归都不熟悉一边学算法一边补语言基础会很吃力甚至怀疑自己是不是不适合学算法。建议先用一两周熟悉一门语言的基础再回来跟课程。只想拿现成模板、对证明过程完全没兴趣的人会觉得很啰嗦。这门课的特色就是证明和推导跳过了证明价值和普通博客文章差别不大。如果对分治、排序、随机化已经非常熟悉可以直接跳过第一部分去学专项后续的图算法和动态规划部分。2.3 资源使用边界课程原版在国际在线教育平台发布中文配音版属于学习者自行整理的资源。学习时建议尽量走正规渠道、尊重视频平台的授权条款。自己做笔记、本地运行课程里的算法代码没有问题但不要未经授权搬运、剪辑、二次分发课程视频。这个边界在学习过程中保持清楚即可。3. 课程内容全景三大知识板块课程内容按照“从确定性算法到随机化算法”的顺序展开大致可以拆成三块主线知识板块典型内容核心目标分治策略归并排序、逆序对计数、Karatsuba 乘法、Strassen 矩阵乘法、主定理学会“分解-递归-合并”的通用问题拆解方法排序算法快速排序、堆排序、比较排序下界理解不同排序算法的复杂度本质与应用边界随机化算法随机化快速排序、线性时间选择、随机化思想应用学会用随机化策略对抗最坏情况三个板块之间是递进关系。分治策略是排序算法的基础比如归并排序本身就是典型的分治算法排序算法中的快速排序又因为 pivot 选择问题顺理成章地引出了随机化改进随机化选择算法则进一步把排序思想延伸到“不需要完整排序也能找到第 k 大元素”的问题上。从课程推进方式看前面先搭建分析和推导的工具也就是主定理和分治框架中间章节用这些工具分析快排、堆排最后进入随机化把普通快排升级成随机化快排再推导出线性时间选择算法。这个顺序设计得比较顺畅跟下来不会有突然跳档的感觉。4. 分治法从归并排序到主定理4.1 分治三步曲分治法的核心思想可以概括成三步分解把原问题拆成若干个规模更小的子问题。递归递归求解每个子问题。合并把子问题的解合并成原问题的解。这个框架看起来简单实际难点在第三步。很多问题分解容易合并才是复杂度能否做优的关键。归并排序就是分治三步曲最经典的案例它解决的问题是“数组排序”分解发生在每一步合并时用双指针完成两个有序数组的归并。4.2 归并排序实现与分析归并排序的 Python 教学版本如下def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res归并排序的时间复杂度是稳定的 O(n log n)。不管输入数组是正序、倒序还是乱序递归深度都是 log n每一层合并的总工作量是 O(n)所以总复杂度始终是 O(n log n)。空间复杂度是 O(n)因为合并时需要额外的辅助数组。严格来说递归栈需要 O(log n) 空间但合并过程需要 O(n) 的临时数组综合起来额外空间是 O(n)。归并排序还有一个重要特性稳定。相同元素的相对顺序在合并过程中不会被打乱这是它相比快排的优势。在需要保持原始顺序的业务场景里稳定排序很重要。4.3 逆序对计数给定一个数组统计其中逆序对的数量。逆序对的定义是对于下标 i j如果 arr[i] arr[j]则 (i, j) 构成一个逆序对。朴素解法是双重循环复杂度 O(n²)。分治解法可以把它优化到 O(n log n)思路借助归并排序把数组分成左右两半。分别统计左半内部逆序对、右半内部逆序对。统计跨左右两个部分的逆序对同时完成排序。跨部分统计的关键是归并时如果右侧元素小于左侧当前元素说明左侧剩余元素都大于该右侧元素总数可以直接累加。这个技巧在面试里非常常见比如“求数组逆序对”这类题目。4.4 Karatsuba 乘法减少子问题数量普通乘法把两个 n 位数相乘本质是 O(n²) 的逐位相乘。Karatsuba 算法的突破点在于把两个大数各分成高低两半用 3 次乘法而不是 4 次乘法完成计算。设两个 n 位数 x 和 y拆成x a * 10^(n/2) b y c * 10^(n/2) d普通做法需要计算 ac、ad、bc、bd 四个乘积。Karatsuba 观察到可以只算三个乘积acbd(ab)(cd) - ac - bd第三个式子的结果恰好是 ad bc。这样递推式从 T(n) 4T(n/2) O(n) 降为 T(n) 3T(n/2) O(n)。主定理算出来Karatsuba 乘法的时间复杂度大约是 O(n^1.585)比 O(n²) 快很多。课程讲这个例子的目的非常明确优化分治的核心不仅仅是“拆得小”更在于减少子问题的数量。4.5 Strassen 矩阵乘法的思想矩阵乘法的朴素实现是三重循环复杂度 O(n³)。Strassen 算法通过巧妙的加减法组合把两个 2×2 矩阵相乘所需的子矩阵乘法次数从 8 次降到 7 次。矩阵乘法的复杂度从 O(n³) 降到 O(n^log2(7))约等于 O(n^2.807)。这个算法在实际工程中应用不算多因为常数因子大、数值稳定性也不如朴素方法但它是分治法和“常数优化”思想的经典案例。这门课讲 Strassen 的主要目的不是为了让你手写而是培养一个意识分治方案的性能瓶颈往往在于子问题的数量增加一些加法运算来换取乘法次数减少有时是划算的。4.6 主定理分析分治复杂度的通用工具主定理是用来分析分治递推式的标准工具。它的标准形式如下对于递推式 T(n) aT(n/b) O(n^d)其中 a ≥ 1b 1d ≥ 0结果分三种情况条件复杂度d log_b(a)O(n^d)d log_b(a)O(n^d log n)d log_b(a)O(n^(log_b(a)))用归并排序验证递推式 T(n) 2T(n/2) O(n)这里 a 2b 2d 1。计算 log_b(a) log_2(2) 1正好等于 d所以归并排序的复杂度是 O(n log n)。再验证 KaratsubaT(n) 3T(n/2) O(n)a 3b 2d 1。log_2(3) ≈ 1.585 1所以复杂度是 O(n^1.585)。掌握主定理之后再看到任何“分几份、每份多大、合并多贵”的递推式都能快速估算出复杂度。这门课把主定理放在分治板块中间讲正好为后面的快排分析做了铺垫。5. 排序算法快速排序、堆排序与复杂度下界5.1 快速排序快速排序可能是实际应用最多的排序算法。它的基本思路是选择一个 pivot把数组分成小于 pivot、等于 pivot、大于 pivot 三部分然后递归处理左右子数组。先看一个最直观的教学版本def quick_sort(arr): if len(arr) 1: return arr pivot arr[0] less [x for x in arr[1:] if x pivot] greater [x for x in arr[1:] if x pivot] return quick_sort(less) [pivot] quick_sort(greater)这个版本只能用于理解思想实际工程里不会这样写因为每次都新建多个数组额外空间很大。真正的快排会做原地分区partition在同一个数组上通过交换元素完成排序。快排的平均时间复杂度是 O(n log n)但最坏情况是 O(n²)。当数组已经有序且每次固定选第一个元素作为 pivot 时划分极端不平衡递归深度变成 n复杂度退化为 O(n²)。这个问题在课程中非常关键因为它直接引出了随机化快排的必要性。5.2 堆排序堆排序利用完全二叉树的性质在 O(1) 额外空间的条件下完成排序。核心操作包括建堆和反复弹出堆顶。堆排序的时间复杂度是 O(n log n)且最坏情况也能保证这一点比快排好。但它不是稳定排序相同元素的相对顺序可能被打乱并且实际常数因子比快排略大所以大部分语言内置排序没有选择堆排序。对于学习来说堆排序的价值在于理解“优先级队列”的数据结构基础。课程主要讲它的构建过程、heapify 复杂度分析以及和快排的场景对比。5.3 比较排序下界为什么不能低于 O(n log n)很多人有个疑问既然排序被反复研究为什么主流比较排序的下限是 O(n log n)这门课用决策树模型给出了严格证明。任何基于比较的排序算法都可以抽象成一棵决策树。树中的每个内部节点表示一次比较叶子节点表示一种可能的输入排列。n 个元素的输入有 n! 种排列所以决策树至少有 n! 个叶子。二叉树高度 h 对应的叶子数最多是 2^h于是2^h ≥ n!两边取对数h ≥ log_2(n!) ≈ n log_2 n - O(n)。这说明任何比较排序算法在最坏情况下至少需要 n log n 量级的比较次数。归并排序和堆排序都已经达到这个下界快排的平均情况也达到。这就是为什么算法设计者只能通过随机化或非比较手段比如计数排序、基数排序来突破这个下界。5.4 稳定性与场景选择排序算法平均复杂度最坏复杂度是否稳定额外空间归并排序O(n log n)O(n log n)是O(n)快速排序O(n log n)O(n²)否O(log n)原地分区版堆排序O(n log n)O(n log n)否O(1)实际选择时需要综合考虑数据规模、稳定性要求、内存限制和是否可能接近最坏情况。课程会反复强调不要背结论要会推导因为面试官往往会在你写完快排之后追问“最坏情况是什么怎么优化”。6. 随机化算法从随机快排到线性时间选择6.1 随机化快速排序快排最坏情况出现在 pivot 选择极端不平衡时。解决思路有两个一种是用三数取中法减少选到最差的概率另一种就是随机化 pivot。随机化快排的核心改动非常小在每次递归时从当前区间随机选择一个元素作为 pivot而不是固定选第一个或最后一个。import random def randomized_quick_sort(arr): if len(arr) 1: return arr pivot_idx random.randrange(len(arr)) pivot arr[pivot_idx] less [x for x in arr if x pivot] equal [x for x in arr if x pivot] greater [x for x in arr if x pivot] return randomized_quick_sort(less) equal randomized_quick_sort(greater)随机化之后理论上最坏情况仍然可能发生但概率极低而且和输入数据没有固定关联。对于已经有序的数组随机选 pivot 能有效避免退化。课程强调的要点是随机化不代表复杂度一定变好而是把“被恶意输入击中”的概率降到可以忽略的程度。6.2 线性时间选择算法经典的顺序统计量问题是在无序数组中找第 k 小的元素。最简单的做法是先排序再取下标复杂度 O(n log n)。但这门课会介绍更优的随机化方法平均复杂度可以达到 O(n)。算法思路类似快排但只需要递归处理一侧不需要完整排序import random def quick_select(arr, k): # 返回数组 arr 中第 k 小的元素k 从 0 开始 if len(arr) 1: return arr[0] pivot_idx random.randrange(len(arr)) pivot arr[pivot_idx] less [x for x in arr if x pivot] equal [x for x in arr if x pivot] greater [x for x in arr if x pivot] if k len(less): return quick_select(less, k) elif k len(less) len(equal): return pivot else: return quick_select(greater, k - len(less) - len(equal))测试代码arr [3, 1, 4, 1, 5, 9, 2, 6] for k in range(len(arr)): print(k, quick_select(arr, k))输出结果应该是从小到大排列的数组元素。这个算法的期望时间复杂度是 O(n)原因是每次期望减少大约一半的递归规模。它是很多高级算法的基础比如求中位数、在大型数据集中找 Top-K。6.3 Las Vegas 与 Monte Carlo两类随机算法随机化算法在理论上分为两类。Las Vegas 算法结果一定正确但运行时间是一个随机变量。随机化快速排序和随机化选择都属于这一类。无论随机结果如何最终答案都是正确的只是速度可能不同。Monte Carlo 算法运行时间确定但结果有一定概率出错。典型例子是某些随机化素数判定算法判定结果可能是“合数”也可能是“概率上质数”。课程主要讲解 Las Vegas 类型但会介绍两类算法的区别。6.4 随机化在真实系统里的应用随机化不只是理论玩具。哈希表里引入随机化的哈希函数可以防止恶意输入导致大量哈希冲突负载均衡算法中的随机选择可以避免集中请求到同一个节点跳表用随机抛硬币决定层高从而在期望上达到二叉搜索树的效果。理解基础的随机化思想之后再看这些系统设计就能很快串起来。这门课的第一部分正是在为这些应用打底。7. 学习路线与效果验证方式7.1 三遍跟学法第一遍完整跟视频不做代码专注理解推导过程。拿纸笔跟着写递推式把主定理的三个分支手动套一遍。第二遍每看完一个算法立刻关掉视频凭理解自己写实现。写不出来没关系回看视频的推导部分再写一遍。这一遍的重点是“卡住之后定位到哪一步没懂”。第三遍用复杂度分析方法重新解释自己写的代码。给每个函数写出递推式套主定理验证复杂度再跑几个规模递增的测试用例观察表现。三遍下来的效果通常比“刷三遍视频但不动手”要好得多。7.2 验证方式写代码、跑规模对比建立一个小实验目录每学完一个算法就写一个 benchmark 脚本。比如对归并排序、快速排序、堆排序分别测试长度为 1000、10000、100000 的随机数组观察耗时随规模的增长曲线。如果归并排序和快排的耗时增长接近线性倍数说明实现没有重大问题。import random import time def run_sort(func, data): start time.time() func(data) return time.time() - start for n in [1000, 10000, 100000]: data [random.randint(0, 100000) for _ in range(n)] t_merge run_sort(merge_sort, data[:]) print(fn{n}, merge_sort{t_merge:.4f}s)注意这里 merge_sort 返回新数组run_sort 里需要接收返回值。实际验证时按自己实现的函数签名调整即可。7.3 每章练习建议分治部分建议练习逆序对计数、多数元素问题、最大子数组和。排序部分建议练习数组中的第 K 个最大元素、颜色分类、合并区间。随机化部分可以用随机化快速选择解决找中位数问题再对比朴素排序实现的时间差异。这些题目在 LeetCode 上都有同名题目搜索对应关键词就能找到。做的时候建议先用自己的算法实现再考虑是否调库函数。8. 常见问题与排查方法问题现象可能原因排查方式解决方案主定理套不进去递推式没写对或用的是非标准形式先写出准确的 T(n)确认 n/b 是整数规模把递推式化成标准 aT(n/b)O(n^d) 再看快排题目超时每次选第一个元素当 pivot输入接近有序本机造一个有序大数据集测试改用随机化 pivot 或三数取中写的归并排序结果不对合并逻辑里比较符号写反或切片写错先跑小数组逐个验证用单步调试跟踪一次 merge 过程递归深度过大输入规模很大或递归版本没有边界条件查看报错 RecursionError 或观察栈深度对超大数组改用迭代或增加递归限制但要先确认算法正确复杂度说不清楚只记住了结论没掌握推导方法自己重新写递推式套主定理把归并、快排、随机选择三个递推式各推导三遍学完还是不会做题只看了视频没有动手写代码检查是否完成每章的实现练习回到第 7 节的三遍跟学法重新过一遍中文配音版本进度太慢视频时间较长每讲信息密度高拆分到多次学习每次 50 分钟用 1.25 倍速二刷第一遍保持正常速度这个清单是我根据算法学习常见误区整理的不一定每一条都会遇到但遇到时知道往哪个方向排查就够了。9. 最佳实践与配套资源9.1 笔记方法建议准备一个纸质笔记本或支持公式输入的笔记工具按照“问题定义 - 算法思路 - 递推式 - 复杂度分析 - 代码实现 - 反例测试”六段式记录。每学完一个算法都用这种方式写一遍比单纯复制讲义有巩固作用。9.2 适配教材如果希望搭配文字教材学习同作者有一本《Algorithms Illuminated》系列第一卷的主题正好对应分治与排序可以作为课程延伸阅读。不过要注意教材目录和视频课不一定完全对齐阅读时按知识点对照不要死板地要求页码完全对应。9.3 提问式学习法每学完一个章节尝试向自己提出反向问题。比如归并排序的合并过程如果改成不稳定的写法会影响正确性吗快排pivot选中间元素就一定比选随机元素更好吗Randomized Selection 里如果 pivot 总是选到当前区间的最小值期望复杂度还是 O(n) 吗回答这些问题不一定都需要写代码但一定要能说出推导过程。说不清楚的地方就是需要回看视频的地方。9.4 避免三个学习陷阱第一个陷阱是跳过所有证明只背复杂度结论。后果是面试里被问到“为什么快排期望 O(n log n)”时答不上来写题正确率也会受影响。第二个陷阱是只写理论版本代码不关注细节。比如快排写的是每次新建数组的简化版本面试时如果需要原地实现就写不出来。建议至少把课程里学的每个算法实现一个原地方案。第三个陷阱是一口气看很多集不做练习。算法和编程一样是实践学科输入和输出的比例最好控制在合理范围。看一讲视频配至少两次动手验证吸收效果会好很多。10. 总结与下一步这门课最值得跟学的点是把“算法”从背题提升到了“可推导的科学”层面。你不需要再记住一堆结论只要掌握分治框架、主定理、随机化思想就能重新推导出排序、选择、复杂度分析等核心内容。首先建议验证的功能点自己实现一遍归并排序和快速排序写下它们各自的递推式再用主定理解释复杂度最后对随机数组做规模测试观察耗时增长规律。最容易踩的坑是跳过证明直接看结论以及只写简化版代码。前者会导致复杂度分析说不清后者会导致面试手撕代码时卡在分区细节上。完成第一部分之后建议保持同样的节奏进入专项后续内容继续学习图算法、最短路径、最小生成树、贪心算法和动态规划。这几块内容与分治、随机化关系密切基础打牢之后可以直接连续学习。最好的验证标准很简单学完后能否在白板上手写随机化快速选择并解释清楚为什么它的期望复杂度是 O(n)而不是 O(n log n)。
分治、排序与随机化算法：斯坦福算法专项课核心解析
算法面试是很多程序员绕不开的硬仗。如果只选一门系统课来补基础斯坦福算法专项课程是非常值得优先考虑的目标。这次要展开的是该专项的第一部分分治、排序与随机化算法完整课程主讲人是斯坦福大学的 Tim Roughgarden 教授视频配有中文配音跟学门槛比裸看英文原版低了不少。这套课程的核心价值不在于给你一堆可以背的排序模板而是把每个算法背后“为什么这样设计”讲透。比如归并排序为什么能稳定地达到 O(n log n)快速排序的期望复杂度为什么是 O(n log n)但最坏情况又会退化成 O(n²)随机化算法又是怎么把“最坏情况”变成“大概率表现良好”这些问题都是面试高频考点也是很多工程师平时写业务代码时没有细想过的盲区。课程从数学推导开始一步步往下走看完之后自己动手实现归并、快排、随机化选择算法心里会踏实很多。本文会按照课程的知识脉络做一个完整梳理先看课程整体讲什么再分别拆解分治法、排序算法、随机化算法三个板块每个板块给出关键结论和可直接运行的代码示例最后整理一套配套学习方法、验证流程和常见问题排查清单。如果你是准备算法面试、刚转编程方向或者想系统补一遍算法基础这篇文章可以收藏备用。1. 课程核心信息速览信息项说明课程名称斯坦福算法专项课第一部分分治·排序·随机化主讲人Tim Roughgarden斯坦福大学计算机科学系教授课程内容分治策略、排序算法、随机化算法视频版本配中文配音难度定位本科高年级到研究生入门对刚接触算法的读者有一定挑战编程前置掌握任意一门编程语言的基本语法即可课程以伪代码推导为主数学前置基础代数、对数运算、简单递推式概念学习周期因人而异建议按每周 3 到 5 小时规划学习工具纸笔推导、IDE、复杂度分析练手、LeetCode 对应专题主要产出能独立推导并实现归并排序、快速排序、随机化选择算法能用主定理分析分治类算法这张表把课程关键信息压缩成一份快速判断清单。这门课不是教学某个具体编程语言的课程核心是算法设计与分析方法。有人说它是“数学课加编程课”的混合体更准确的理解是它把工程直觉和数学严谨性放在同等重要的位置。你不需要死记大量实现细节但必须理解复杂度结论是怎么来的。2. 这门课适合谁适用场景与学习边界2.1 适合哪些人第一类准备大厂算法面试的开发者。面试里最常见的手撕代码题很大一部分围绕排序、二分、分治和随机化展开。直接刷题容易陷入“背模板、换题就不会”的循环而这门课正好补上解题前的那一层原理推导。第二类自学过很多算法知识但缺乏体系感的人。很多人会写冒泡排序知道快速排序大概思想但说不清主定理是什么也解释不了随机化选择算法为什么平均复杂度是 O(n)。这门课把散落的知识串成一条主线学完之后你的知识结构会是树状的而不是零散点状。第三类转码或刚入门编程的在校学生。只要提前掌握一门语言的基本语法就可以跟着课程走。课程重点不在语言细节而在算法思维的建立这对后续学习数据结构和系统设计都有帮助。第四类想参加算法竞赛、希望提升复杂度分析能力的人。竞赛考察的不仅是“能不能写出来”更重要的是“有没有更优的复杂度”。分治和随机化是很多高级算法的地基这部分基础扎实后再去看图算法和动态规划会轻松很多。2.2 不太适合哪些情况完全没写过代码的情况不建议直接上手。如果连变量、循环、函数递归都不熟悉一边学算法一边补语言基础会很吃力甚至怀疑自己是不是不适合学算法。建议先用一两周熟悉一门语言的基础再回来跟课程。只想拿现成模板、对证明过程完全没兴趣的人会觉得很啰嗦。这门课的特色就是证明和推导跳过了证明价值和普通博客文章差别不大。如果对分治、排序、随机化已经非常熟悉可以直接跳过第一部分去学专项后续的图算法和动态规划部分。2.3 资源使用边界课程原版在国际在线教育平台发布中文配音版属于学习者自行整理的资源。学习时建议尽量走正规渠道、尊重视频平台的授权条款。自己做笔记、本地运行课程里的算法代码没有问题但不要未经授权搬运、剪辑、二次分发课程视频。这个边界在学习过程中保持清楚即可。3. 课程内容全景三大知识板块课程内容按照“从确定性算法到随机化算法”的顺序展开大致可以拆成三块主线知识板块典型内容核心目标分治策略归并排序、逆序对计数、Karatsuba 乘法、Strassen 矩阵乘法、主定理学会“分解-递归-合并”的通用问题拆解方法排序算法快速排序、堆排序、比较排序下界理解不同排序算法的复杂度本质与应用边界随机化算法随机化快速排序、线性时间选择、随机化思想应用学会用随机化策略对抗最坏情况三个板块之间是递进关系。分治策略是排序算法的基础比如归并排序本身就是典型的分治算法排序算法中的快速排序又因为 pivot 选择问题顺理成章地引出了随机化改进随机化选择算法则进一步把排序思想延伸到“不需要完整排序也能找到第 k 大元素”的问题上。从课程推进方式看前面先搭建分析和推导的工具也就是主定理和分治框架中间章节用这些工具分析快排、堆排最后进入随机化把普通快排升级成随机化快排再推导出线性时间选择算法。这个顺序设计得比较顺畅跟下来不会有突然跳档的感觉。4. 分治法从归并排序到主定理4.1 分治三步曲分治法的核心思想可以概括成三步分解把原问题拆成若干个规模更小的子问题。递归递归求解每个子问题。合并把子问题的解合并成原问题的解。这个框架看起来简单实际难点在第三步。很多问题分解容易合并才是复杂度能否做优的关键。归并排序就是分治三步曲最经典的案例它解决的问题是“数组排序”分解发生在每一步合并时用双指针完成两个有序数组的归并。4.2 归并排序实现与分析归并排序的 Python 教学版本如下def merge_sort(arr): if len(arr) 1: return arr mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i j 0 res [] while i len(left) and j len(right): if left[i] right[j]: res.append(left[i]) i 1 else: res.append(right[j]) j 1 res.extend(left[i:]) res.extend(right[j:]) return res归并排序的时间复杂度是稳定的 O(n log n)。不管输入数组是正序、倒序还是乱序递归深度都是 log n每一层合并的总工作量是 O(n)所以总复杂度始终是 O(n log n)。空间复杂度是 O(n)因为合并时需要额外的辅助数组。严格来说递归栈需要 O(log n) 空间但合并过程需要 O(n) 的临时数组综合起来额外空间是 O(n)。归并排序还有一个重要特性稳定。相同元素的相对顺序在合并过程中不会被打乱这是它相比快排的优势。在需要保持原始顺序的业务场景里稳定排序很重要。4.3 逆序对计数给定一个数组统计其中逆序对的数量。逆序对的定义是对于下标 i j如果 arr[i] arr[j]则 (i, j) 构成一个逆序对。朴素解法是双重循环复杂度 O(n²)。分治解法可以把它优化到 O(n log n)思路借助归并排序把数组分成左右两半。分别统计左半内部逆序对、右半内部逆序对。统计跨左右两个部分的逆序对同时完成排序。跨部分统计的关键是归并时如果右侧元素小于左侧当前元素说明左侧剩余元素都大于该右侧元素总数可以直接累加。这个技巧在面试里非常常见比如“求数组逆序对”这类题目。4.4 Karatsuba 乘法减少子问题数量普通乘法把两个 n 位数相乘本质是 O(n²) 的逐位相乘。Karatsuba 算法的突破点在于把两个大数各分成高低两半用 3 次乘法而不是 4 次乘法完成计算。设两个 n 位数 x 和 y拆成x a * 10^(n/2) b y c * 10^(n/2) d普通做法需要计算 ac、ad、bc、bd 四个乘积。Karatsuba 观察到可以只算三个乘积acbd(ab)(cd) - ac - bd第三个式子的结果恰好是 ad bc。这样递推式从 T(n) 4T(n/2) O(n) 降为 T(n) 3T(n/2) O(n)。主定理算出来Karatsuba 乘法的时间复杂度大约是 O(n^1.585)比 O(n²) 快很多。课程讲这个例子的目的非常明确优化分治的核心不仅仅是“拆得小”更在于减少子问题的数量。4.5 Strassen 矩阵乘法的思想矩阵乘法的朴素实现是三重循环复杂度 O(n³)。Strassen 算法通过巧妙的加减法组合把两个 2×2 矩阵相乘所需的子矩阵乘法次数从 8 次降到 7 次。矩阵乘法的复杂度从 O(n³) 降到 O(n^log2(7))约等于 O(n^2.807)。这个算法在实际工程中应用不算多因为常数因子大、数值稳定性也不如朴素方法但它是分治法和“常数优化”思想的经典案例。这门课讲 Strassen 的主要目的不是为了让你手写而是培养一个意识分治方案的性能瓶颈往往在于子问题的数量增加一些加法运算来换取乘法次数减少有时是划算的。4.6 主定理分析分治复杂度的通用工具主定理是用来分析分治递推式的标准工具。它的标准形式如下对于递推式 T(n) aT(n/b) O(n^d)其中 a ≥ 1b 1d ≥ 0结果分三种情况条件复杂度d log_b(a)O(n^d)d log_b(a)O(n^d log n)d log_b(a)O(n^(log_b(a)))用归并排序验证递推式 T(n) 2T(n/2) O(n)这里 a 2b 2d 1。计算 log_b(a) log_2(2) 1正好等于 d所以归并排序的复杂度是 O(n log n)。再验证 KaratsubaT(n) 3T(n/2) O(n)a 3b 2d 1。log_2(3) ≈ 1.585 1所以复杂度是 O(n^1.585)。掌握主定理之后再看到任何“分几份、每份多大、合并多贵”的递推式都能快速估算出复杂度。这门课把主定理放在分治板块中间讲正好为后面的快排分析做了铺垫。5. 排序算法快速排序、堆排序与复杂度下界5.1 快速排序快速排序可能是实际应用最多的排序算法。它的基本思路是选择一个 pivot把数组分成小于 pivot、等于 pivot、大于 pivot 三部分然后递归处理左右子数组。先看一个最直观的教学版本def quick_sort(arr): if len(arr) 1: return arr pivot arr[0] less [x for x in arr[1:] if x pivot] greater [x for x in arr[1:] if x pivot] return quick_sort(less) [pivot] quick_sort(greater)这个版本只能用于理解思想实际工程里不会这样写因为每次都新建多个数组额外空间很大。真正的快排会做原地分区partition在同一个数组上通过交换元素完成排序。快排的平均时间复杂度是 O(n log n)但最坏情况是 O(n²)。当数组已经有序且每次固定选第一个元素作为 pivot 时划分极端不平衡递归深度变成 n复杂度退化为 O(n²)。这个问题在课程中非常关键因为它直接引出了随机化快排的必要性。5.2 堆排序堆排序利用完全二叉树的性质在 O(1) 额外空间的条件下完成排序。核心操作包括建堆和反复弹出堆顶。堆排序的时间复杂度是 O(n log n)且最坏情况也能保证这一点比快排好。但它不是稳定排序相同元素的相对顺序可能被打乱并且实际常数因子比快排略大所以大部分语言内置排序没有选择堆排序。对于学习来说堆排序的价值在于理解“优先级队列”的数据结构基础。课程主要讲它的构建过程、heapify 复杂度分析以及和快排的场景对比。5.3 比较排序下界为什么不能低于 O(n log n)很多人有个疑问既然排序被反复研究为什么主流比较排序的下限是 O(n log n)这门课用决策树模型给出了严格证明。任何基于比较的排序算法都可以抽象成一棵决策树。树中的每个内部节点表示一次比较叶子节点表示一种可能的输入排列。n 个元素的输入有 n! 种排列所以决策树至少有 n! 个叶子。二叉树高度 h 对应的叶子数最多是 2^h于是2^h ≥ n!两边取对数h ≥ log_2(n!) ≈ n log_2 n - O(n)。这说明任何比较排序算法在最坏情况下至少需要 n log n 量级的比较次数。归并排序和堆排序都已经达到这个下界快排的平均情况也达到。这就是为什么算法设计者只能通过随机化或非比较手段比如计数排序、基数排序来突破这个下界。5.4 稳定性与场景选择排序算法平均复杂度最坏复杂度是否稳定额外空间归并排序O(n log n)O(n log n)是O(n)快速排序O(n log n)O(n²)否O(log n)原地分区版堆排序O(n log n)O(n log n)否O(1)实际选择时需要综合考虑数据规模、稳定性要求、内存限制和是否可能接近最坏情况。课程会反复强调不要背结论要会推导因为面试官往往会在你写完快排之后追问“最坏情况是什么怎么优化”。6. 随机化算法从随机快排到线性时间选择6.1 随机化快速排序快排最坏情况出现在 pivot 选择极端不平衡时。解决思路有两个一种是用三数取中法减少选到最差的概率另一种就是随机化 pivot。随机化快排的核心改动非常小在每次递归时从当前区间随机选择一个元素作为 pivot而不是固定选第一个或最后一个。import random def randomized_quick_sort(arr): if len(arr) 1: return arr pivot_idx random.randrange(len(arr)) pivot arr[pivot_idx] less [x for x in arr if x pivot] equal [x for x in arr if x pivot] greater [x for x in arr if x pivot] return randomized_quick_sort(less) equal randomized_quick_sort(greater)随机化之后理论上最坏情况仍然可能发生但概率极低而且和输入数据没有固定关联。对于已经有序的数组随机选 pivot 能有效避免退化。课程强调的要点是随机化不代表复杂度一定变好而是把“被恶意输入击中”的概率降到可以忽略的程度。6.2 线性时间选择算法经典的顺序统计量问题是在无序数组中找第 k 小的元素。最简单的做法是先排序再取下标复杂度 O(n log n)。但这门课会介绍更优的随机化方法平均复杂度可以达到 O(n)。算法思路类似快排但只需要递归处理一侧不需要完整排序import random def quick_select(arr, k): # 返回数组 arr 中第 k 小的元素k 从 0 开始 if len(arr) 1: return arr[0] pivot_idx random.randrange(len(arr)) pivot arr[pivot_idx] less [x for x in arr if x pivot] equal [x for x in arr if x pivot] greater [x for x in arr if x pivot] if k len(less): return quick_select(less, k) elif k len(less) len(equal): return pivot else: return quick_select(greater, k - len(less) - len(equal))测试代码arr [3, 1, 4, 1, 5, 9, 2, 6] for k in range(len(arr)): print(k, quick_select(arr, k))输出结果应该是从小到大排列的数组元素。这个算法的期望时间复杂度是 O(n)原因是每次期望减少大约一半的递归规模。它是很多高级算法的基础比如求中位数、在大型数据集中找 Top-K。6.3 Las Vegas 与 Monte Carlo两类随机算法随机化算法在理论上分为两类。Las Vegas 算法结果一定正确但运行时间是一个随机变量。随机化快速排序和随机化选择都属于这一类。无论随机结果如何最终答案都是正确的只是速度可能不同。Monte Carlo 算法运行时间确定但结果有一定概率出错。典型例子是某些随机化素数判定算法判定结果可能是“合数”也可能是“概率上质数”。课程主要讲解 Las Vegas 类型但会介绍两类算法的区别。6.4 随机化在真实系统里的应用随机化不只是理论玩具。哈希表里引入随机化的哈希函数可以防止恶意输入导致大量哈希冲突负载均衡算法中的随机选择可以避免集中请求到同一个节点跳表用随机抛硬币决定层高从而在期望上达到二叉搜索树的效果。理解基础的随机化思想之后再看这些系统设计就能很快串起来。这门课的第一部分正是在为这些应用打底。7. 学习路线与效果验证方式7.1 三遍跟学法第一遍完整跟视频不做代码专注理解推导过程。拿纸笔跟着写递推式把主定理的三个分支手动套一遍。第二遍每看完一个算法立刻关掉视频凭理解自己写实现。写不出来没关系回看视频的推导部分再写一遍。这一遍的重点是“卡住之后定位到哪一步没懂”。第三遍用复杂度分析方法重新解释自己写的代码。给每个函数写出递推式套主定理验证复杂度再跑几个规模递增的测试用例观察表现。三遍下来的效果通常比“刷三遍视频但不动手”要好得多。7.2 验证方式写代码、跑规模对比建立一个小实验目录每学完一个算法就写一个 benchmark 脚本。比如对归并排序、快速排序、堆排序分别测试长度为 1000、10000、100000 的随机数组观察耗时随规模的增长曲线。如果归并排序和快排的耗时增长接近线性倍数说明实现没有重大问题。import random import time def run_sort(func, data): start time.time() func(data) return time.time() - start for n in [1000, 10000, 100000]: data [random.randint(0, 100000) for _ in range(n)] t_merge run_sort(merge_sort, data[:]) print(fn{n}, merge_sort{t_merge:.4f}s)注意这里 merge_sort 返回新数组run_sort 里需要接收返回值。实际验证时按自己实现的函数签名调整即可。7.3 每章练习建议分治部分建议练习逆序对计数、多数元素问题、最大子数组和。排序部分建议练习数组中的第 K 个最大元素、颜色分类、合并区间。随机化部分可以用随机化快速选择解决找中位数问题再对比朴素排序实现的时间差异。这些题目在 LeetCode 上都有同名题目搜索对应关键词就能找到。做的时候建议先用自己的算法实现再考虑是否调库函数。8. 常见问题与排查方法问题现象可能原因排查方式解决方案主定理套不进去递推式没写对或用的是非标准形式先写出准确的 T(n)确认 n/b 是整数规模把递推式化成标准 aT(n/b)O(n^d) 再看快排题目超时每次选第一个元素当 pivot输入接近有序本机造一个有序大数据集测试改用随机化 pivot 或三数取中写的归并排序结果不对合并逻辑里比较符号写反或切片写错先跑小数组逐个验证用单步调试跟踪一次 merge 过程递归深度过大输入规模很大或递归版本没有边界条件查看报错 RecursionError 或观察栈深度对超大数组改用迭代或增加递归限制但要先确认算法正确复杂度说不清楚只记住了结论没掌握推导方法自己重新写递推式套主定理把归并、快排、随机选择三个递推式各推导三遍学完还是不会做题只看了视频没有动手写代码检查是否完成每章的实现练习回到第 7 节的三遍跟学法重新过一遍中文配音版本进度太慢视频时间较长每讲信息密度高拆分到多次学习每次 50 分钟用 1.25 倍速二刷第一遍保持正常速度这个清单是我根据算法学习常见误区整理的不一定每一条都会遇到但遇到时知道往哪个方向排查就够了。9. 最佳实践与配套资源9.1 笔记方法建议准备一个纸质笔记本或支持公式输入的笔记工具按照“问题定义 - 算法思路 - 递推式 - 复杂度分析 - 代码实现 - 反例测试”六段式记录。每学完一个算法都用这种方式写一遍比单纯复制讲义有巩固作用。9.2 适配教材如果希望搭配文字教材学习同作者有一本《Algorithms Illuminated》系列第一卷的主题正好对应分治与排序可以作为课程延伸阅读。不过要注意教材目录和视频课不一定完全对齐阅读时按知识点对照不要死板地要求页码完全对应。9.3 提问式学习法每学完一个章节尝试向自己提出反向问题。比如归并排序的合并过程如果改成不稳定的写法会影响正确性吗快排pivot选中间元素就一定比选随机元素更好吗Randomized Selection 里如果 pivot 总是选到当前区间的最小值期望复杂度还是 O(n) 吗回答这些问题不一定都需要写代码但一定要能说出推导过程。说不清楚的地方就是需要回看视频的地方。9.4 避免三个学习陷阱第一个陷阱是跳过所有证明只背复杂度结论。后果是面试里被问到“为什么快排期望 O(n log n)”时答不上来写题正确率也会受影响。第二个陷阱是只写理论版本代码不关注细节。比如快排写的是每次新建数组的简化版本面试时如果需要原地实现就写不出来。建议至少把课程里学的每个算法实现一个原地方案。第三个陷阱是一口气看很多集不做练习。算法和编程一样是实践学科输入和输出的比例最好控制在合理范围。看一讲视频配至少两次动手验证吸收效果会好很多。10. 总结与下一步这门课最值得跟学的点是把“算法”从背题提升到了“可推导的科学”层面。你不需要再记住一堆结论只要掌握分治框架、主定理、随机化思想就能重新推导出排序、选择、复杂度分析等核心内容。首先建议验证的功能点自己实现一遍归并排序和快速排序写下它们各自的递推式再用主定理解释复杂度最后对随机数组做规模测试观察耗时增长规律。最容易踩的坑是跳过证明直接看结论以及只写简化版代码。前者会导致复杂度分析说不清后者会导致面试手撕代码时卡在分区细节上。完成第一部分之后建议保持同样的节奏进入专项后续内容继续学习图算法、最短路径、最小生成树、贪心算法和动态规划。这几块内容与分治、随机化关系密切基础打牢之后可以直接连续学习。最好的验证标准很简单学完后能否在白板上手写随机化快速选择并解释清楚为什么它的期望复杂度是 O(n)而不是 O(n log n)。
