算法与数据结构

算法学科简史：人物、事件与流派

01-基础与复杂度分析入门预计 15 分钟历史人物流派
学习状态：

一句话定义

算法学科史是「算法」从算术程式（9 世纪花拉子米）到可计算性理论（1936 图灵机）、再到以复杂度为核心的现代学科（1970s NP 完全理论）的演化脉络，以及由此分化出的理论、工程、竞赛三大流派。

为什么重要

今天的每个「标准结论」都曾是某个具体问题逼出来的发明：知道 Dijkstra 1959 年在 20 分钟内想出最短路算法、知道 Knuth 为写书发明了 TeX，你才能把「经典」还原为「人在约束下的创造」，既避免把定理当天降真理，也理解学科为何长成今天的形状——这直接塑造你学习时的取舍。

前置知识

kp-001；对「时间线」叙事的基本阅读能力即可。

核心概念

  • 前史：「algorithm」源自 9 世纪波斯数学家花拉子米（al-Khwārizmī）；欧几里得辗转相除法（约公元前 300 年）是最古老记录在案的算法。
  • 奠基（1930s）：哥德尔不完备定理与图灵机（1936）把「可计算」形式化，划出算法能力的理论边界。
  • 成型（1950s–60s）：Dijkstra 最短路（1959）、Kruskal/Prim 最小生成树（1956/1957）、Quicksort（Hoare, 1961）、B 树雏形（1970 前后）随工业计算兴起。
  • 学科化（1962–1974）：Knuth 开始出版《计算机程序设计艺术》（TAOCP），首次把算法分析变成系统学科。
  • 复杂度时代（1971–）：Cook 提出 NP 完全（1971），Karp 归约 21 个问题（1972），「P vs NP」成为核心悬案。
  • 繁荣（1970s–90s）：KMP 字符串匹配（1977）、Tarjan 并查集分析（1975）、RSA（1977）、FFT 应用（Cooley–Tukey 1965）、LSM-Tree（1996）。
  • 当代：随机化与近似算法、MapReduce/流式算法、学习型索引等把「算法」推进到系统与数据 scale 的战场。

原理与机制

学科演化的反复机制是「问题压力 → 理论抽象 → 工具沉淀」：工业计算的压力逼出 Dijkstra 最短路、快速排序等具体算法；Cook/Karp 的复杂度理论把这些个案抽象成可归类的普适语言；Knuth 的 TAOCP 再把散落的成果沉淀为系统学科。理解这条循环，就能解释为什么每次硬件变革（磁盘、分布式、GPU）都会催生一批新结构，而不是旧结构被简单淘汰。

直观类比

把学科史看成一条河流：可计算性理论是上游泉眼，1950s 工业计算是降雨带来的径流，Knuth 修坝蓄水（系统化），Cook/Karp 开凿出复杂度这条主河道，今天的工程与竞赛都是下游灌溉区。

图示

前300年 欧几里得算法
  825  花拉子米《代数学》（algorithm 词源）
 1936  图灵机：可计算性边界
 1956-61 Kruskal / Prim / Dijkstra / Hoare
 1962- TAOCP 出版计划启动（Knuth）
 1965  Cooley–Tukey FFT
 1971  Cook：NP 完全 → 1972 Karp 21 问题
 1975-77 Tarjan 并查集 / KMP / RSA
 1996- LSM-Tree；2000s 随机化、流式、学习型方法

实例或案例

  • 理论流派：以复杂度类、随机化、近似算法为语言，代表如 Cook、Karp、Tarjan；关心「什么能做、多快是极限」。
  • 工程流派：以系统约束为语言，代表如 Bentley（《编程珠玑》）、数据库与存储引擎设计者；关心「在真实硬件与数据规模上怎么跑赢」。
  • 竞赛流派：OI/ACM-ICPC 训练体系，把大量结构（线段树、并查集、后缀数组）打磨成肌肉记忆；关心「限时内正确实现」。
  • Dijkstra 1959 年那篇论文只有两页多，却同时给出 Dijkstra 算法并顺带定义了后来被称为「栈」的结构雏形——好工作常常短小。

常见误区

  • 认为算法 = 竞赛：竞赛是训练场之一，学科主体是理论与工程两大版图。
  • 以为「NP = 无解/不可计算」：NP 是「解可在多项式时间内验证」，NP 完全问题目前只是「未找到多项式算法」，与图灵不可判定是两回事。
  • 把顺序读成「取代」：LSM 没有淘汰 B+ 树，随机化没有淘汰确定性算法——新范式是扩展问题域，不是推翻旧结论。

自测题

  1. 「algorithm」一词的词源是什么？

答案要点：9 世纪数学家花拉子米（al-Khwārizmī）名字的拉丁化。

  1. NP 完全理论由谁在何年奠定？它和「图灵不可判定」的区别是什么？

答案要点：Cook 1971 提出、Karp 1972 推广；NP 完全谈的是多项式时间内求解的困难度，不可判定谈的是根本没有算法，二者层次不同。

  1. 三大流派各自最关心什么？举一个你在本库后续会遇到的代表人物/成果。

答案要点：理论—极限与归类（如 Tarjan 并查集分析）；工程—真实系统效率（如 Bentley 排序工程化）；竞赛—限时实现（如并查集、线段树）。举例合理即可。

与其他知识点的关系

kp-001 给出概念快照，本节给出概念的运动轨迹；kp-015 的 LSM、kp-030 的 Tarjan 分析、kp-033 的伦理议题都有一条可回溯的历史线。

延伸阅读

《计算机程序设计艺术》卷一前言（关于「程序设计作为艺术」的论述）；Knuth, "Computer Programming as an Art"（1974 图灵奖演说）。

前置知识点

相关知识点

暂无。