最近在系统啃 MIT 6.854 Advanced Algorithms也就是国内很多研究生和算法岗同学都会参考的《高级算法》课程。这门课覆盖的知识面很广哈希、流算法、线性规划、半定规划、压缩感知每一讲单独拿出来都能写一篇长文。网上关于这门课的零散笔记不少但大多数只贴 PPT 截图缺少一条能把“理论—算法—应用”串起来的完整路线。所以本文想以课程为主线把每块核心主题的原理、关键算法、适合的项目场景和可上手的代码示例整理成一份偏实战的课程学习笔记。无论是正在修这门课的研究生还是准备面试算法岗、想补强理论基础的后端开发者这篇文章都适合收藏后慢慢看。在正式展开前先说清一个概念MIT 6.854 讲的是“高级算法”不是传统的“数据结构与算法入门”。它默认你已经掌握分治、排序、图论、动态规划这些基础然后在此基础上深入讨论更复杂的算法设计与分析工具。课程难度偏大数学推导多但每一讲都对应真实工程中频繁出现的问题模型。把它学扎实对后续看论文、做系统设计、写高性能组件都有帮助。1. 课程整体脉络与学习收益1.1 这门课到底讲什么MIT 6.854 的完整名称是 Advanced Algorithms属于麻省理工学院计算机科学方向的研究生核心课程。它和本科阶段的数据结构课最大的区别在于数据结构课的重点是“工具的使用”而 6.854 的重点是“工具为什么有效、什么时候失效、怎么设计新工具”。课程覆盖的模块大致如下哈希与数据结构 流算法与子线性空间算法 线性规划与对偶 半定规划与特征值优化 压缩感知与稀疏恢复 近似算法与随机算法其中标题提到的“哈希、流算法、线性规划、半定规划、压缩感知”是课程中最有代表性的五块内容。它们虽然在授课顺序上相互独立但在思想上一脉相承都是利用某种数学结构在资源受限的情况下解决计算问题。1.2 适合哪些读者从实际读者画像来看以下三类人群最适合学习并阅读这篇笔记计算机、数学、统计相关专业的研究生正在修高级算法课程。准备算法岗、基础架构岗面试想补强随机化算法与优化理论基础的候选人。对大数据处理、推荐系统、图像压缩、网络测量等方向感兴趣想了解底层算法原理的工程师。如果你目前还处于刚学完《算法导论》的阶段建议先把基础数据结构掌握扎实再来啃 6.854否则容易陷入“每个字都认识、连起来不知道在说什么”的困境。1.3 学完后能获得什么理解哈希表背后的数学保证能分析不同哈希策略的均匀性。掌握流算法中“亚线性空间”的核心思想知道如何在海量数据中估计频次、基数、Top-K。能够把业务建模成线性规划问题并用对偶理论分析最优解结构。了解半定规划在组合优化和机器学习中的应用看懂相关论文中的 SDP 松弛。掌握压缩感知的稀疏恢复思想理解为什么 L1 范数能够代替 L0 范数做优化。2. 哈希从工程工具到算法思想哈希是这门课最早进入深水区的主题也是网络热搜词中出现频率最高的一块。很多人对哈希的理解停留在“HashMap 的 key 经过哈希函数映射到数组下标”但 6.854 中的哈希是更高维度的算法设计工具。2.1 哈希表的核心模型先看一个最简单的哈希表示例。假设我们要存储若干个整数期望在 O(1) 期望时间内完成插入、删除、查找。最容易想到的模型是数组长度 m 哈希函数 h: U - {0, 1, ..., m-1}当两个不同元素映射到同一个槽位时就产生哈希冲突。解决冲突的经典方式有链地址法和开放地址法。链地址法把冲突元素挂成链表开放地址法通过线性探测、二次探测或双重哈希寻找下一个空闲槽位。其中开放地址法的探测序列设计非常考验哈希函数质量。下面用 C 给出一个开放地址法定长哈希表的极简实现重点展示哈希冲突存在时如何向后探测// 文件路径hash_table_open_addressing.cpp #include iostream #include vector class OpenAddressingHashTable { private: std::vectorint table; std::vectorbool used; int capacity; // 哈希函数取模 int hash(int key) { return key % capacity; } // 线性探测 int probe(int key) { int index hash(key); while (used[index]) { index (index 1) % capacity; } return index; } public: OpenAddressingHashTable(int cap) : capacity(cap) { table.resize(cap, -1); used.resize(cap, false); } void insert(int key) { int index probe(key); table[index] key; used[index] true; } bool find(int key) { int index hash(key); while (used[index]) { if (table[index] key) { return true; } index (index 1) % capacity; } return false; } }; int main() { OpenAddressingHashTable ht(10); ht.insert(5); ht.insert(15); // 和 5 冲突放到下一个位置 std::cout ht.find(15) std::endl; // 输出 1 return 0; }这个示例是最基础的线性探测。问题也很明显当哈希函数的质量较差时元素会聚集成长长的连续占用区查找退化到 O(n)。因此现实中更常用双重哈希来分散探测序列而非线性探测。2.2 原地哈希空间受限的编程技巧热搜词中出现的“原地哈希”是一个很有工程价值的技巧。它的核心思想是在数组本来就有空间的情况下利用下标本身作为哈希地址直接在原数组上完成映射不额外申请空间。最经典的例题是“找到数组中第一个缺失的正整数”// 文件路径first_missing_positive.cpp #include vector #include iostream using namespace std; int firstMissingPositive(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { while (nums[i] 1 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums[nums[i] - 1], nums[i]); } } for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; } int main() { vectorint nums {3, 4, -1, 1}; cout firstMissingPositive(nums) endl; // 输出 2 return 0; }这里的关键点在于nums[nums[i] - 1]用元素值推导出它应当存放的下标类似于把“值”作为“键”直接做原地哈希。工程中原地哈希常用于内存敏感的场景比如嵌入式设备的去重、日志文件的离线分组。2.3 哈希函数的工程选择网络热搜词里多次出现“哈希算法”“C哈希怎么写”“哈希表开放地址法”这其实说明了同一个问题的不同侧面很多人需要的是一个“能跑”的哈希而不是一个“有理论保证”的哈希。在工程中选择哈希函数需要关注三件事均匀性尽量让数据分布到所有桶避免热点。效率哈希计算本身要快否则会成为瓶颈。安全性如果面对恶意输入需要抗碰撞的加密哈希例如 SHA-256如果只是内部 HashMapMD5 或非加密哈希足够。需要注意的是MD5 和 SHA-1 目前已被认为在安全场景下不够安全建议在签名、证书、口令存储等场景改用 SHA-256 或更高强度算法。但如果只是用来做数据分片或一致性哈希MD5 仍然大量出现在历史系统中。这里补充一个 C 语言风格的增量哈希计算库设计思路支持分块输入适合大文件的哈希校验// 文件路径incremental_hash_example.c #include stdio.h #include string.h #include openssl/sha.h int main() { SHA256_CTX ctx; unsigned char hash[SHA256_DIGEST_LENGTH]; char buf[1024]; size_t n; FILE* fp fopen(largefile.bin, rb); if (!fp) return 1; SHA256_Init(ctx); while ((n fread(buf, 1, sizeof(buf), fp)) 0) { SHA256_Update(ctx, buf, n); } SHA256_Final(hash, ctx); for (int i 0; i SHA256_DIGEST_LENGTH; i) { printf(%02x, hash[i]); } printf(\n); fclose(fp); return 0; }这段代码演示了“分块增量输入”思想无需一次性把整个文件载入内存边读边更新哈希上下文适合超大文件的完整性校验。核心结构Init - Update - Final是几乎所有哈希库的通用模式。2.4 从哈希到随机化算法6.854 将哈希升级为随机化算法的核心工具。最典型的案例是布隆过滤器Bloom Filter它用多个哈希函数把元素映射到一个位数组上以极低的内存代价判断“元素是否可能存在”。布隆过滤器的基本结构初始化 m 位数组全部置 0。插入元素时用 k 个哈希函数得到 k 个位置全部置 1。查询元素时检查 k 个位置是否全部为 1如果存在一个位置为 0则一定不存在如果全部为 1则可能存在也可能误判。布隆过滤器的误判率公式为误判率 ≈ (1 - e^(-kn/m))^k其中 n 是插入元素数量m 是位数组长度k 是哈希函数数量。当 k (m/n) * ln2 时误判率最低。这套思想在流算法里还会再次出现。可以说哈希不只是数据结构更是一种“用概率换空间”的算法设计哲学。3. 流算法处理海量数据的亚线性空间艺术3.1 为什么需要流算法在实际业务中我们经常会遇到“数据量大到无法存进内存”的场景统计某天访问网站的独立 IP 数。从千万级日志中实时计算 Top-K 热词。统计一个无限数据流中每个元素出现的频次。如果数据流无限增长用 HashMap 保存所有 key 显然不可行。流算法的目标就是在数据只能顺序读取一次、内存远小于数据规模的情况下给出近似结果。3.2 水库抽样等概率采样未知总量数据水库抽样用于从长度未知的数据流中随机抽取 k 个样本保证每个元素被抽中的概率相等。算法思路前 k 个元素直接放入“水库”。从第 k1 个元素开始以 k/i 的概率决定是否用当前元素替换水库中的随机一个元素。下面用 Python 实现# 文件路径reservoir_sampling.py import random def reservoir_sampling(stream, k): reservoir [] for i, item in enumerate(stream): if i k: reservoir.append(item) else: j random.randint(0, i) if j k: reservoir[j] item return reservoir # 模拟数据流 stream list(range(1, 10001)) sample reservoir_sampling(stream, 10) print(sample)这个算法的精妙之处在于不需要知道流的总长度空间复杂度为 O(k)时间复杂度 O(n)。常用于日志随机抽样、A/B 测试样本抽取、分布式系统中的负载均衡样本维护。3.3 Flajolet-Martin估计基数Flajolet-Martin 算法用于估计数据流中不同元素的数量也就是基数。它的核心思想是通过哈希函数将元素映射成长度固定的二进制串记录哈希结果中“末尾连续零的个数”然后根据尾部零的最大长度推导基数。直觉解释如果哈希函数是理想的均匀随机函数那么哈希值的第 r 位为 0 的概率是 2^(-r)。如果数据流中有 N 个不同元素那么尾部零的最大长度大约是 log2(N)。因此通过维护哈希结果尾部零的最大值可以反推出基数。该算法是 HyperLogLog 的前身。HyperLogLog 进一步优化了估计精度是 Redis 中 PFCOUNT 命令的底层实现。3.4 Count-Min Sketch频次估计Count-Min Sketch 是流算法中非常实用的频率估计数据结构。它的结构是 d 行 w 列的二维数组每行对应一个哈希函数。插入元素时对每一行计算哈希找到对应列加 1。查询元素频次时取所有行对应列的最小值作为频次的估计值。# 文件路径count_min_sketch.py import hashlib class CountMinSketch: def __init__(self, width, depth): self.width width self.depth depth self.table [[0] * width for _ in range(depth)] def _hash(self, item, seed): # 用不同的种子构造不同哈希函数 h hashlib.md5(f{seed}:{item}.encode()) return int(h.hexdigest(), 16) % self.width def add(self, item, count1): for d in range(self.depth): idx self._hash(item, d) self.table[d][idx] count def estimate(self, item): return min(self.table[d][self._hash(item, d)] for d in range(self.depth)) # 示例 cms CountMinSketch(width100, depth5) for word in [apple, banana, apple, orange, apple]: cms.add(word) print(cms.estimate(apple)) # 输出 3Count-Min Sketch 的误差范围由 w 和 d 决定w 越大精度越高d 越大越能降低哈希冲突导致的过估风险。工程中常用于网络流量测量、热词统计、数据库基数的预估计。3.5 流算法在课程中的地位在 6.854 课程中流算法属于“亚线性空间算法”这一讲。核心思想可以总结为用近似答案换取内存空间的极大节省。Google 的 BigQuery、ClickHouse 等系统在聚合查询中大量使用该类算法来降低内存压力。4. 线性规划建模与对偶4.1 线性规划的基本形式线性规划Linear ProgrammingLP是在一组线性约束条件下优化一个线性目标函数的问题。标准形式如下最大化 / 最小化c^T x 约束条件Ax b, x 0其中 c、x 是 n 维向量A 是 m×n 矩阵b 是 m 维向量。线性规划的应用场景非常广泛物流运输成本最小化。生产计划中的资源分配。投资组合的风险收益建模。网络流问题。4.2 一个最小的 Python 线性规划示例使用scipy.optimize.linprog可以快速求解线性规划。下面示例演示如何求解一个简单的最大化问题。问题假设生产两种产品 x1、x2每种产品消耗不同资源目标最大化利润 3x1 4x2。约束条件x1 2*x2 8 3*x1 2*x2 12 x1, x2 0# 文件路径linear_programming_example.py from scipy.optimize import linprog # scipy 默认求最小化因此最大化 3*x1 4*x2 等价于最小化 -3*x1 - 4*x2 c [-3, -4] # 约束矩阵 A_ub * x b_ub A_ub [ [1, 2], [3, 2] ] b_ub [8, 12] # 变量边界 x 0 bounds [(0, None), (0, None)] result linprog(c, A_ubA_ub, b_ubb_ub, boundsbounds, methodhighs) print(result) print(最优解 x1, x2:, result.x) print(最大利润:, -result.fun)methodhighs是 SciPy 1.6 默认推荐的求解器它实现了内点法和单纯形法的混合策略数值稳定性远超旧版默认配置。4.3 单纯形法与内点法6.854 课程重点介绍了两种主流求解算法单纯形法沿可行域的顶点移动目标函数值逐步改善。最坏情况是指数复杂度但实际场景通常表现优秀。内点法从可行域内部沿中心路径逼近最优解多项式复杂度适合大规模问题。理解线性规划的关键不只是在代码里调用linprog而是要学会“建模”。工程中真正难的不是求解而是把业务约束转成不等式。4.4 对偶理论观察问题的另一面对偶理论是线性规划中最深刻的部分。每个线性规划问题都有一个对应的对偶问题。原始问题和对偶问题的最优值相等满足强对偶条件时。对偶理论的意义在于提供最优性的验证手段。用于敏感度分析和影子价格。在近似算法设计中给出下界。例如最大流问题的最小割问题实际上就是一个强对偶关系的经典案例。课程后面讲近似算法和在线算法时对偶思维会被反复使用。5. 半定规划从线性规划到矩阵优化5.1 什么是半定规划半定规划Semidefinite ProgrammingSDP是线性规划的推广。LP 的变量是向量约束是线性不等式SDP 的变量是矩阵约束是“矩阵半正定”。半正定矩阵的定义是对于任意非零向量 x都有 x^T M x 0。记作 M ⪰ 0。一个标准 SDP 形式最大化 / 最小化tr(C X) 约束条件tr(A_i X) b_i X ⪰ 0其中 tr 表示矩阵的迹。5.2 半定规划的典型应用SDP 在组合优化和机器学习中有重要应用。最经典的例子是 Max-Cut 问题的 SDP 松弛。Max-Cut 问题给定一个无向图把顶点分成两组使被切断的边权总和最大。这是一个 NP-hard 问题。但通过 SDP 松弛可以在多项式时间内得到近似比为 0.878 的近似解这是 Goemans 和 Williamson 在 1994 年得到的著名结果。SDP 在其他方向的常见应用还包括传感器网络定位。蛋白质结构预测。机器学习中的核矩阵学习。信号处理中的波束成形。5.3 用 CVXPY 求解一个简单的 SDP在工程中如果只是验证一个 SDP 模型推荐使用 CVXPY 搭配 SCS 或 MOSEK 求解器。安装命令pip install cvxpy下面是一个简单的 SDP 示例寻找一个 2×2 半正定矩阵 X使得它的迹最大同时满足 X[0][0] 1。# 文件路径sdp_example.py import cvxpy as cp X cp.Variable((2, 2), symmetricTrue) # 目标函数最大化迹 objective cp.Maximize(cp.trace(X)) # 约束半正定 X[0][0] 1 constraints [X 0, X[0][0] 1] problem cp.Problem(objective, constraints) problem.solve() print(状态:, problem.status) print(最优值:, problem.value) print(最优 X:\n, X.value)这里的X 0是 CVXPY 中定义“X 半正定”的语法。运行后可以看到最优解满足对称性和半正定性。SDP 对初学者的最大挑战不是语法而是理解“为什么矩阵半正定约束能松绑原来的 NP-hard 问题”。我的建议是先跳过严格证明把 SDP 当作一种“把离散选择放松成连续向量内积”的工具来理解多看 Max-Cut 松弛的推导过程。6. 压缩感知稀疏性与 L1 范数6.1 问题背景压缩感知Compressed Sensing研究的是能否从远少于奈奎斯特采样定理要求的样本数中精确恢复原始信号这个问题的前提是信号本身具有稀疏性。也就是说信号在某个变换域下的大多数系数为 0。例如自然图像在小波变换下通常表现出良好的稀疏性。6.2 稀疏恢复的数学模型假设我们有一个稀疏信号 x ∈ R^n通过测量矩阵 A ∈ R^(m×n) 得到测量值 y A x其中 m n。压缩感知的目标是从 y 中恢复 x。直接求解 L0 范数最小化问题是 NP-hard 的因为需要穷举所有非零系数的位置。但神奇之处在于在满足约束等距性质RIP的条件下L1 范数最小化可以精确恢复原始信号最小化||x||_1 约束A x y这就是 L1 范数魔法它在稀疏约束下是可解的凸优化问题同时能诱导出稀疏解。相比 L2 范数L1 范数会把“多余”的系数压缩到 0。6.3 Python 实现压缩感知恢复下面用一个简单示例演示如何用 L1 范数最小化恢复稀疏信号。这里需要安装numpy和cvxpy。# 文件路径compressed_sensing.py import numpy as np import cvxpy as cp n 100 # 原始信号长度 m 50 # 测量数量 k 10 # 稀疏度 # 生成稀疏信号 np.random.seed(42) x_true np.zeros(n) nonzero_idx np.random.choice(n, k, replaceFalse) x_true[nonzero_idx] np.random.randn(k) # 随机测量矩阵 A np.random.randn(m, n) y A x_true # L1 范数最小化 x cp.Variable(n) objective cp.Minimize(cp.norm(x, 1)) constraints [A x y] problem cp.Problem(objective, constraints) problem.solve() x_hat x.value # 恢复误差 error np.linalg.norm(x_hat - x_true) print(f恢复误差: {error:.6f})如果测量矩阵满足 RIP并且 m 足够大大约 m k * log(n/k)恢复误差会非常接近 0。压缩感知在工程中的典型应用核磁共振成像MRI加速采样。相机中的单像素成像。频谱感知。无线通信中的信道估计。6.4 与课程模块的关系压缩感知在 6.854 中属于较靠后的专题它综合运用了线性代数、凸优化、随机矩阵理论和概率不等式。如果你已经理解线性规划和半定规划的基础再看压缩感知的 L1 恢复证明会顺畅很多。7. 学习这门课的高频问题与排查思路在自学过程中很多读者会遇到类似的困难。下面整理成一张表格方便对照排查。问题现象常见原因解决思路课程讲义能看懂但作业做不出来知识点停留在“听懂”阶段缺乏推导训练先抄写一遍核心证明再合上笔记独立推导看到 SDP 松弛就犯迷糊没有理解 LP 对偶和矩阵不等式的几何意义回看线性规划的顶点与对偶章节多画二维三维图流算法的近似率不会分析随机变量定义不清先写清楚期望和方差表达式再套用 Chernoff 界Python 调用 cvxpy 报错求解器未安装或版本不匹配检查pip list确认已安装 scs、ecos 或 mosek压缩感知 RIP 条件不知道如何验证RIP 是理论保证不是实用判据实际工程中直接比较恢复误差不要试图精确计算 RIP 常数哈希表的开放地址法删除元素后查询异常删除后没有标记墓碑删除操作应引入“已删除”标记查询时跳过墓碑8. 最佳实践与自学建议8.1 重视和手推相结合的练习习惯高级算法课程最大的特征是证明密度高。每讲至少有三到五个关键定理。建议不要只读证明而是把证明过程当作“路线图”自己尝试重新走一遍。最好的检测方法是合上笔记尝试独立证明一遍。如果卡住超过十分钟再回看讲义。8.2 用代码验证算法思想很多算法只有在亲手实现后才会变得立体。哈希链地址法和开放地址法可以在代码层面直观感受冲突率差异Count-Min Sketch 可以用来统计日志中的热词验证误差范围是否和理论公式一致线性规划和半定规划可以直接用 cvxpy 建模求解观察最优解结构。8.3 建立“模型-算法-应用”的映射强烈建议给每个主题建立一张映射表数学思想典型算法工程应用哈希均匀性布隆过滤器网页去重、缓存穿透防护亚线性空间估计Count-Min Sketch流式热词统计LP 建模与对偶单纯形法资源分配、网络流SDP 松弛内点法Max-Cut 近似、传感器定位稀疏恢复L1 最小化MRI 加速、信号压缩把这轮映射做下来你再去读论文或做技术方案时会更容易看出问题的本质适合套用哪种数学模型。8.4 注意安全与隐私边界如果课程中涉及的哈希、概率数据结构用于生产环境请特别注意数据安全和隐私合规哈希脱敏不等于完全匿名低熵输入仍然可能被穷举还原。布隆过滤器无法删除元素不适合需要频繁删除的隐私数据场景。流算法给出的是近似值如果用于计费或审计必须评估误差容忍度。涉及数据库、用户数据、敏感指标时需要在测试环境充分验证后再上线并保留数据备份。8.5 不要盲目追求全部细节6.854 的每一讲都可以扩展成独立课程。如果你只是工程方向不需要深挖所有定理的证明细节。建议优先级如下高优先级哈希、流算法、线性规划、对偶、L1 稀疏恢复 中优先级半定规划、随机算法、近似算法 低优先级复杂平摊分析、高级数据结构的内部证明按照优先级分配时间和精力才能在一个学期内把最有价值的算法思想吃透。9. 总结与延伸学习路线这篇文章围绕 MIT 6.854 的核心模块梳理了哈希、流算法、线性规划、半定规划、压缩感知五条主线。每个模块都给了数学模型、核心算法和可运行的代码示例并整理了自学者常见的问题排查思路。如果你刚开始接触这门课建议先按照下面顺序学习先复习矩阵论基础包括特征值分解、奇异值分解、正定矩阵。掌握线性规划的建模和对偶理论这是后续 SDP 的基础。重点学习哈希与流算法它们工程属性强容易获得正反馈。再进入半定规划和压缩感知的专题推导。每学完一个模块用 Python 实现一次核心算法。如果在学习过程中遇到具体报错比如 cvxpy 安装不上、哈希表实现导致死循环、流算法误差过大等问题可以把代码和报错信息整理出来按“现象—原因—解决”的方式排查这也是研究生阶段最需要锻炼的能力。希望这份笔记能成为你啃下 6.854 的一份实用参考。 MIT 6.854高级算法实战笔记：哈希、流算法与优化理论全解析
最近在系统啃 MIT 6.854 Advanced Algorithms也就是国内很多研究生和算法岗同学都会参考的《高级算法》课程。这门课覆盖的知识面很广哈希、流算法、线性规划、半定规划、压缩感知每一讲单独拿出来都能写一篇长文。网上关于这门课的零散笔记不少但大多数只贴 PPT 截图缺少一条能把“理论—算法—应用”串起来的完整路线。所以本文想以课程为主线把每块核心主题的原理、关键算法、适合的项目场景和可上手的代码示例整理成一份偏实战的课程学习笔记。无论是正在修这门课的研究生还是准备面试算法岗、想补强理论基础的后端开发者这篇文章都适合收藏后慢慢看。在正式展开前先说清一个概念MIT 6.854 讲的是“高级算法”不是传统的“数据结构与算法入门”。它默认你已经掌握分治、排序、图论、动态规划这些基础然后在此基础上深入讨论更复杂的算法设计与分析工具。课程难度偏大数学推导多但每一讲都对应真实工程中频繁出现的问题模型。把它学扎实对后续看论文、做系统设计、写高性能组件都有帮助。1. 课程整体脉络与学习收益1.1 这门课到底讲什么MIT 6.854 的完整名称是 Advanced Algorithms属于麻省理工学院计算机科学方向的研究生核心课程。它和本科阶段的数据结构课最大的区别在于数据结构课的重点是“工具的使用”而 6.854 的重点是“工具为什么有效、什么时候失效、怎么设计新工具”。课程覆盖的模块大致如下哈希与数据结构 流算法与子线性空间算法 线性规划与对偶 半定规划与特征值优化 压缩感知与稀疏恢复 近似算法与随机算法其中标题提到的“哈希、流算法、线性规划、半定规划、压缩感知”是课程中最有代表性的五块内容。它们虽然在授课顺序上相互独立但在思想上一脉相承都是利用某种数学结构在资源受限的情况下解决计算问题。1.2 适合哪些读者从实际读者画像来看以下三类人群最适合学习并阅读这篇笔记计算机、数学、统计相关专业的研究生正在修高级算法课程。准备算法岗、基础架构岗面试想补强随机化算法与优化理论基础的候选人。对大数据处理、推荐系统、图像压缩、网络测量等方向感兴趣想了解底层算法原理的工程师。如果你目前还处于刚学完《算法导论》的阶段建议先把基础数据结构掌握扎实再来啃 6.854否则容易陷入“每个字都认识、连起来不知道在说什么”的困境。1.3 学完后能获得什么理解哈希表背后的数学保证能分析不同哈希策略的均匀性。掌握流算法中“亚线性空间”的核心思想知道如何在海量数据中估计频次、基数、Top-K。能够把业务建模成线性规划问题并用对偶理论分析最优解结构。了解半定规划在组合优化和机器学习中的应用看懂相关论文中的 SDP 松弛。掌握压缩感知的稀疏恢复思想理解为什么 L1 范数能够代替 L0 范数做优化。2. 哈希从工程工具到算法思想哈希是这门课最早进入深水区的主题也是网络热搜词中出现频率最高的一块。很多人对哈希的理解停留在“HashMap 的 key 经过哈希函数映射到数组下标”但 6.854 中的哈希是更高维度的算法设计工具。2.1 哈希表的核心模型先看一个最简单的哈希表示例。假设我们要存储若干个整数期望在 O(1) 期望时间内完成插入、删除、查找。最容易想到的模型是数组长度 m 哈希函数 h: U - {0, 1, ..., m-1}当两个不同元素映射到同一个槽位时就产生哈希冲突。解决冲突的经典方式有链地址法和开放地址法。链地址法把冲突元素挂成链表开放地址法通过线性探测、二次探测或双重哈希寻找下一个空闲槽位。其中开放地址法的探测序列设计非常考验哈希函数质量。下面用 C 给出一个开放地址法定长哈希表的极简实现重点展示哈希冲突存在时如何向后探测// 文件路径hash_table_open_addressing.cpp #include iostream #include vector class OpenAddressingHashTable { private: std::vectorint table; std::vectorbool used; int capacity; // 哈希函数取模 int hash(int key) { return key % capacity; } // 线性探测 int probe(int key) { int index hash(key); while (used[index]) { index (index 1) % capacity; } return index; } public: OpenAddressingHashTable(int cap) : capacity(cap) { table.resize(cap, -1); used.resize(cap, false); } void insert(int key) { int index probe(key); table[index] key; used[index] true; } bool find(int key) { int index hash(key); while (used[index]) { if (table[index] key) { return true; } index (index 1) % capacity; } return false; } }; int main() { OpenAddressingHashTable ht(10); ht.insert(5); ht.insert(15); // 和 5 冲突放到下一个位置 std::cout ht.find(15) std::endl; // 输出 1 return 0; }这个示例是最基础的线性探测。问题也很明显当哈希函数的质量较差时元素会聚集成长长的连续占用区查找退化到 O(n)。因此现实中更常用双重哈希来分散探测序列而非线性探测。2.2 原地哈希空间受限的编程技巧热搜词中出现的“原地哈希”是一个很有工程价值的技巧。它的核心思想是在数组本来就有空间的情况下利用下标本身作为哈希地址直接在原数组上完成映射不额外申请空间。最经典的例题是“找到数组中第一个缺失的正整数”// 文件路径first_missing_positive.cpp #include vector #include iostream using namespace std; int firstMissingPositive(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { while (nums[i] 1 nums[i] n nums[nums[i] - 1] ! nums[i]) { swap(nums[nums[i] - 1], nums[i]); } } for (int i 0; i n; i) { if (nums[i] ! i 1) { return i 1; } } return n 1; } int main() { vectorint nums {3, 4, -1, 1}; cout firstMissingPositive(nums) endl; // 输出 2 return 0; }这里的关键点在于nums[nums[i] - 1]用元素值推导出它应当存放的下标类似于把“值”作为“键”直接做原地哈希。工程中原地哈希常用于内存敏感的场景比如嵌入式设备的去重、日志文件的离线分组。2.3 哈希函数的工程选择网络热搜词里多次出现“哈希算法”“C哈希怎么写”“哈希表开放地址法”这其实说明了同一个问题的不同侧面很多人需要的是一个“能跑”的哈希而不是一个“有理论保证”的哈希。在工程中选择哈希函数需要关注三件事均匀性尽量让数据分布到所有桶避免热点。效率哈希计算本身要快否则会成为瓶颈。安全性如果面对恶意输入需要抗碰撞的加密哈希例如 SHA-256如果只是内部 HashMapMD5 或非加密哈希足够。需要注意的是MD5 和 SHA-1 目前已被认为在安全场景下不够安全建议在签名、证书、口令存储等场景改用 SHA-256 或更高强度算法。但如果只是用来做数据分片或一致性哈希MD5 仍然大量出现在历史系统中。这里补充一个 C 语言风格的增量哈希计算库设计思路支持分块输入适合大文件的哈希校验// 文件路径incremental_hash_example.c #include stdio.h #include string.h #include openssl/sha.h int main() { SHA256_CTX ctx; unsigned char hash[SHA256_DIGEST_LENGTH]; char buf[1024]; size_t n; FILE* fp fopen(largefile.bin, rb); if (!fp) return 1; SHA256_Init(ctx); while ((n fread(buf, 1, sizeof(buf), fp)) 0) { SHA256_Update(ctx, buf, n); } SHA256_Final(hash, ctx); for (int i 0; i SHA256_DIGEST_LENGTH; i) { printf(%02x, hash[i]); } printf(\n); fclose(fp); return 0; }这段代码演示了“分块增量输入”思想无需一次性把整个文件载入内存边读边更新哈希上下文适合超大文件的完整性校验。核心结构Init - Update - Final是几乎所有哈希库的通用模式。2.4 从哈希到随机化算法6.854 将哈希升级为随机化算法的核心工具。最典型的案例是布隆过滤器Bloom Filter它用多个哈希函数把元素映射到一个位数组上以极低的内存代价判断“元素是否可能存在”。布隆过滤器的基本结构初始化 m 位数组全部置 0。插入元素时用 k 个哈希函数得到 k 个位置全部置 1。查询元素时检查 k 个位置是否全部为 1如果存在一个位置为 0则一定不存在如果全部为 1则可能存在也可能误判。布隆过滤器的误判率公式为误判率 ≈ (1 - e^(-kn/m))^k其中 n 是插入元素数量m 是位数组长度k 是哈希函数数量。当 k (m/n) * ln2 时误判率最低。这套思想在流算法里还会再次出现。可以说哈希不只是数据结构更是一种“用概率换空间”的算法设计哲学。3. 流算法处理海量数据的亚线性空间艺术3.1 为什么需要流算法在实际业务中我们经常会遇到“数据量大到无法存进内存”的场景统计某天访问网站的独立 IP 数。从千万级日志中实时计算 Top-K 热词。统计一个无限数据流中每个元素出现的频次。如果数据流无限增长用 HashMap 保存所有 key 显然不可行。流算法的目标就是在数据只能顺序读取一次、内存远小于数据规模的情况下给出近似结果。3.2 水库抽样等概率采样未知总量数据水库抽样用于从长度未知的数据流中随机抽取 k 个样本保证每个元素被抽中的概率相等。算法思路前 k 个元素直接放入“水库”。从第 k1 个元素开始以 k/i 的概率决定是否用当前元素替换水库中的随机一个元素。下面用 Python 实现# 文件路径reservoir_sampling.py import random def reservoir_sampling(stream, k): reservoir [] for i, item in enumerate(stream): if i k: reservoir.append(item) else: j random.randint(0, i) if j k: reservoir[j] item return reservoir # 模拟数据流 stream list(range(1, 10001)) sample reservoir_sampling(stream, 10) print(sample)这个算法的精妙之处在于不需要知道流的总长度空间复杂度为 O(k)时间复杂度 O(n)。常用于日志随机抽样、A/B 测试样本抽取、分布式系统中的负载均衡样本维护。3.3 Flajolet-Martin估计基数Flajolet-Martin 算法用于估计数据流中不同元素的数量也就是基数。它的核心思想是通过哈希函数将元素映射成长度固定的二进制串记录哈希结果中“末尾连续零的个数”然后根据尾部零的最大长度推导基数。直觉解释如果哈希函数是理想的均匀随机函数那么哈希值的第 r 位为 0 的概率是 2^(-r)。如果数据流中有 N 个不同元素那么尾部零的最大长度大约是 log2(N)。因此通过维护哈希结果尾部零的最大值可以反推出基数。该算法是 HyperLogLog 的前身。HyperLogLog 进一步优化了估计精度是 Redis 中 PFCOUNT 命令的底层实现。3.4 Count-Min Sketch频次估计Count-Min Sketch 是流算法中非常实用的频率估计数据结构。它的结构是 d 行 w 列的二维数组每行对应一个哈希函数。插入元素时对每一行计算哈希找到对应列加 1。查询元素频次时取所有行对应列的最小值作为频次的估计值。# 文件路径count_min_sketch.py import hashlib class CountMinSketch: def __init__(self, width, depth): self.width width self.depth depth self.table [[0] * width for _ in range(depth)] def _hash(self, item, seed): # 用不同的种子构造不同哈希函数 h hashlib.md5(f{seed}:{item}.encode()) return int(h.hexdigest(), 16) % self.width def add(self, item, count1): for d in range(self.depth): idx self._hash(item, d) self.table[d][idx] count def estimate(self, item): return min(self.table[d][self._hash(item, d)] for d in range(self.depth)) # 示例 cms CountMinSketch(width100, depth5) for word in [apple, banana, apple, orange, apple]: cms.add(word) print(cms.estimate(apple)) # 输出 3Count-Min Sketch 的误差范围由 w 和 d 决定w 越大精度越高d 越大越能降低哈希冲突导致的过估风险。工程中常用于网络流量测量、热词统计、数据库基数的预估计。3.5 流算法在课程中的地位在 6.854 课程中流算法属于“亚线性空间算法”这一讲。核心思想可以总结为用近似答案换取内存空间的极大节省。Google 的 BigQuery、ClickHouse 等系统在聚合查询中大量使用该类算法来降低内存压力。4. 线性规划建模与对偶4.1 线性规划的基本形式线性规划Linear ProgrammingLP是在一组线性约束条件下优化一个线性目标函数的问题。标准形式如下最大化 / 最小化c^T x 约束条件Ax b, x 0其中 c、x 是 n 维向量A 是 m×n 矩阵b 是 m 维向量。线性规划的应用场景非常广泛物流运输成本最小化。生产计划中的资源分配。投资组合的风险收益建模。网络流问题。4.2 一个最小的 Python 线性规划示例使用scipy.optimize.linprog可以快速求解线性规划。下面示例演示如何求解一个简单的最大化问题。问题假设生产两种产品 x1、x2每种产品消耗不同资源目标最大化利润 3x1 4x2。约束条件x1 2*x2 8 3*x1 2*x2 12 x1, x2 0# 文件路径linear_programming_example.py from scipy.optimize import linprog # scipy 默认求最小化因此最大化 3*x1 4*x2 等价于最小化 -3*x1 - 4*x2 c [-3, -4] # 约束矩阵 A_ub * x b_ub A_ub [ [1, 2], [3, 2] ] b_ub [8, 12] # 变量边界 x 0 bounds [(0, None), (0, None)] result linprog(c, A_ubA_ub, b_ubb_ub, boundsbounds, methodhighs) print(result) print(最优解 x1, x2:, result.x) print(最大利润:, -result.fun)methodhighs是 SciPy 1.6 默认推荐的求解器它实现了内点法和单纯形法的混合策略数值稳定性远超旧版默认配置。4.3 单纯形法与内点法6.854 课程重点介绍了两种主流求解算法单纯形法沿可行域的顶点移动目标函数值逐步改善。最坏情况是指数复杂度但实际场景通常表现优秀。内点法从可行域内部沿中心路径逼近最优解多项式复杂度适合大规模问题。理解线性规划的关键不只是在代码里调用linprog而是要学会“建模”。工程中真正难的不是求解而是把业务约束转成不等式。4.4 对偶理论观察问题的另一面对偶理论是线性规划中最深刻的部分。每个线性规划问题都有一个对应的对偶问题。原始问题和对偶问题的最优值相等满足强对偶条件时。对偶理论的意义在于提供最优性的验证手段。用于敏感度分析和影子价格。在近似算法设计中给出下界。例如最大流问题的最小割问题实际上就是一个强对偶关系的经典案例。课程后面讲近似算法和在线算法时对偶思维会被反复使用。5. 半定规划从线性规划到矩阵优化5.1 什么是半定规划半定规划Semidefinite ProgrammingSDP是线性规划的推广。LP 的变量是向量约束是线性不等式SDP 的变量是矩阵约束是“矩阵半正定”。半正定矩阵的定义是对于任意非零向量 x都有 x^T M x 0。记作 M ⪰ 0。一个标准 SDP 形式最大化 / 最小化tr(C X) 约束条件tr(A_i X) b_i X ⪰ 0其中 tr 表示矩阵的迹。5.2 半定规划的典型应用SDP 在组合优化和机器学习中有重要应用。最经典的例子是 Max-Cut 问题的 SDP 松弛。Max-Cut 问题给定一个无向图把顶点分成两组使被切断的边权总和最大。这是一个 NP-hard 问题。但通过 SDP 松弛可以在多项式时间内得到近似比为 0.878 的近似解这是 Goemans 和 Williamson 在 1994 年得到的著名结果。SDP 在其他方向的常见应用还包括传感器网络定位。蛋白质结构预测。机器学习中的核矩阵学习。信号处理中的波束成形。5.3 用 CVXPY 求解一个简单的 SDP在工程中如果只是验证一个 SDP 模型推荐使用 CVXPY 搭配 SCS 或 MOSEK 求解器。安装命令pip install cvxpy下面是一个简单的 SDP 示例寻找一个 2×2 半正定矩阵 X使得它的迹最大同时满足 X[0][0] 1。# 文件路径sdp_example.py import cvxpy as cp X cp.Variable((2, 2), symmetricTrue) # 目标函数最大化迹 objective cp.Maximize(cp.trace(X)) # 约束半正定 X[0][0] 1 constraints [X 0, X[0][0] 1] problem cp.Problem(objective, constraints) problem.solve() print(状态:, problem.status) print(最优值:, problem.value) print(最优 X:\n, X.value)这里的X 0是 CVXPY 中定义“X 半正定”的语法。运行后可以看到最优解满足对称性和半正定性。SDP 对初学者的最大挑战不是语法而是理解“为什么矩阵半正定约束能松绑原来的 NP-hard 问题”。我的建议是先跳过严格证明把 SDP 当作一种“把离散选择放松成连续向量内积”的工具来理解多看 Max-Cut 松弛的推导过程。6. 压缩感知稀疏性与 L1 范数6.1 问题背景压缩感知Compressed Sensing研究的是能否从远少于奈奎斯特采样定理要求的样本数中精确恢复原始信号这个问题的前提是信号本身具有稀疏性。也就是说信号在某个变换域下的大多数系数为 0。例如自然图像在小波变换下通常表现出良好的稀疏性。6.2 稀疏恢复的数学模型假设我们有一个稀疏信号 x ∈ R^n通过测量矩阵 A ∈ R^(m×n) 得到测量值 y A x其中 m n。压缩感知的目标是从 y 中恢复 x。直接求解 L0 范数最小化问题是 NP-hard 的因为需要穷举所有非零系数的位置。但神奇之处在于在满足约束等距性质RIP的条件下L1 范数最小化可以精确恢复原始信号最小化||x||_1 约束A x y这就是 L1 范数魔法它在稀疏约束下是可解的凸优化问题同时能诱导出稀疏解。相比 L2 范数L1 范数会把“多余”的系数压缩到 0。6.3 Python 实现压缩感知恢复下面用一个简单示例演示如何用 L1 范数最小化恢复稀疏信号。这里需要安装numpy和cvxpy。# 文件路径compressed_sensing.py import numpy as np import cvxpy as cp n 100 # 原始信号长度 m 50 # 测量数量 k 10 # 稀疏度 # 生成稀疏信号 np.random.seed(42) x_true np.zeros(n) nonzero_idx np.random.choice(n, k, replaceFalse) x_true[nonzero_idx] np.random.randn(k) # 随机测量矩阵 A np.random.randn(m, n) y A x_true # L1 范数最小化 x cp.Variable(n) objective cp.Minimize(cp.norm(x, 1)) constraints [A x y] problem cp.Problem(objective, constraints) problem.solve() x_hat x.value # 恢复误差 error np.linalg.norm(x_hat - x_true) print(f恢复误差: {error:.6f})如果测量矩阵满足 RIP并且 m 足够大大约 m k * log(n/k)恢复误差会非常接近 0。压缩感知在工程中的典型应用核磁共振成像MRI加速采样。相机中的单像素成像。频谱感知。无线通信中的信道估计。6.4 与课程模块的关系压缩感知在 6.854 中属于较靠后的专题它综合运用了线性代数、凸优化、随机矩阵理论和概率不等式。如果你已经理解线性规划和半定规划的基础再看压缩感知的 L1 恢复证明会顺畅很多。7. 学习这门课的高频问题与排查思路在自学过程中很多读者会遇到类似的困难。下面整理成一张表格方便对照排查。问题现象常见原因解决思路课程讲义能看懂但作业做不出来知识点停留在“听懂”阶段缺乏推导训练先抄写一遍核心证明再合上笔记独立推导看到 SDP 松弛就犯迷糊没有理解 LP 对偶和矩阵不等式的几何意义回看线性规划的顶点与对偶章节多画二维三维图流算法的近似率不会分析随机变量定义不清先写清楚期望和方差表达式再套用 Chernoff 界Python 调用 cvxpy 报错求解器未安装或版本不匹配检查pip list确认已安装 scs、ecos 或 mosek压缩感知 RIP 条件不知道如何验证RIP 是理论保证不是实用判据实际工程中直接比较恢复误差不要试图精确计算 RIP 常数哈希表的开放地址法删除元素后查询异常删除后没有标记墓碑删除操作应引入“已删除”标记查询时跳过墓碑8. 最佳实践与自学建议8.1 重视和手推相结合的练习习惯高级算法课程最大的特征是证明密度高。每讲至少有三到五个关键定理。建议不要只读证明而是把证明过程当作“路线图”自己尝试重新走一遍。最好的检测方法是合上笔记尝试独立证明一遍。如果卡住超过十分钟再回看讲义。8.2 用代码验证算法思想很多算法只有在亲手实现后才会变得立体。哈希链地址法和开放地址法可以在代码层面直观感受冲突率差异Count-Min Sketch 可以用来统计日志中的热词验证误差范围是否和理论公式一致线性规划和半定规划可以直接用 cvxpy 建模求解观察最优解结构。8.3 建立“模型-算法-应用”的映射强烈建议给每个主题建立一张映射表数学思想典型算法工程应用哈希均匀性布隆过滤器网页去重、缓存穿透防护亚线性空间估计Count-Min Sketch流式热词统计LP 建模与对偶单纯形法资源分配、网络流SDP 松弛内点法Max-Cut 近似、传感器定位稀疏恢复L1 最小化MRI 加速、信号压缩把这轮映射做下来你再去读论文或做技术方案时会更容易看出问题的本质适合套用哪种数学模型。8.4 注意安全与隐私边界如果课程中涉及的哈希、概率数据结构用于生产环境请特别注意数据安全和隐私合规哈希脱敏不等于完全匿名低熵输入仍然可能被穷举还原。布隆过滤器无法删除元素不适合需要频繁删除的隐私数据场景。流算法给出的是近似值如果用于计费或审计必须评估误差容忍度。涉及数据库、用户数据、敏感指标时需要在测试环境充分验证后再上线并保留数据备份。8.5 不要盲目追求全部细节6.854 的每一讲都可以扩展成独立课程。如果你只是工程方向不需要深挖所有定理的证明细节。建议优先级如下高优先级哈希、流算法、线性规划、对偶、L1 稀疏恢复 中优先级半定规划、随机算法、近似算法 低优先级复杂平摊分析、高级数据结构的内部证明按照优先级分配时间和精力才能在一个学期内把最有价值的算法思想吃透。9. 总结与延伸学习路线这篇文章围绕 MIT 6.854 的核心模块梳理了哈希、流算法、线性规划、半定规划、压缩感知五条主线。每个模块都给了数学模型、核心算法和可运行的代码示例并整理了自学者常见的问题排查思路。如果你刚开始接触这门课建议先按照下面顺序学习先复习矩阵论基础包括特征值分解、奇异值分解、正定矩阵。掌握线性规划的建模和对偶理论这是后续 SDP 的基础。重点学习哈希与流算法它们工程属性强容易获得正反馈。再进入半定规划和压缩感知的专题推导。每学完一个模块用 Python 实现一次核心算法。如果在学习过程中遇到具体报错比如 cvxpy 安装不上、哈希表实现导致死循环、流算法误差过大等问题可以把代码和报错信息整理出来按“现象—原因—解决”的方式排查这也是研究生阶段最需要锻炼的能力。希望这份笔记能成为你啃下 6.854 的一份实用参考。