computer-science / algorithms
算法
排序、图搜索、动态规划、哈希、加密、机器学习——解决问题的配方
52 篇
排序算法
Sorting Algorithms
把一列数字从小到大排好，看起来是个简单到无聊的问题。但排序是计算机科学里被研究最深、影响最广的问题之一。操作系统调度任务、数据库查找记录、搜索引擎返回结果、基因组学处理 DNA 序列——背后几乎都有排序在工作。高德纳（Donald Knuth）在《计算机程序设计艺术》第三卷整本书讲排序与搜索，不是偶然。 教科书常给学生…
排序 · 时间复杂度 · 比较排序
二分查找
Binary Search
在 1000 页的字典里查一个单词，没有人会从第一页开始逐页翻。人们翻到中间，判断目标词在左半还是右半，然后对着那半部分重复这个动作——几步就找到了。 这就是二分查找（Binary Search）的本质。它是最简单、最优雅的算法思想之一，也是"搜索有序结构"这类问题的理论最优解。
二分查找 · 搜索算法 · 对数时间
被 1 个领域引用（数学）
图的遍历（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）在阿姆斯特丹数学中心工作，那时没有鼠标、没有编辑器——程序员用铅笔在纸上写，然后把穿孔卡片送进去运行。 他在这年想出了一个算法，能找出加权图中任意两点之间的最短路径。这个算法今天仍然运行在全球每一台路由器上，也在你每次用导航 Ap…
Dijkstra · 最短路径 · 图算法
被 1 个领域引用（生命科学）
字符串匹配
String Matching
每次你按下 Ctrl+F 搜索一个词，每次你的 IDE 给你标出一个错误，每次 grep 在日志文件里找到一行记录——背后都有一个字符串匹配算法在工作。 字符串匹配听起来简单：给定文本 T（长度 n）和模式 P（长度 m），找出 P 在 T 中所有出现的位置。但"如何高效地做"这件事，包含了计算机科学中一些最精妙的思想…
字符串匹配 · 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 编码）。 学生 David Huffman 选择了写…
霍夫曼编码 · 数据压缩 · 贪心
被 2 个领域引用（生命科学、数学）
背包问题
Knapsack Problem
一位探险家准备出发，背包最多承重 $W$ 公斤。他面前有 $n$ 件宝物，每件有重量 $wi$ 和价值 $vi$。他应该带哪些宝物，才能让总价值最大，同时不超过背包承重？ 这就是著名的0-1 背包问题（0-1 Knapsack Problem）——"0-1"意味着每件物品要么完整带走（1），要么完全不带（0），不能只带…
背包问题 · 动态规划 · NP完全
被 1 个领域引用（医学与公共卫生）
正则表达式
Regular Expressions
注册表单里检查邮箱格式的那行校验、IDE 里按下 Ctrl+Shift+F 的全局搜索、运维在几十 GB 日志里捞出某个错误码的那条 grep——它们背后是同一个工具：正则表达式。 正则表达式是一种用紧凑的符号描述"一类字符串"的语言。比如 \d{4}-\d{2}-\d{2} 描述所有"四位数字-两位数字-两位数字"形…
正则表达式 · 有限自动机 · NFA
动态规划
Dynamic Programming
"Dynamic Programming"这个名字，是 Richard Bellman（美国应用数学家）在 1950 年代发明的。他后来在自传里坦承，选这个名字是因为"dynamic"听起来酷，而"programming"在当时意指"规划"（不是写代码），还因为他需要一个让军方资助人"无法反对"的词汇来隐藏他的数学研究…
动态规划 · 最优子结构 · 记忆化
被 2 个领域引用（数学、经济学）
哈希
Hashing
有两件事，哈希函数都能做，而且性质完全不同： 第一件：把任意数据映射到一个小的固定范围（如 0 到 999），用来快速查找——你在 Python 字典里每次用 dkey，背后就是这个。
哈希 · 哈希函数 · 哈希表
被 1 个领域引用（哲学思想）
贪心算法
Greedy Algorithms
1956 年，年轻的 Edsger Dijkstra 在为阿姆斯特丹数学中心编写程序时，想到了一个简洁到让人惊叹的主意：每次都走目前看起来最近的路，就这样，不回头。 这就是贪心算法的核心精神：在每一步，做出局部最优的选择，从不回溯。它不考虑未来，不担心后悔，只管眼前最好。
贪心 · 最优子结构 · 局部最优
分治算法
Divide and Conquer
"分而治之"——这句话在政治上是权谋，在算法里是智慧。 分治（Divide and Conquer）是最古老、最有力的算法设计范式之一。它的逻辑无比简单：把一个大问题拆成若干个同类小问题，递归地解决每个小问题，再把结果合并起来。
分治 · 递归 · 主定理
被 1 个领域引用（宇宙学）
回溯算法
Backtracking
1848 年，国际象棋棋手 Max Bezzel 提出了一个看似简单的问题：把 8 个皇后放在 $8 \times 8$ 棋盘上，使得没有两个皇后互相攻击。这个问题有多少种放法？ 92 种——这个答案在当时用穷举法需要很长时间。但一旦引入系统性的"尝试-撤销"策略，效率可以提高几个数量级。这就是回溯算法的精髓。
回溯 · 搜索 · 剪枝
梯度下降与反向传播
Gradient Descent and Backpropagation
今天所有主流的神经网络——GPT、Stable Diffusion、AlphaFold、自动驾驶系统——都依赖两个核心算法在数以亿计的参数上共同工作：梯度下降告诉参数应该往哪个方向调整，反向传播高效地计算出"每个参数对误差贡献多少"。没有这两个算法，现代深度学习不可能在计算上可行。 反向传播经常被错误地称为"神经网络的…
梯度下降 · 反向传播 · 神经网络
被 2 个领域引用（数学、经济学）
K-means 聚类
K-means Clustering
1957 年，Bell Labs 的 Stuart Lloyd 开发了一种信号量化算法，用于将连续信号压缩为有限个离散值——他将类似的点"聚合"到同一个"中心"附近。这个方法在 Bell Labs 内部流传了二十多年，直到 1982 年才正式发表。与此同时，James MacQueen 在 1967 年的论文中命名了"…
K-means · 聚类 · 无监督学习
被 3 个领域引用（宇宙学、数学、政治学）
决策树
Decision Trees
一个人去看医生，医生问：你发烧吗？是的。咳嗽吗？是的。呼吸困难吗？不。那么，可能是普通支气管炎。 这就是决策树的工作模式：通过一系列有序的问题，逐步将问题缩小到一个答案。它是最接近人类直觉推理的机器学习模型。
决策树 · 信息增益 · 随机森林
被 4 个领域引用（宇宙学、经济学、医学与公共卫生、哲学思想）
支持向量机
Support Vector Machines
1995 年，贝尔实验室的科琳娜·科尔特斯（Corinna Cortes）和弗拉基米尔·万普尼克（Vladimir Vapnik）发表论文《支持向量网络》，奠定了支持向量机（Support Vector Machine, SVM）的现代形态。其核心思想可追溯到更早：带核技巧的最大间隔分类器由 Boser、Guyon 与…
支持向量机 · SVM · 核方法
被 2 个领域引用（宇宙学、数学）
随机森林
Random Forests
2001 年，利奥·布雷曼（Leo Breiman）在《机器学习》杂志发表了题为《随机森林》的论文，提出了一个简单但极其有效的思想：一棵决策树不稳定、容易过拟合，但一千棵随机生长的决策树投票，却能得到稳定而准确的预测。 随机森林是当今工业界应用最广泛的机器学习算法之一。它不需要特征缩放，天然处理缺失值，提供特征重要性排…
随机森林 · 集成学习 · 决策树
被 1 个领域引用（化学）
梯度提升
Gradient Boosting
2001 年，斯坦福大学教授杰罗姆·弗里德曼（Jerome Friedman）发表论文《贪婪函数近似：梯度提升机》，将函数空间的梯度下降与集成学习结合，创造了梯度提升（Gradient Boosting）框架。此后，以此为基础的 XGBoost（2016）、LightGBM（2017）和 CatBoost（2017）横…
梯度提升 · XGBoost · 集成学习
Q 学习与强化学习
Q-Learning and Reinforcement Learning
1992 年，克里斯托弗·沃特金斯（Christopher Watkins）和彼得·达扬（Peter Dayan）发表论文，为 Q 学习（Q-Learning）算法提供了收敛证明。但这个算法在 2013-2015 年之前几乎只存在于学术研究中——直到 DeepMind 的研究员将 Q 学习与深度神经网络结合，创造了 D…
Q学习 · 强化学习 · 马尔可夫决策过程
被 2 个领域引用（哲学思想、经济学）
主成分分析
Principal Component Analysis
主成分分析（Principal Component Analysis, PCA）的历史可以追溯到 1901 年，由卡尔·皮尔逊（Karl Pearson）在《哲学杂志》发表的论文中首次提出（作为拟合"最接近的直线和平面"的方法）；现代矩阵形式由哈罗德·霍特林（Harold Hotelling）在 1933 年完善。 P…
PCA · 降维 · 特征提取
被 3 个领域引用（宇宙学、经济学、数学）
网络流
Network Flow
1956 年，美国空军系统分析师 T.E. Harris 写了一份机密备忘录，估算若苏联遭受核打击后，铁路网络能承载多少物资流量。这个问题后来成为一道经典算法题目的直接来源。同年，L.R. Ford Jr. 和 D.R. Fulkerson 在 Canadian Journal of Mathematics 上发表了"…
网络流 · 最大流 · 最小割
被 5 个领域引用（经济学、生命科学、医学与公共卫生、政治学、宇宙物理）
A* 搜索算法
A* Search Algorithm
1968 年，Stanford Research Institute 的三位研究员——Peter Hart、Nils Nilsson 和 Bertram Raphael——在开发一台机器人（Shakey）的导航系统时，需要一种高效的路径规划算法。 他们提出的算法发表在论文"A Formal Basis for the …
A* · 启发式搜索 · 路径规划
被 1 个领域引用（数学）
贝尔曼-福特算法
Bellman-Ford Algorithm
Richard Bellman（动态规划的奠基人）在 1958 年的论文《On a Routing Problem》中、Lester Ford Jr.（最大流-最小割定理的共同提出者，他与 Fulkerson 的最大流论文发表于 1956 年）在更早的 RAND 报告中，分别给出了处理含负权边图的最短路径算法。Alfo…
贝尔曼-福特 · 最短路径 · 负权边
被 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）。 Excel 也在做…
拓扑排序 · 有向无环图 · DAG
被 2 个领域引用（宇宙学、数学）
PageRank 算法
PageRank Algorithm
1998 年，斯坦福大学的两位博士生 Larry Page 和 Sergey Brin 在论文"The Anatomy of a Large-Scale Hypertextual Web Search Engine"中描述了一种给网页打分的方法，并用它建立了一个新的搜索引擎。他们把这个算法命名为"PageRank"——…
PageRank · 搜索引擎 · 随机游走
被 2 个领域引用（数学、哲学思想）
堆与优先队列
Heaps and Priority Queues
想象一家急诊室：病人按紧迫程度（而不是到达时间）接受治疗。最危重的病人总是最先被处理，哪怕他是最后到达的。这就是优先队列的行为模型——一种"根据优先级出队"而非"先进先出"的数据结构。 朴素地维护这样一个队列，每次取出"最紧迫的"都要扫一遍全部元素：一百万个元素里找最值要比较一百万次。堆（Heap）把这件事压到 $\l…
堆 · 优先队列 · 二叉堆
被 1 个领域引用（经济学）
并查集
Union-Find (Disjoint Set Union)
一张有十亿用户的社交网络，好友关系不断新增。系统要随时回答："张三和李四，通过朋友的朋友的朋友……能不能连上？" 每来一对询问就跑一次深度优先搜索？一次搜索要遍历整张图（$O(n + m)$）；十亿节点上做几百万次询问，等于把整张网络扫几百万遍——根本跑不动。
并查集 · 不相交集合 · 路径压缩
线段树
Segment Trees
考虑一个百万元素的数组，要回答几十万次这样的问询："第 30000 到 80000 个元素之和是多少？"——而且元素的值还会不断被修改。 朴素地每次从头加一遍，单次查询要扫 $n$ 个元素；一百万元素、十万次查询就是 $10^{11}$ 次加法，普通 CPU 要跑上分钟。线段树把单次查询和单次修改都压到 $\log2 …
线段树 · 区间查询 · 数据结构
跳表
Skip Lists
1990 年，威廉·普格（William Pugh）在《ACM 通讯》发表了《跳表：平衡树的概率替代》，提出了跳表（Skip List）这一数据结构。 普格开篇写道："平衡树……可以用于同样的问题，但效率要低得多，而且实现和调试更加困难……我们相信跳表比平衡树的代码更容易实现，而且更快。"三十年后，跳表成了 Redis…
跳表 · 有序数据结构 · 概率数据结构
模拟退火
Simulated Annealing
金属工匠早在几千年前就知道：将金属加热到高温后缓慢冷却（退火），能使原子找到低能量的稳定排列，消除内部应力，使材料更坚韧。1983 年，IBM 研究员柯克帕特里克（Scott Kirkpatrick）、葛莱特（C. D. Gelatt）和韦奇（M. P. Vecchi）将这个物理过程翻译成了优化算法——模拟退火（Sim…
模拟退火 · 组合优化 · 元启发式
被 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% …
卷积神经网络 · CNN · 深度学习
被 5 个领域引用（宇宙学、艺术、工程与技术、数学、医学与公共卫生）
循环神经网络
Recurrent Neural Networks
1986 年，大卫·鲁姆哈特（David Rumelhart）、杰弗里·欣顿（Geoffrey Hinton）和罗纳德·威廉姆斯（Ronald Williams）在提出反向传播算法的同一篇论文中，也提出了将其应用于循环网络的设想。循环神经网络（Recurrent Neural Network, RNN）随后成为处理语言…
循环神经网络 · RNN · LSTM
注意力机制与 Transformer
Attention and Transformers
2017 年，谷歌大脑的八位研究员——阿希什·瓦斯瓦尼（Ashish Vaswani）等人——发表了题为《注意力就是一切》（Attention Is All You Need）的论文，提出了 Transformer 架构。这篇论文彻底改变了人工智能的方向：GPT、BERT、T5、PaLM、LLaMA、Gemini——今…
Transformer · 注意力机制 · 自注意力
被 3 个领域引用（哲学思想、心理学、语言学）
后缀树与后缀数组
Suffix Trees and Arrays
人类基因组包含约 32 亿个碱基对。生物信息学家每天都需要在其中寻找一段几十个字符的 DNA 序列——这是一个对 32 亿字符字符串做模式匹配的问题，而且同一个基因组上要做的不是一次查询，是成千上万次。能在合理时间内完成这项工作的数据结构，正是后缀树（Suffix Tree）和后缀数组（Suffix Array）。 普…
后缀树 · 后缀数组 · 字符串算法
编辑距离算法
Edit Distance Algorithms
"您是要搜索 'Alber Einstien'？" 搜索引擎能识别你的拼写错误，文本编辑器能自动纠错，DNA 序列能被比对到参考基因组——这些背后都有同一个算法：编辑距离（Edit Distance），或称 Levenshtein 距离。
编辑距离 · 动态规划 · Levenshtein距离
被 2 个领域引用（生命科学、化学）
LRU 缓存淘汰算法
LRU Cache Eviction
每次你访问一个网站，浏览器从本地缓存中加载它，而不是从服务器重新下载——这背后有一个决策：当缓存满了，哪个页面应该被删除，为新内容腾出空间？ 最近最少使用（Least Recently Used, LRU） 是这个问题最经典的答案：删除最久没有被访问的那个。
LRU · 缓存算法 · 内存管理
限流算法
Rate Limiting Algorithms
你写了一个公开的 API，某天凌晨流量突然暴涨——可能是真实的爆款，也可能是某个客户端写错代码陷入死循环、每秒打来上万次请求，还可能是恶意攻击。如果什么都不做，你的服务器会被压垮，连正常用户也一起遭殃。限流（rate limiting） 就是给请求装上一个阀门：超过约定速率的请求被拒绝或排队，从而保护系统、保证公平。 …
限流 · 令牌桶 · 漏桶
被 3 个领域引用（经济学、宇宙学、政治学）
一致性哈希
Consistent Hashing
1997 年，大卫·卡格（David Karger）等人在 ACM STOC 会议上发表了论文《一致性哈希及随机树：分布式缓存协议以减轻万维网上的热点》（第 654 至 663 页）。当时的背景是万维网流量爆炸：热门内容把单个源站服务器打垮，而多台缓存服务器分摊内容时又面临一个痛苦的现实问题——当分布式缓存集群中一台服…
一致性哈希 · 分布式系统 · 负载均衡
MapReduce
MapReduce
2004 年，谷歌工程师杰弗里·迪恩（Jeffrey Dean）和桑贾伊·格马瓦特（Sanjay Ghemawat）发表了《MapReduce：大型集群上的简化数据处理》。这篇论文描述了 Google 内部用于处理 PB 级数据的编程模型，并在发表后迅速成为大数据时代的基础范式，催生了 Hadoop 生态系统，影响了此…
MapReduce · 分布式计算 · 大数据