computer-science / algorithms
算法
排序、图搜索、动态规划、哈希、加密、机器学习——解决问题的配方
55 篇
排序算法
Sorting Algorithms
把一列数字从小到大排好，看起来是个简单到无聊的问题。但排序是计算机科学里被研究最深、影响最广的问题之一。操作系统调度任务、数据库查找记录、搜索引擎返回结果、基因组学处理 DNA 序列——背后几乎都有排序在工作。高德纳（Donald Knuth）在《计算机程序设计艺术》第三卷整本书讲排序与搜索，不是偶然。
排序 · 时间复杂度 · 比较排序
二分查找
Binary Search
在 1000 页的字典里查一个单词，没有人会从第一页开始逐页翻。人们翻到中间，判断目标词在左半还是右半，然后对着那半部分重复这个动作——几步就找到了。
二分查找 · 搜索算法 · 对数时间
被 2 个领域引用（数学、心理学）
图的遍历（BFS 与 DFS）
Graph Traversal — BFS and DFS
谷歌的网络爬虫访问 example.com，发现它链接到 a.com、b.com，然后访问 a.com，发现它链接到 c.com、d.com……这个过程叫做图遍历：系统地访问图中每一个可达节点，不重复、不遗漏。
BFS · DFS · 图遍历
被 2 个领域引用（数学、医学与公共卫生）
最短路径与 Dijkstra 算法
Shortest Path and Dijkstra's Algorithm
1956 年，荷兰计算机科学家艾兹赫尔·迪克斯特拉（Edsger W. Dijkstra）在阿姆斯特丹数学中心工作，那时没有鼠标、没有编辑器——程序员用铅笔在纸上写，然后把穿孔卡片送进去运行。
Dijkstra · 最短路径 · 图算法
被 1 个领域引用（生命科学）
字符串匹配
String Matching
每次你按下 Ctrl+F 搜索一个词，每次你的 IDE 给你标出一个错误，每次 grep 在日志文件里找到一行记录——背后都有一个字符串匹配算法在工作。
字符串匹配 · KMP算法 · Boyer-Moore
被 1 个领域引用（医学与公共卫生）
最小生成树
Minimum Spanning Tree
1926 年，捷克数学家奥塔卡尔·博鲁夫卡（Otakar Borůvka）受摩拉维亚电力公司委托，研究如何用最少的电线把全国所有城镇连接成电网。他发表了第一个求解最小生成树的算法——比 Kruskal 和 Prim 的工作早了整整 30 年。
最小生成树 · Kruskal算法 · Prim算法
快速傅里叶变换
Fast Fourier Transform (FFT)
1965 年，James Cooley 和 John Tukey 在 Mathematics of Computation 上发表了一篇五页的论文"An Algorithm for the Machine Calculation of Complex Fourier Series"，提出了快速傅里叶变换（FFT）算法。
FFT · 傅里叶变换 · 分治
被 5 个领域引用（数学、宇宙学、化学、语言学、宇宙物理）
霍夫曼编码
Huffman Coding
1951 年，麻省理工学院一门信息论课程上，教授 Robert Fano 给学生一个选择：要么参加期末考试，要么写一篇学期论文，证明一种最优的数据编码方案——能把信息压缩到尽可能短。Fano 自己（与香农一道）已经有一个接近但并非最优的方案（Shannon-Fano 编码）。
霍夫曼编码 · 数据压缩 · 贪心
被 2 个领域引用（生命科学、数学）
背包问题
Knapsack Problem
一位探险家准备出发，背包最多承重 $W$ 公斤。他面前有 $n$ 件宝物，每件有重量 $wi$ 和价值 $vi$。他应该带哪些宝物，才能让总价值最大，同时不超过背包承重？
背包问题 · 动态规划 · NP完全
被 1 个领域引用（医学与公共卫生）
正则表达式
Regular Expressions
注册表单里检查邮箱格式的那行校验、IDE 里按下 Ctrl+Shift+F 的全局搜索、运维在几十 GB 日志里捞出某个错误码的那条 grep——它们背后是同一个工具：正则表达式。
正则表达式 · 有限自动机 · NFA
动态规划
Dynamic Programming
"Dynamic Programming"这个名字，是 Richard Bellman（美国应用数学家）在 1950 年代发明的。
动态规划 · 最优子结构 · 记忆化
被 2 个领域引用（数学、经济学）
哈希
Hashing
有两件事，哈希函数都能做，而且性质完全不同：
哈希 · 哈希函数 · 哈希表
被 2 个领域引用（哲学思想、心理学）
贪心算法
Greedy Algorithms
1956 年，年轻的 Edsger Dijkstra 在为阿姆斯特丹数学中心编写程序时，想到了一个简洁到让人惊叹的主意：每次都走目前看起来最近的路，就这样，不回头。
贪心 · 最优子结构 · 局部最优
分治算法
Divide and Conquer
"分而治之"——这句话在政治上是权谋，在算法里是智慧。
分治 · 递归 · 主定理
被 1 个领域引用（宇宙学）
回溯算法
Backtracking
1848 年，国际象棋棋手 Max Bezzel 提出了一个看似简单的问题：把 8 个皇后放在 $8 \times 8$ 棋盘上，使得没有两个皇后互相攻击。这个问题有多少种放法？
回溯 · 搜索 · 剪枝
梯度下降与反向传播
Gradient Descent and Backpropagation
今天所有主流的神经网络——GPT、Stable Diffusion、AlphaFold、自动驾驶系统——都依赖两个核心算法在数以亿计的参数上共同工作：梯度下降告诉参数应该往哪个方向调整，反向传播高效地计算出"每个参数对误差贡献多少"。没有这两个算法，现代深度学习不可能在计算上可行。
梯度下降 · 反向传播 · 神经网络
被 2 个领域引用（数学、经济学）
K-means 聚类
K-means Clustering
1957 年，Bell Labs 的 Stuart Lloyd 开发了一种信号量化算法，用于将连续信号压缩为有限个离散值——他将类似的点"聚合"到同一个"中心"附近。这个方法在 Bell Labs 内部流传了二十多年，直到 1982 年才正式发表。
K-means · 聚类 · 无监督学习
被 3 个领域引用（宇宙学、数学、政治学）
决策树
Decision Trees
一个人去看医生，医生问：你发烧吗？是的。咳嗽吗？是的。呼吸困难吗？不。那么，可能是普通支气管炎。
决策树 · 信息增益 · 随机森林
被 4 个领域引用（宇宙学、经济学、医学与公共卫生、哲学思想）
支持向量机
Support Vector Machines
1995 年，贝尔实验室的科琳娜·科尔特斯（Corinna Cortes）和弗拉基米尔·万普尼克（Vladimir Vapnik）发表论文《支持向量网络》，奠定了支持向量机（Support Vector Machine, SVM）的现代形态。
支持向量机 · SVM · 核方法
被 2 个领域引用（宇宙学、数学）
随机森林
Random Forests
2001 年，利奥·布雷曼（Leo Breiman）在《机器学习》杂志发表了题为《随机森林》的论文，提出了一个简单但极其有效的思想：一棵决策树不稳定、容易过拟合，但一千棵随机生长的决策树投票，却能得到稳定而准确的预测。
随机森林 · 集成学习 · 决策树
被 1 个领域引用（化学）
梯度提升
Gradient Boosting
2001 年，斯坦福大学教授杰罗姆·弗里德曼（Jerome Friedman）发表论文《贪婪函数近似：梯度提升机》，将函数空间的梯度下降与集成学习结合，创造了梯度提升（Gradient Boosting）框架。
梯度提升 · XGBoost · 集成学习
Q 学习与强化学习
Q-Learning and Reinforcement Learning
1992 年，克里斯托弗·沃特金斯（Christopher Watkins）和彼得·达扬（Peter Dayan）发表论文，为 Q 学习（Q-Learning）算法提供了收敛证明。
Q学习 · 强化学习 · 马尔可夫决策过程
被 2 个领域引用（哲学思想、经济学）
主成分分析
Principal Component Analysis
主成分分析（Principal Component Analysis, PCA）的历史可以追溯到 1901 年，由卡尔·皮尔逊（Karl Pearson）在《哲学杂志》发表的论文中首次提出（作为拟合"最接近的直线和平面"的方法）；现代矩阵形式由哈罗德·霍特林（Harold Hotelling）在 1933 年完善。
PCA · 降维 · 特征提取
被 3 个领域引用（宇宙学、经济学、数学）
网络流
Network Flow
1956 年，美国空军系统分析师 T.E. Harris 写了一份机密备忘录，估算若苏联遭受核打击后，铁路网络能承载多少物资流量。这个问题后来成为一道经典算法题目的直接来源。
网络流 · 最大流 · 最小割
被 5 个领域引用（经济学、生命科学、医学与公共卫生、政治学、宇宙物理）
A* 搜索算法
A* Search Algorithm
1968 年，Stanford Research Institute 的三位研究员——Peter Hart、Nils Nilsson 和 Bertram Raphael——在开发一台机器人（Shakey）的导航系统时，需要一种高效的路径规划算法。
A* · 启发式搜索 · 路径规划
被 1 个领域引用（数学）
贝尔曼-福特算法
Bellman-Ford Algorithm
Richard Bellman（动态规划的奠基人）在 1958 年的论文《On a Routing Problem》中、Lester Ford Jr.（最大流-最小割定理的共同提出者，他与 Fulkerson 的最大流论文发表于 1956 年）在更早的 RAND 报告中，分别给出了处理含负权边图的最短路径算法。
贝尔曼-福特 · 最短路径 · 负权边
被 1 个领域引用（数学）
Floyd-Warshall 算法
Floyd-Warshall Algorithm
1962 年，两位研究者几乎同时发表了全对最短路径算法。Robert Floyd 在 Communications of the ACM 上发表了"Algorithm 97: Shortest Path"；Stephen Warshall 的先前工作（1962 年，针对图的传递闭包）提供了相同的矩阵递推框架。
Floyd-Warshall · 全对最短路 · 动态规划
拓扑排序
Topological Sort
你敲下 make 编译一个 C 项目，或者 npm install 装一堆依赖包：a.o 必须先于 b.o 编译，库 X 必须先于依赖它的库 Y 安装。构建工具要做的第一件事，就是把这张"谁依赖谁"的关系图，理成一条所有依赖都排在前面的执行顺序——这就是拓扑排序（Topological Sort）。
拓扑排序 · 有向无环图 · DAG
被 2 个领域引用（宇宙学、数学）
PageRank 算法
PageRank Algorithm
1998 年，斯坦福大学的两位博士生 Larry Page 和 Sergey Brin 在论文"The Anatomy of a Large-Scale Hypertextual Web Search Engine"中描述了一种给网页打分的方法，并用它建立了一个新的搜索引擎。
PageRank · 搜索引擎 · 随机游走
被 2 个领域引用（数学、哲学思想）
匹配算法
Matching Algorithms
1965 年，杰克·埃德蒙兹（Jack Edmonds）发表《Paths, Trees, and Flowers》。论文要解决的是一般图上的最大基数匹配：任意一对顶点最多共用一条边，怎样选出尽量多的边。二部图当时已有匈牙利方法和网络流；非二部图会被奇数环绊住。
二部匹配 · 霍普克罗夫特-卡普 · 花朵算法
堆与优先队列
Heaps and Priority Queues
想象一家急诊室：病人按紧迫程度（而不是到达时间）接受治疗。最危重的病人总是最先被处理，哪怕他是最后到达的。这就是优先队列的行为模型——一种"根据优先级出队"而非"先进先出"的数据结构。
堆 · 优先队列 · 二叉堆
被 1 个领域引用（经济学）
并查集
Union-Find (Disjoint Set Union)
一张有十亿用户的社交网络，好友关系不断新增。系统要随时回答："张三和李四，通过朋友的朋友的朋友……能不能连上？"
并查集 · 不相交集合 · 路径压缩
线段树
Segment Trees
考虑一个百万元素的数组，要回答几十万次这样的问询："第 30000 到 80000 个元素之和是多少？"——而且元素的值还会不断被修改。
线段树 · 区间查询 · 数据结构
跳表
Skip Lists
1990 年，威廉·普格（William Pugh）在《ACM 通讯》发表了《跳表：平衡树的概率替代》，提出了跳表（Skip List）这一数据结构。
跳表 · 有序数据结构 · 概率数据结构
布隆过滤器
Bloom Filter
1970 年，Burton Howard Bloom 在 Communications of the ACM 上发表了一篇不到 3 页的短文"Space/Time Trade-offs in Hash Coding with Allowable Errors"，提出了一种奇特的数据结构。
布隆过滤器 · 概率数据结构 · 哈希
流算法与草图
Streaming Algorithms and Sketches
路由器每秒转发的包数以千万计，日志不能全存。你仍想知道：有多少不同的源地址？哪个流最热？二次频率矩是否在飙升？
数据流 · HyperLogLog · Count-Min
模拟退火
Simulated Annealing
金属工匠早在几千年前就知道：将金属加热到高温后缓慢冷却（退火），能使原子找到低能量的稳定排列，消除内部应力，使材料更坚韧。
模拟退火 · 组合优化 · 元启发式
被 1 个领域引用（宇宙物理）
遗传算法
Genetic Algorithms
1975 年，密歇根大学教授约翰·霍兰德（John Holland）出版了《自然与人工系统中的适应》（Adaptation in Natural and Artificial Systems），正式确立了遗传算法（Genetic Algorithm, GA）的理论框架。
遗传算法 · 演化计算 · 元启发式
被 3 个领域引用（生命科学、化学、医学与公共卫生）
卷积神经网络
Convolutional Neural Networks
2012 年 9 月，ImageNet 大规模视觉识别竞赛（ILSVRC）的结果让整个计算机视觉社区震惊：来自多伦多大学的 AlexNet，由亚历克斯·克里热夫斯基（Alex Krizhevsky）、伊利亚·苏茨克维尔（Ilya Sutskever）和杰弗里·欣顿（Geoffrey Hinton）构建，以 15.3% 的错误率夺冠，比第二名低了近 11 个百分点。
卷积神经网络 · CNN · 深度学习
被 5 个领域引用（宇宙学、艺术、工程与技术、数学、医学与公共卫生）
循环神经网络
Recurrent Neural Networks
1986 年，大卫·鲁姆哈特（David Rumelhart）、杰弗里·欣顿（Geoffrey Hinton）和罗纳德·威廉姆斯（Ronald Williams）在提出反向传播算法的同一篇论文中，也提出了将其应用于循环网络的设想。
循环神经网络 · RNN · LSTM
注意力机制与 Transformer
Attention and Transformers
2017 年，谷歌大脑的八位研究员——阿希什·瓦斯瓦尼（Ashish Vaswani）等人——发表了题为《注意力就是一切》（Attention Is All You Need）的论文，提出了 Transformer 架构。
Transformer · 注意力机制 · 自注意力
被 5 个领域引用（哲学思想、心理学、教育学与学习科学、语言学、文学与叙事）
后缀树与后缀数组
Suffix Trees and Arrays
人类基因组包含约 32 亿个碱基对。生物信息学家每天都需要在其中寻找一段几十个字符的 DNA 序列——这是一个对 32 亿字符字符串做模式匹配的问题，而且同一个基因组上要做的不是一次查询，是成千上万次。能在合理时间内完成这项工作的数据结构，正是后缀树（Suffix Tree）和后缀数组（Suffix Array）。
后缀树 · 后缀数组 · 字符串算法
编辑距离算法
Edit Distance Algorithms
"您是要搜索 'Alber Einstien'？"
编辑距离 · 动态规划 · Levenshtein距离
被 2 个领域引用（生命科学、化学）
LRU 缓存淘汰算法
LRU Cache Eviction
每次你访问一个网站，浏览器从本地缓存中加载它，而不是从服务器重新下载——这背后有一个决策：当缓存满了，哪个页面应该被删除，为新内容腾出空间？
LRU · 缓存算法 · 内存管理
被 1 个领域引用（心理学）
限流算法
Rate Limiting Algorithms
你写了一个公开的 API，某天凌晨流量突然暴涨——可能是真实的爆款，也可能是某个客户端写错代码陷入死循环、每秒打来上万次请求，还可能是恶意攻击。如果什么都不做，你的服务器会被压垮，连正常用户也一起遭殃。限流（rate limiting） 就是给请求装上一个阀门：超过约定速率的请求被拒绝或排队，从而保护系统、保证公平。
限流 · 令牌桶 · 漏桶
被 3 个领域引用（经济学、宇宙学、政治学）
一致性哈希
Consistent Hashing
1997 年，大卫·卡格（David Karger）等人在 ACM STOC 会议上发表了论文《一致性哈希及随机树：分布式缓存协议以减轻万维网上的热点》（第 654 至 663 页）。
一致性哈希 · 分布式系统 · 负载均衡
MapReduce
MapReduce
2004 年，谷歌工程师杰弗里·迪恩（Jeffrey Dean）和桑贾伊·格马瓦特（Sanjay Ghemawat）发表了《MapReduce：大型集群上的简化数据处理》。
MapReduce · 分布式计算 · 大数据