History · Ideas Over Dates
算法与结构
发展史
下面按阶段写公开可核对的主线。精确到年的只写有共识的节点；其余写年代。思想线索比年表更重要：步骤如何被命名为算法，复杂度如何变成统一标尺，结构与算法怎样被写成一门课。
分治、贪心、动态规划在 20 世纪中后期被写成可教的套路。408 只收进大纲的实例，不把范式名当新结构。
Niklaus Wirth 1976 年的书名把两者并置。同一套操作换存储，界就变：这是本站线性表两章的来历。
最好 / 平均 / 最坏把「快」从口号变成可比较的界。平均必须带分布前提，不能只写一个 O()。
古典算法与词源
欧几里得《几何原本》里的辗转相除，是至今仍在用的古典算法：用有限、可重复的步骤求最大公约数。它比电子计算机早两千年，说明「算法」首先是步骤，不是某门编程语言。
9 世纪花剌子模的穆罕默德·本·穆萨（al-Khwarizmi）写算术与代数著作。其拉丁转写 Algoritmi 后来变成 algorithm 一词的词源。词源故事只解释名字，不证明某条现代算法是他发明的。
可计算性与复杂度
Alan Turing 1936 年的论文把「机械可计算」写成后来称为图灵机的模型；原论文处理的是 circle-free 等机器行为判定问题并据此解决 Entscheidungsproblem，奠定了后来通常以停机不可判定讲述的不可判定性结论。同一年代 Church、Kleene 等人的工作与之并列。可计算性回答「能不能算完」；复杂度回答「要多少步」。
1960–70 年代，复杂度类被写成可比较的对象。Stephen Cook 1971 年证明命题可满足性是 NP 完全的；Richard Karp 1972 年给出一批现已通称「Karp 的 21 个问题」的归约。Leonid Levin 在同一时期独立得到相近结论。P 与 NP 是否相等，至今仍是开放问题。
经典算法与结构
Edsger W. Dijkstra 1959 年发表关于图上两个问题的短文，其中给出了边权非负时的单源最短路方法——后来教材里的 Dijkstra 算法。同一篇也讨论了生成树，但最小生成树的常用署名是 Kruskal（1956）与 Prim（1957）；更早还有 Jarník 1930 年的独立工作。不要把 MST 全部记在 Dijkstra 名下。
C. A. R. Hoare 在 1959–1961 年间提出并发表快速排序。Donald Knuth 从 1968 年起陆续出版《计算机程序设计艺术》，把已有算法写成可核对的分析传统。Huffman 编码出现在 1952 年。AVL 树由 Adelson-Velsky 与 Landis 在 1962 年给出。红黑树的谱系通常追溯到 Bayer 1970 年代初的对称二叉 B 树，Guibas 与 Sedgewick 1978 年使用「红黑」这一称呼。
Knuth、Morris、Pratt 的串匹配论文发表于 1977 年（此前已有技术报告）。教材里的 next 数组是后来的教学整理，不是 1977 年论文的唯一写法。
工程、教材与竞赛
Wirth 1976 年的 Algorithms + Data Structures = Programs 将 algorithms 与 data structures 并置。此后大学课把线性表、树、图、排序当作常见核心模块，编排因教材而异；严蔚敏等国内教材、CLRS、Sedgewick 是同一门课的不同侧面。本站的读法是：结构选错，算法再巧也补不回来——这是本站观点，不是书中原话。
程序设计竞赛在 1970 年代于北美校园出现，后来形成 ACM-ICPC（今 ICPC）国际赛。国际信息学奥林匹克 IOI 始于 1989 年。中国的 NOI / OI 体系、以及后来的在线评测站（如洛谷、LeetCode、Codeforces 等）把刷题做成可公开参与的练习方式。竞赛训练题集不是 408 大纲本身。