English
For a programmer, an algorithm is a method for solving a computational problem that can be analyzed before it is run: given a description of the inputs, you can reason about whether it will produce the right output, and how long it will take, and how much memory it will use. This is what separates an algorithm from a program that happens to work. A program you have only tested gives you evidence about specific inputs; an algorithm you have analyzed gives you guarantees about all inputs of the relevant kind. The distinction matters because software deployed at scale will encounter inputs that no test anticipated.
A data structure is a way of organizing data so that specific operations on it are efficient. The choice is not aesthetic. An unsorted list finds an element by scanning from the beginning — O(n) time regardless of input. A hash table finds it in expected constant time. A balanced binary search tree finds it in O(log n) time and additionally keeps elements in sorted order. The algorithm and the data structure it operates on are not independent choices: they co-determine each other’s cost, and the central skill of this subject is matching the right combination to the problem at hand.
Algorithms and data structures is the subject concerned with the design, analysis, and correctness of computational procedures. It sits near the base of the field — discrete mathematics (§2.2) and the ability to write and run code (§2.1) are the direct prerequisites, probability (§2.5) is needed for randomized methods — and almost everything downstream draws on it: databases, compilers, graphics, machine learning, distributed systems are all, in part, applications of algorithm design.
How the Study of Procedures Became a Mathematical Discipline
For most of recorded history, an algorithm was a recipe, and whether it was correct was settled by trying it. Euclid described a procedure for the greatest common divisor around 300 BCE and, unusually, argued that it always terminates with the right answer. The word “algorithm” itself descends from the Latinization of al-Khwārizmī’s name — the ninth-century mathematician whose textbook taught Europe to calculate with Hindu-Arabic numerals. But for two thousand years, the question of how fast a procedure ran was barely asked, for a reason that explains why the subject is young: until machines could execute procedures automatically, the slow step was always the human carrying them out, and counting a procedure’s abstract steps served little purpose.
The subject became a science when Donald Knuth began publishing The Art of Computer Programming in 1968. Knuth’s contribution was a reframing: the cost of an algorithm can be studied mathematically, independent of any particular machine, by asking how its number of steps grows as the input grows. An algorithm is not simply fast or slow — it has a growth rate, a property of the algorithm itself, knowable and provable before running it. This came with the asymptotic notation that suppresses irrelevant constants to expose the qualitative behavior (big-O), a method (count operations as a function of input size), and a standard inherited from mathematics: prove that an algorithm is correct for all inputs, not merely that it has produced correct output on the inputs tested. The line this draws — between an algorithm observed to work and one proven to work — is the line between programming as craft and algorithms as science.
With analysis established as the method, the field began accumulating results, and one of the most consequential was a discovery about what is impossible. Through the 1960s, computer scientists had assembled a collection of problems that resisted efficient solution — finding the shortest tour through a set of cities, scheduling tasks under constraints, satisfying a system of logical conditions. Each had been attacked separately, and each had resisted, so the working assumption was that every one simply awaited its own clever insight. In 1971, Stephen Cook, with Leonid Levin arriving independently in the Soviet Union, showed the assumption was wrong. Cook proved that one problem — Boolean satisfiability, asking whether a logical formula can be made true by some assignment of values — had a remarkable property: every problem in a vast natural class could be mechanically rewritten as an instance of it in polynomial time. Richard Karp showed the same of twenty-one other problems the following year. These problems were not separately hard; they were the same hardness in different disguises. Solve any one efficiently and you solve them all. This is the origin of the P vs. NP question, now the most famous open problem in computer science. Nearly everyone believes the answer implies no efficient exact solution exists for these problems, and no proof has settled it after half a century. What the discovery changed was the field’s posture: proving that no good algorithm exists is as valuable a result as producing one, and recognizing NP-completeness is the productive response to a certain class of failure — not a personal deficiency but a structural fact about the problem.
The third development is quieter and surfaces when theory meets a real machine. Knuth’s analysis assumed a model in which every basic operation costs the same and every memory location is equally fast to reach — the RAM model, a fair approximation to 1970s hardware. A great deal of algorithm analysis is still conducted in it. But the model has drifted from reality. A modern processor sees memory as a hierarchy: a handful of values reachable in a single cycle, caches reachable in a few cycles, main memory that takes hundreds of cycles. An algorithm that performs fewer operations but scatters them across distant memory can run several times slower than one that performs more operations while keeping its data close. Binary search is optimal in the RAM model; on large data a B-tree, which performs more comparisons but stores related keys in contiguous blocks, routinely outperforms it because it was designed for the hierarchy the model elides. The lesson is not that the theory is wrong. Asymptotic analysis correctly answers whether an algorithm scales; it does not answer whether it is fast on a particular machine with a particular input. The distance between those two questions is where algorithm engineering operates: cache-aware data structures, empirical profiling, designing along the grain of real hardware.
These three movements — the founding of rigorous analysis, the discovery that intractability has provable structure, and the reckoning between idealized cost models and real machines — have left the subject unusually stable at its center. The major algorithms, data structures, and proof techniques have changed little in decades; what a student learns today about sorting, shortest paths, and dynamic programming is nearly what a student learned in 1990. This stability is rare in computer science and is a quiet argument for mastering the subject carefully: the investment does not expire. The active edges belong to the third movement. The plateau in processor clock speeds around 2005 forced serious attention to parallel and distributed algorithms, where many classical sequential results have no efficient counterpart. The deepening memory hierarchy makes algorithm engineering increasingly important. And there is live, unsettled work on whether learned data structures — indexes and data structures that adapt to their data using ML — can displace hand-designed ones in some domains. Each of these directions sits on top of the classical core, not in place of it.
Correctness, Cost, and the Limits of What Is Possible
The subject organizes itself around three recurring questions and the design vocabulary that connects them.
Proving Correctness and Characterizing Cost
Correctness is not a matter of testing well. A proof of correctness establishes that an algorithm produces the right output for every valid input — covering the infinite cases that no test suite reaches. The standard tools are mathematical induction (for algorithms on naturally ordered inputs), loop invariants (for iterative procedures — a property maintained before and after every iteration that implies correctness when the loop terminates), and structural induction (for recursive algorithms — prove the claim for base cases and show it holds for the recursive case if it holds for the subproblems). Each technique is a way of making a finite argument that ranges over an infinite domain.
Cost analysis begins with asymptotic notation. An algorithm that performs f(n) operations on input of size n is O(g(n)) if f grows no faster than g: there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. The constants are suppressed to expose the growth rate, which determines qualitative behavior at scale. The gap between complexity classes is enormous. An O(n²) algorithm on a million inputs performs a trillion operations — at 10⁹ operations per second, that is over fifteen minutes. An O(n log n) algorithm on the same input performs roughly twenty million operations — about twenty milliseconds. No hardware choice closes a gap of this magnitude; only the algorithm choice does.
Recurrence relations express the cost of recursive algorithms in terms of smaller instances. Mergesort divides the input in half, recurses on both halves, and merges in linear time: T(n) = 2T(n/2) + O(n). The Master Theorem resolves this recurrence to T(n) = O(n log n). Setting up and solving recurrences is the core analytical skill for recursive algorithms; the technique connects directly to the discrete mathematics of §2.2 and to the probability of §2.5 for randomized algorithms.
Amortized analysis handles data structures whose operations occasionally cost more than usual. Appending to a dynamic array is O(1) most of the time, but O(n) when the array must be resized. The right measure for a data structure is not the worst-case cost of any single operation but the average cost over a realistic sequence: amortized analysis shows that dynamic array append is O(1) amortized, because the expensive resizing operations are infrequent enough that their cost, spread across all operations, is constant per operation.
The Landscape of Hardness
NP-completeness is not a catalog item but a diagnostic. When a new combinatorial optimization problem resists — when every algorithm you try is too slow, when reducing to a simpler problem fails — the right first question is whether the problem is NP-complete. If it is, the search for a polynomial-time exact solution should be abandoned in favor of alternatives: approximation algorithms that find near-optimal solutions with provable guarantees, parameterized algorithms that are efficient when a structural parameter of the input is small, heuristics with good empirical behavior, or exact algorithms for the special cases that actually arise in practice.
Karp’s 1972 paper established twenty-one classic NP-complete problems — satisfiability, vertex cover, independent set, graph coloring, Hamiltonian cycle, traveling salesman, and others — that serve as reduction targets. Recognizing that a new problem resembles one of these, and constructing the polynomial-time reduction that proves equivalence, is itself an algorithm design skill. The ability to identify intractability early changes what gets built.
Beyond NP-completeness, complexity theory provides a richer landscape: problems that are hard even to approximate (inapproximability results), problems with fine-grained complexity (exact hardness of specific polynomial-time algorithms), problems that are hard for classical but not quantum computers, and the hierarchy of complexity classes above NP. This landscape is the territory of Chapter 3.
The Design Vocabulary
The major algorithm design paradigms are not tricks but recurring structural patterns. Learning to recognize which pattern a problem admits — and when none of the standard patterns fit — is the hard part of algorithm design.
Divide and conquer splits a problem into smaller instances of the same problem, solves them recursively, and combines the results efficiently. Mergesort divides the array in half, sorts each half, and merges in O(n): the combination is efficient, and the total work is O(n log n). The fast Fourier transform applies the same structure to polynomial evaluation at roots of unity: a degree-n polynomial can be evaluated at all n-th roots simultaneously in O(n log n) by computing at n/2 roots and combining, rather than the naive O(n²) of evaluating separately at each root. The FFT is one of the most consequential algorithms in applied mathematics, making digital signal processing computationally tractable.
Dynamic programming identifies overlapping subproblems — where the same subproblem is needed to solve many larger instances — and solves each once, storing results to avoid redundant computation. The classic instances include shortest paths (Bellman-Ford, Floyd-Warshall), sequence alignment in bioinformatics, and the knapsack problem. The intellectual challenge is identifying the right subproblem: the one whose solution, plus optimal decisions for the remaining choices, gives an optimal overall solution. This property — optimal substructure — must be verified, not assumed. Without it, DP does not apply.
Greedy algorithms make locally optimal choices at each step without reconsidering previous choices. Huffman coding for data compression is greedy: repeatedly merge the two lowest-frequency symbols. Prim’s and Kruskal’s algorithms for minimum spanning trees are greedy. Greedy algorithms are faster and simpler than dynamic programming when they apply, but they require a proof of global optimality — that locally optimal choices lead to a globally optimal solution. Many problems that look greedy are not; the exchange argument, which shows that any deviation from the greedy choice can only worsen the result, is the standard proof technique.
Graph algorithms address the most frequently reused collection of problems in CS. Breadth-first search finds shortest paths in unweighted graphs and identifies connected components. Dijkstra’s algorithm finds shortest paths in weighted graphs with non-negative weights, using a priority queue to repeatedly extract and relax the closest unvisited vertex. Bellman-Ford handles negative weights and detects negative cycles. Maximum flow, minimum cut, and bipartite matching are among the most broadly applicable results: they solve scheduling, assignment, and network design problems that appear across systems and operations research. Topological sort on directed acyclic graphs enables dependency resolution — the foundation of build systems, package managers, and course prerequisite planning.
Data structures determine which algorithms are feasible. Hash tables provide expected O(1) lookup, insertion, and deletion, making them the most broadly used data structure in practice; database indexes, compiler symbol tables, caches, and deduplication all rest on hashing. Balanced binary search trees (AVL trees, red-black trees, B-trees) provide O(log n) operations with sorted-order guarantees; B-trees are the standard for database indexes because their high branching factor minimizes the tree’s height and thus the number of disk accesses per operation. Heaps provide O(log n) extraction of the minimum or maximum element, enabling priority queues and the efficient implementation of Dijkstra’s algorithm. Union-find supports O(α(n)) amortized union and find operations — effectively constant — and is essential for Kruskal’s minimum spanning tree and for network connectivity queries.
What Studying This Changes
Algorithms and data structures changes a practitioner’s competence in ways that are not visible until a problem demands them.
The most durable change is asymptotic intuition: the immediate, habitual assessment of cost. A nested loop is O(n²); adding a hash table lookup changes a linear scan to O(1); sorting before binary searching changes the complexity class of repeated lookups. This intuition is not acquired from reading but from practice — from deriving complexity bounds, having estimates confirmed or corrected by measurement, and developing the sense of what growth class a structure implies. It becomes automatic, and when it becomes automatic, it operates before code is written rather than after it is profiled.
The second change is reduction recognition: the ability to see that a new problem is a known one. A scheduling problem reduces to maximum flow; a resource allocation problem reduces to bipartite matching; a dependency problem is a DAG traversal. Recognizing the reduction means applying decades of known results rather than designing from scratch. This recognition is built through broad exposure to canonical algorithms, which is why the subject cannot be adequately learned from a narrow problem set.
The third change is knowing when to stop looking for the optimal. A practitioner who recognizes NP-completeness early stops an unproductive search and starts a productive one — for approximations, for heuristics, for efficient special cases. Without this recognition, the temptation is to interpret failure as personal inadequacy rather than structural impossibility.
Resources
Books and Texts
The standard comprehensive reference is Cormen, Leiserson, Rivest, and Stein’s Introduction to Algorithms (CLRS, 4th ed., 2022). It covers sorting, searching, graph algorithms, dynamic programming, greedy methods, amortized analysis, NP-completeness, and approximation algorithms with complete proofs and careful analysis. Dense and brisk, it is better treated as a reference one grows into than a book read cover to cover; the proofs are complete, the definitions precise, and coverage is comprehensive enough that most practitioners keep it on the shelf throughout their careers.
Sedgewick and Wayne’s Algorithms (4th ed.) takes the opposite approach: implementation-first, visual, and empirical, with actual running-time measurements alongside asymptotic bounds. Where CLRS develops analysis and then shows code, Sedgewick shows working code and builds intuition from observing its behavior. A common path is Sedgewick for initial fluency, CLRS for depth thereafter.
Skiena’s The Algorithm Design Manual (3rd ed.) solves a problem neither of the above addresses: what to do when you face a problem you have not seen before. Its first half teaches design technique through real consulting problems — the messy process of matching a problem to a method, shown honestly. Its second half is a catalog of problems with advice on which algorithms apply. It is the book most directly about how to think, not just what to know, and the one that most directly builds problem-recognition skill.
Kleinberg and Tardos’s Algorithm Design is the standard second course text, stronger than CLRS on why design techniques work and with a particularly thorough treatment of network flow and its applications. Dasgupta, Papadimitriou, and Vazirani’s Algorithms (free online) covers the core in roughly 300 pages with unusual conceptual compression — a valuable re-read once the foundations are in place.
For randomized algorithms — which underlie hash tables, quicksort’s practical performance, primality testing, and most of streaming and approximation — Motwani and Raghavan’s Randomized Algorithms is canonical. For NP-hard problems, Williamson and Shmoys’s The Design of Approximation Algorithms (free online) covers what to do when no exact efficient solution exists.
Two books belong on the reference shelf. Knuth’s The Art of Computer Programming is the encyclopedic authority — too comprehensive to read sequentially, indispensable for the definitive treatment of specific topics. Graham, Knuth, and Patashnik’s Concrete Mathematics develops the recurrence-solving and asymptotic machinery that algorithm analysis assumes but most textbooks do not teach.
| Book | Role | Type |
|---|---|---|
| Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (4th ed.) | Comprehensive standard; rigorous depth | Reference |
| Sedgewick & Wayne, Algorithms (4th ed.) | Implementation-first, empirical, accessible | Practice |
| Skiena, The Algorithm Design Manual (3rd ed.) | Design thinking and problem recognition | Entry |
| Kleinberg & Tardos, Algorithm Design | Second course; reasoning behind techniques | Depth |
| Dasgupta, Papadimitriou & Vazirani, Algorithms (free) | Compact conceptual re-read | Depth |
| Motwani & Raghavan, Randomized Algorithms | Randomized methods | Depth |
| Williamson & Shmoys, The Design of Approximation Algorithms (free) | Approximation for NP-hard problems | Depth |
| Knuth, The Art of Computer Programming | Encyclopedic authority | Reference |
| Graham, Knuth & Patashnik, Concrete Mathematics | Mathematical machinery for analysis | Reference |
Courses and Lectures
Sedgewick and Wayne’s Algorithms Parts I and II on Coursera (free to audit) are the most refined free courses for the subject. Taught by the textbook authors, the courses cover data structures and sorting (Part I) and graph algorithms and string processing (Part II) with live algorithm visualizations. The pedagogical approach matches the book: implementation-driven, with direct observation of algorithm behavior alongside analysis.
MIT 6.006 (Introduction to Algorithms, free on MIT OCW) and 6.046 (Design and Analysis of Algorithms) form the standard academic sequence. 6.006 covers foundations — sorting, hashing, graph search, shortest paths, dynamic programming — with full lecture videos, problem sets, and exams freely available. 6.046 extends into advanced design techniques, amortized analysis, and NP-completeness.
Tim Roughgarden’s Algorithms Specialization on Coursera (free to audit) covers divide and conquer, graph algorithms, greedy methods, dynamic programming, and NP-completeness across four courses. Roughgarden narrates the reasoning behind each technique with unusual clarity; the companion Algorithms Illuminated volumes extend the lectures into a standalone text.
UC Berkeley CS 61B (Data Structures, free lectures on YouTube) covers data structures and introductory algorithm analysis with strong implementation depth using Java. It complements the more analysis-heavy MIT courses by emphasizing what it actually takes to build correct and efficient data structure implementations.
Khan Academy Algorithms (free) is a beginner-friendly visual and interactive path through basic algorithmic ideas. It is shallow compared with Sedgewick, MIT, or Roughgarden, but it can make the first encounter with asymptotic notation, sorting, graph search, and recursion less forbidding.
Brilliant’s CS path (paid subscription) is a polished interactive option for learners who benefit from short visual puzzles and immediate feedback. It should be treated as an auxiliary intuition-builder, not as a rigorous algorithms or data structures course, but its format gives readers a useful alternative to long lectures and textbooks.
| Course | Platform | Type |
|---|---|---|
| Sedgewick & Wayne, Algorithms Parts I & II (free to audit) | Coursera | Entry |
| MIT 6.006 + 6.046 (free) | MIT OCW | Entry |
| Tim Roughgarden, Algorithms Specialization (free to audit) | Coursera | Entry |
| UC Berkeley CS 61B (free) | YouTube / course site | Practice |
| Khan Academy Algorithms (free) | Khan Academy | Auxiliary |
| Brilliant CS path (paid subscription) | brilliant.org | Auxiliary |
Practice, Tools, and Code
Visualgo (visualgo.net) provides interactive step-by-step visualizations of sorting algorithms, graph traversals, dynamic programming, and data structures. Watching an algorithm execute on a chosen input — with each comparison and pointer update highlighted — builds intuitions that pseudocode and static diagrams cannot.
OpenDSA is a free interactive system for data structures and algorithms, combining text, visualizations, and exercises. It overlaps with Visualgo in subject matter, but its integration with practice problems makes it a different learning mode rather than a duplicate.
Algorithm Visualizer is a code-driven interactive platform that visualizes algorithms from executable examples. It is useful when learners want to connect implementation details to motion on screen, especially for sorting, graph, and data-structure procedures.
William Fiset’s algorithm series on YouTube covers graph algorithms with high-quality animations and clean walkthroughs. His treatments of BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, maximum flow, and strongly connected components are among the clearest video explanations of these topics available, particularly for the graph algorithms that introductory courses often handle poorly.
Abdul Bari’s algorithm lectures on YouTube are strong on dynamic programming and greedy algorithms — developing the intuition behind each problem before presenting the algorithm, which is the right pedagogical order. The DP series in particular is worth watching for learners who find the standard textbook presentation opaque.
The Algorithms project on GitHub provides multi-language implementations of mainstream algorithms. It is valuable because readers can compare the same algorithm across languages and see implementation idioms side by side. Quality and explanation vary by contribution, so it should be used with a course or text rather than as an authority by itself.
Runestone’s Problem Solving with Algorithms and Data Structures is a free interactive textbook available in Python and related versions. It is useful for learners who want a code-first, exercise-rich path through data structures before or alongside a more analytical course.
cp-algorithms is a compact contest-oriented reference for algorithmic techniques, data structures, graph algorithms, string algorithms, and number theory. It is not a first course, but it is excellent after the fundamentals are in place, especially when the learner needs implementation-level details quickly.
Project Euler turns mathematical programming into a sequence of increasingly difficult problems. It does not teach data structures systematically, but it develops the habit of combining number theory, combinatorics, search, dynamic programming, and careful implementation under constraints.
| Resource | Platform | Type |
|---|---|---|
| Visualgo (free) | visualgo.net | Practice |
| OpenDSA (free) | opendsa.org | Practice |
| Algorithm Visualizer (free) | algorithm-visualizer.org / GitHub | Practice |
| William Fiset, graph algorithm series (free) | YouTube | Auxiliary |
| Abdul Bari, algorithm lectures (free) | YouTube | Auxiliary |
| The Algorithms (free) | GitHub / the-algorithms.com | Practice |
| Runestone, Problem Solving with Algorithms and Data Structures (free) | Runestone Academy | Practice |
| cp-algorithms (free) | cp-algorithms.com | Reference |
| Project Euler (free) | projecteuler.net | Auxiliary |
Traps
| Trap | Why it misleads | Better response |
|---|---|---|
| Studying for interviews instead of for understanding | Interview preparation trains pattern-matching on a fixed catalogue under time pressure. This builds recall of specific solutions without the ability to analyze cost, prove correctness, or design something new — it collapses the moment a problem departs from the catalogue. | Keep the two activities separate. Study by proving correctness and deriving complexity from first principles; prepare for interviews on top of that foundation. Understanding makes interview preparation easy; the reverse is not true. |
| Implementing without analyzing | Getting an algorithm to run feels like understanding it. The substance is in the analysis: if you cannot prove it correct, derive its growth rate from the recurrence, and explain why the analysis comes out as it does, you have surface familiarity that does not transfer to novel problems. | For each algorithm: implement it, prove it correct, derive the complexity from first principles without looking. The derivation is the learning; the running code is evidence of it. |
| Hitting dynamic programming and concluding failure | Dynamic programming defeats more learners than any other topic, and the failure is almost always misread as personal. The difficulty — identifying the right subproblem, formulating the recurrence, ordering the computation — is intrinsic to the technique, not a sign of deficiency. Textbooks systematically underallocate time to it. | Budget two to three times the time the textbook implies. The skill is recognizing subproblem structure, which develops only through problem volume, not through reading explanations of solutions. Work problems until the structure becomes visible before it is named. |
| Reading “asymptotically optimal” as “fastest” | Asymptotic analysis answers whether an algorithm scales; it does not say whether it is fast on a given input on a given machine. An asymptotically inferior algorithm with better cache behavior can be several times faster in practice, and the theory is not wrong — it answered a different question. | Hold both questions explicitly: which scales better (theory answers this) and which is faster here (measurement answers this). When they diverge, the usual cause is the memory hierarchy; profile before concluding the analysis is misleading. |
| Treating NP-completeness as a theoretical footnote | Learners often memorize the definition without learning to recognize it in a live problem, then spend weeks searching for an efficient exact algorithm to something that almost certainly has none. | When an optimization problem resists, check before continuing whether it resembles a known NP-complete problem — Karp’s twenty-one are the canonical reference. Recognizing intractability early is what allows a productive pivot to approximation or heuristics. |
| Skipping randomized algorithms as a specialization | Randomized algorithms underlie everyday tools: hash tables, quicksort’s practical performance, the primality tests in most cryptographic libraries, locality-sensitive hashing, reservoir sampling. Treating them as advanced elective material leaves the foundations of common infrastructure unexplained. | Study randomized algorithms alongside the deterministic core. The key ideas — expected-case analysis, Las Vegas versus Monte Carlo guarantees — are not difficult and clarify a great deal that otherwise looks arbitrary. |
中文
对程序员来说，算法是一种解决计算问题的方法，而且这种方法可以在运行之前被分析：给定输入的描述，你可以推理它是否会产生正确输出，它需要多长时间，以及它会使用多少内存。这正是算法与“碰巧能工作”的程序之间的区别。一个只被测试过的程序，只能给你关于特定输入的证据；一个被分析过的算法，则能给你关于所有相关输入的保证。这个区别很重要，因为大规模部署的软件会遇到测试从未预料到的输入。
数据结构是一种组织数据的方式，目的是让作用于这些数据的特定操作变得高效。这不是审美选择。一个无序列表要查找元素，只能从头扫描——无论输入如何，都是 O(n) 时间。哈希表可以在期望常数时间内找到它。平衡二叉搜索树可以在 O(log n) 时间内找到它，并额外保持元素有序。算法与它所操作的数据结构并不是彼此独立的选择：它们共同决定彼此的成本，而这门学科的核心能力，就是为手头问题匹配正确的组合。
算法与数据结构研究的是计算过程的设计、分析和正确性。它位于整个领域的底层附近——离散数学（§2.2）和写出并运行代码的能力（§2.1）是直接前置知识，概率论（§2.5）是随机方法所需的前置知识——而几乎所有后续主题都会依赖它：数据库、编译器、图形学、机器学习、分布式系统，在某种程度上都是算法设计的应用。
对过程的研究如何成为一门数学学科
在人类有文字记录的大部分历史中，算法是一种配方，而它是否正确，通常靠尝试来判断。Euclid 在约公元前 300 年描述了一种求最大公约数的过程，并且很不寻常地论证了它总会终止并给出正确答案。“algorithm” 这个词本身来自 al-Khwārizmī 之名的拉丁化形式；这位九世纪数学家的教材把使用印度—阿拉伯数字进行计算的方法传入欧洲。但在两千年里，人们几乎没有问过一个过程运行得有多快。原因也解释了为什么这门学科很年轻：在机器能够自动执行过程之前，最慢的步骤始终是执行这些过程的人；计数一个过程的抽象步骤并没有太大意义。
这门学科成为科学，始于 Donald Knuth 在 1968 年开始出版 The Art of Computer Programming。Knuth 的贡献是一种重新框定：算法的成本可以被数学化研究，并且可以独立于任何特定机器来研究；关键问题是，当输入增长时，它的步骤数量如何增长。一个算法并不是简单地“快”或“慢”——它有一个增长率，这是算法本身的性质，可以在运行前被认识和证明。这带来了渐近记号，用来压掉无关常数，暴露定性行为（big-O）；也带来了一种方法，即把操作次数表示为输入规模的函数；还带来了一种继承自数学的标准：证明一个算法对所有输入都正确，而不只是证明它在测试过的输入上产生了正确输出。这里划出的界线——一个算法只是被观察到能工作，还是被证明能工作——正是作为手艺的编程与作为科学的算法之间的界线。
随着分析被确立为方法，这个领域开始积累结果，而其中最有后果的结果之一，是关于什么不可能的发现。整个 1960 年代，计算机科学家已经收集了一批抗拒高效求解的问题——在一组城市中寻找最短巡回路线，在约束下安排任务，满足一组逻辑条件。每个问题都曾被单独攻击，每个问题都顽强抵抗，因此当时的工作假设是：每个问题都只是在等待自己的巧妙洞见。1971 年，Stephen Cook 证明这个假设是错误的；几乎同时，Leonid Levin 在苏联独立得出了类似结果。Cook 证明，一个问题——布尔可满足性问题，也就是问一个逻辑公式能否通过某种变量赋值而为真——具有一种惊人性质：一个庞大而自然的问题类别中的每个问题，都可以在多项式时间内被机械地重写为它的一个实例。第二年，Richard Karp 对另外 21 个问题证明了同样的事情。这些问题并不是各自独立地困难；它们是同一种困难的不同伪装。只要你能高效解决其中任何一个，就能高效解决它们全部。这就是 P vs. NP 问题的源头，而它现在是计算机科学中最著名的开放问题。几乎所有人都相信答案意味着这些问题不存在高效的精确解，但半个世纪以来仍没有证明定论。这个发现改变的是整个领域的姿态：证明不存在好算法，与给出一个算法同样有价值；而识别 NP-completeness，是面对某一类失败时的生产性回应——这不是个人能力不足，而是问题本身的结构性事实。
第三个发展更安静，只有当理论遇到真实机器时才会浮现。Knuth 的分析假设一个模型：每个基本操作成本相同，每个内存位置的访问速度相同——这就是 RAM 模型，对 1970 年代的硬件来说是一个合理近似。大量算法分析至今仍在这个模型中进行。但这个模型已经逐渐偏离现实。现代处理器把内存看成一个层级：少量值可以在一个周期内访问，缓存需要几个周期，主内存则可能需要数百个周期。一个算法即使执行更少操作，如果这些操作分散在相距很远的内存中，也可能比另一个执行更多操作、但让数据保持局部性的算法慢好几倍。在 RAM 模型中，二分搜索是最优的；但在大数据上，B-tree 虽然执行更多比较，却把相关键存储在连续块中，因此经常优于二分搜索，因为它是为模型所忽略的内存层级而设计的。这里的教训不是理论错了。渐近分析正确回答的是一个算法是否可扩展；它并不回答某个算法在某台具体机器、某个具体输入上是否快。这两个问题之间的距离，就是算法工程运作的地方：缓存感知数据结构、经验 profiling，以及顺着真实硬件的纹理来设计。
这三场运动——严谨分析的建立、难解性具有可证明结构的发现，以及理想化成本模型与真实机器之间的对账——使这门学科在核心处异常稳定。主要算法、数据结构和证明技术几十年来变化很小；今天学生学习排序、最短路径和动态规划的内容，与 1990 年学生学习的内容几乎相同。这种稳定性在计算机科学中很罕见，也是在静默地说明：这门学科值得认真掌握，因为这项投入不会过期。活跃前沿属于第三场运动。2005 年前后处理器时钟频率进入平台期，迫使人们严肃关注并行与分布式算法，而许多经典顺序结果并没有高效对应物。不断加深的内存层级让算法工程越来越重要。还有一些仍未定论的活跃工作，研究 learned data structures——即利用 ML 适应数据的索引和数据结构——能否在某些领域取代手工设计的数据结构。所有这些方向都建立在经典核心之上，而不是取代经典核心。
正确性、成本与可能性的边界
这门学科围绕三个反复出现的问题组织自身，并围绕连接这些问题的设计词汇展开。
证明正确性与刻画成本
正确性不是测试得好不好。正确性证明要建立的是：一个算法对每个有效输入都会产生正确输出——覆盖那些任何测试套件都无法到达的无限情形。标准工具包括数学归纳法（用于自然有序输入上的算法）、循环不变量（用于迭代过程——在每次迭代前后都保持的性质，并在循环终止时推出正确性）、结构归纳法（用于递归算法——先证明基例，再证明如果对子问题成立，那么对递归情形也成立）。每种技术都是一种用有限论证覆盖无限领域的方式。
成本分析始于渐近记号。如果一个算法在规模为 n 的输入上执行 f(n) 次操作，而 f 的增长速度不超过 g，那么它就是 O(g(n))：存在常数 c 和 n₀，使得对所有 n ≥ n₀，都有 f(n) ≤ c·g(n)。常数被压掉，是为了暴露增长率；而增长率决定规模变大时的定性行为。复杂度类别之间的差距极大。一个 O(n²) 算法在一百万个输入上执行一万亿次操作——即使每秒 10⁹ 次操作，也要超过十五分钟。一个 O(n log n) 算法在同样输入上大约执行两千万次操作——约二十毫秒。任何硬件选择都无法弥合这种量级差距；只有算法选择可以。
递推关系用较小实例的成本来表达递归算法的成本。Mergesort 把输入一分为二，对两半递归排序，并在线性时间内合并：T(n) = 2T(n/2) + O(n)。主定理把这个递推式解为 T(n) = O(n log n)。建立并求解递推关系，是递归算法的核心分析能力；这项技术直接连接到 §2.2 的离散数学，也会在随机算法中连接到 §2.5 的概率论。
摊还分析处理那些操作偶尔会比平时昂贵的数据结构。向动态数组追加元素，大多数时候是 O(1)，但当数组必须扩容时是 O(n)。对数据结构来说，正确度量不应该是任何单次操作的最坏成本，而是一个现实操作序列上的平均成本：摊还分析表明，动态数组的 append 是摊还 O(1)，因为昂贵的扩容操作足够少，它们的成本摊到所有操作上后，每次操作成本仍是常数。
困难性的景观
NP-completeness 不是目录项，而是诊断工具。当一个新的组合优化问题顽固抵抗时——你尝试的每个算法都太慢，把它归约成更简单问题也失败——第一个正确问题应该是：这个问题是不是 NP-complete？如果是，就应当放弃寻找多项式时间精确解，转向替代方案：能以可证明保证找到近似最优解的近似算法；在输入的某个结构参数较小时高效的参数化算法；具有良好经验表现的启发式算法；或者只针对实践中实际出现的特殊情形设计的精确算法。
Karp 1972 年的论文确立了 21 个经典 NP-complete 问题——可满足性、顶点覆盖、独立集、图着色、Hamiltonian cycle、旅行商问题等——它们可以作为归约目标。识别一个新问题类似于其中某个问题，并构造能证明等价性的多项式时间归约，本身就是一种算法设计能力。越早识别难解性，就越会改变实际会被构建的东西。
在 NP-completeness 之外，复杂性理论提供了更丰富的景观：甚至难以近似的问题（不可近似性结果）、具有细粒度复杂性的问题（关于特定多项式时间算法的精确困难性）、对经典计算机困难但对量子计算机不困难的问题，以及 NP 之上的复杂性类层级。这个景观属于第三章的内容。
设计词汇
主要算法设计范式不是技巧，而是反复出现的结构模式。学会识别一个问题允许哪种模式——以及何时没有任何标准模式适用——是算法设计中的难点。
分治法把一个问题分成同类的更小实例，递归解决它们，再高效合并结果。Mergesort 把数组分半，分别排序两半，并用 O(n) 时间合并：合并过程高效，总工作量是 O(n log n)。快速傅里叶变换把同样结构应用于在单位根上进行多项式求值：一个 n 次多项式可以通过先在 n/2 个根上计算、再合并，在 O(n log n) 时间内同时得到所有 n 次单位根处的值，而不是用朴素方法对每个根分别求值，耗费 O(n²)。FFT 是应用数学中最有后果的算法之一，它使数字信号处理在计算上变得可行。
动态规划识别重叠子问题——同一个子问题会被用于解决许多更大实例——并且每个子问题只求解一次，保存结果以避免冗余计算。经典例子包括最短路径（Bellman-Ford、Floyd-Warshall）、生物信息学中的序列比对，以及背包问题。智力挑战在于识别正确的子问题：这个子问题的解，加上剩余选择中的最优决策，可以给出整体最优解。这种性质——最优子结构——必须被验证，而不能被假定。没有它，DP 就不适用。
贪心算法在每一步做局部最优选择，并且不重新考虑之前的选择。用于数据压缩的 Huffman coding 是贪心的：反复合并频率最低的两个符号。Prim 和 Kruskal 的最小生成树算法也是贪心的。贪心算法在适用时比动态规划更快、更简单，但它需要全局最优性证明——证明局部最优选择会导致全局最优解。许多看起来适合贪心的问题其实并不适合；交换论证是标准证明技术，它说明任何偏离贪心选择的方案都只会让结果变差。
图算法处理的是 CS 中最频繁复用的问题集合。广度优先搜索可以在无权图中寻找最短路径，并识别连通分量。Dijkstra 算法在具有非负权重的加权图中寻找最短路径，它使用优先队列反复取出并松弛最近的未访问顶点。Bellman-Ford 可以处理负权重，并检测负环。最大流、最小割和二分图匹配是适用范围最广的结果之一：它们可以解决调度、分配和网络设计问题，而这些问题会出现在系统和运筹学的各个场景中。有向无环图上的拓扑排序支持依赖解析——这是构建系统、包管理器和课程先修规划的基础。
数据结构决定哪些算法是可行的。哈希表提供期望 O(1) 的查找、插入和删除，因此是实践中使用最广的数据结构；数据库索引、编译器符号表、缓存和去重，都建立在哈希之上。平衡二叉搜索树（AVL 树、红黑树、B-tree）提供 O(log n) 操作，并保证有序性；B-tree 是数据库索引标准，因为它的高分支因子最小化了树高，从而最小化每次操作所需的磁盘访问次数。堆提供 O(log n) 的最小或最大元素提取，从而支持优先队列和 Dijkstra 算法的高效实现。Union-find 支持摊还 O(α(n)) 的 union 和 find 操作——事实上几乎是常数——并且对 Kruskal 最小生成树和网络连通性查询至关重要。
学习这一部分会改变什么
算法与数据结构会以一些在问题真正要求它们之前并不明显的方式，改变实践者的能力。
最持久的变化是渐近直觉：对成本的即时、习惯性判断。嵌套循环是 O(n²)；加入哈希表查找会把线性扫描变为 O(1)；先排序再二分查找，会改变重复查找的复杂度类别。这种直觉不是靠阅读获得的，而是靠实践获得的——通过推导复杂度界限，通过测量确认或修正估计，并逐渐形成某种结构意味着哪种增长类别的感觉。它会变成自动反应；而一旦变成自动反应，它会在写代码之前，而不是在 profile 之后就开始发挥作用。
第二个变化是归约识别能力：看出一个新问题其实是一个已知问题。一个调度问题可以归约为最大流；一个资源分配问题可以归约为二分图匹配；一个依赖问题是 DAG 遍历。识别出归约，意味着使用几十年来的已知结果，而不是从零设计。这种识别能力来自对经典算法的广泛接触，这也是为什么这门学科无法通过狭窄题集充分学会。
第三个变化，是知道什么时候应该停止寻找最优解。一个能早早识别 NP-completeness 的实践者，会停止无效搜索，转向有效搜索——寻找近似、启发式方法或高效特殊情形。如果没有这种识别，人很容易把失败理解成个人能力不足，而不是结构性不可能。
资源
书籍与文本
标准综合参考是 Cormen、Leiserson、Rivest 和 Stein 的 Introduction to Algorithms（CLRS，第 4 版，2022）。它覆盖排序、搜索、图算法、动态规划、贪心方法、摊还分析、NP-completeness 和近似算法，并提供完整证明和谨慎分析。它密集且推进很快，更适合作为一本逐渐用得上的参考书，而不是从头读到尾的书；它的证明完整，定义精确，覆盖面足够全面，因此多数实践者会在整个职业生涯中把它放在书架上。
Sedgewick 和 Wayne 的 Algorithms（第 4 版）采取相反方式：实现优先、视觉化、经验化，并且把实际运行时间测量与渐近界限并列呈现。CLRS 先发展分析再展示代码，而 Sedgewick 先展示可运行代码，并从观察其行为中建立直觉。一条常见路径是先用 Sedgewick 获得初步流利度，再用 CLRS 深入。
Skiena 的 The Algorithm Design Manual（第 3 版）解决了前两本书都没有处理的问题：当你面对一个从没见过的问题时，该怎么办。它的前半部分通过真实咨询问题教授设计技术——诚实展示把一个问题匹配到一种方法的混乱过程。后半部分是问题目录，并附有关于哪些算法适用的建议。它最直接地讨论“如何思考”，而不只是“知道什么”，也是最直接培养问题识别能力的一本书。
Kleinberg 和 Tardos 的 Algorithm Design 是标准第二门课程教材，它比 CLRS 更强地解释设计技术为什么有效，并且对网络流及其应用处理得特别充分。Dasgupta、Papadimitriou 和 Vazirani 的 Algorithms（免费在线）用约 300 页覆盖核心内容，概念压缩得很不寻常——一旦基础已经到位，它是很有价值的重读材料。
对于随机算法——它们支撑哈希表、quicksort 的实践表现、素性测试，以及大多数流式算法和近似算法——Motwani 和 Raghavan 的 Randomized Algorithms 是经典教材。对于 NP-hard 问题，Williamson 和 Shmoys 的 The Design of Approximation Algorithms（免费在线）覆盖了当不存在高效精确解时应该做什么。
有两本书应放在参考书架上。Knuth 的 The Art of Computer Programming 是百科全书式权威——过于全面，不适合顺序阅读，但当需要某个具体主题的权威处理时不可替代。Graham、Knuth 和 Patashnik 的 Concrete Mathematics 发展了算法分析默认需要、但多数教材并不系统教授的递推求解和渐近分析工具。
| 书籍 | 作用 | 类型 |
|---|---|---|
| Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms（第 4 版） | 综合标准；严谨深度 | 参考 |
| Sedgewick & Wayne, Algorithms（第 4 版） | 实现优先、经验化、可进入 | 实践 |
| Skiena, The Algorithm Design Manual（第 3 版） | 设计思维与问题识别 | 入门 |
| Kleinberg & Tardos, Algorithm Design | 第二门课程；技术背后的推理 | 深入 |
| Dasgupta, Papadimitriou & Vazirani, Algorithms（免费） | 紧凑的概念重读 | 深入 |
| Motwani & Raghavan, Randomized Algorithms | 随机方法 | 深入 |
| Williamson & Shmoys, The Design of Approximation Algorithms（免费） | 面向 NP-hard 问题的近似算法 | 深入 |
| Knuth, The Art of Computer Programming | 百科全书式权威 | 参考 |
| Graham, Knuth & Patashnik, Concrete Mathematics | 分析所需的数学工具 | 参考 |
课程与讲座
Sedgewick 和 Wayne 在 Coursera 上的 Algorithms Parts I and II（可免费旁听）是这门学科最精炼的免费课程之一。课程由教材作者讲授，Part I 覆盖数据结构和排序，Part II 覆盖图算法和字符串处理，并带有实时算法可视化。其教学方式与教材一致：以实现为驱动，把对算法行为的直接观察与分析并列。
MIT 6.006（Introduction to Algorithms，MIT OCW 免费）和 6.046（Design and Analysis of Algorithms）构成标准学术序列。6.006 覆盖基础——排序、哈希、图搜索、最短路径、动态规划——并免费提供完整讲座视频、习题和考试。6.046 延伸到高级设计技术、摊还分析和 NP-completeness。
Tim Roughgarden 的 Algorithms Specialization（Coursera，可免费旁听）通过四门课程覆盖分治、图算法、贪心方法、动态规划和 NP-completeness。Roughgarden 以异常清楚的方式讲述每种技术背后的推理；配套的 Algorithms Illuminated 系列书则把讲座扩展成独立文本。
UC Berkeley CS 61B（Data Structures，YouTube 免费讲座）使用 Java 覆盖数据结构和入门算法分析，并且具有很强的实现深度。它通过强调构建正确且高效的数据结构实现，补充了更偏分析的 MIT 课程。
Khan Academy Algorithms（免费）是一条对初学者友好的视觉化、交互式路径，覆盖基本算法思想。它比 Sedgewick、MIT 或 Roughgarden 浅，但可以让第一次接触渐近记号、排序、图搜索和递归时没那么艰难。
Brilliant 的 CS path（付费订阅）是一个精致的交互式选项，适合从短小视觉谜题和即时反馈中受益的学习者。它应被视为辅助直觉构建工具，而不是严谨的算法或数据结构课程；但它的形式为读者提供了区别于长讲座和教材的有用替代。
| 课程 | 平台 | 类型 |
|---|---|---|
| Sedgewick & Wayne, Algorithms Parts I & II（可免费旁听） | Coursera | 入门 |
| MIT 6.006 + 6.046（免费） | MIT OCW | 入门 |
| Tim Roughgarden, Algorithms Specialization（可免费旁听） | Coursera | 入门 |
| UC Berkeley CS 61B（免费） | YouTube / 课程网站 | 实践 |
| Khan Academy Algorithms（免费） | Khan Academy | 辅助 |
| Brilliant CS path（付费订阅） | brilliant.org | 辅助 |
实践、工具与代码
Visualgo（visualgo.net）提供排序算法、图遍历、动态规划和数据结构的交互式逐步可视化。看一个算法在自选输入上执行——每一次比较和指针更新都被高亮——能建立伪代码和静态图无法带来的直觉。
OpenDSA 是一个免费的交互式数据结构与算法系统，结合文本、可视化和练习。它与 Visualgo 在主题上有重叠，但它与练习题结合，因此是另一种学习模式，而不是重复品。
Algorithm Visualizer 是一个代码驱动的交互式平台，可以从可执行示例中可视化算法。当学习者想把实现细节与屏幕上的运动连接起来时，它很有用，尤其适合排序、图和数据结构过程。
William Fiset 的算法系列（YouTube）用高质量动画和清晰推导讲解图算法。他对 BFS、DFS、Dijkstra、Bellman-Ford、Floyd-Warshall、最大流和强连通分量的处理，是这些主题目前最清晰的视频解释之一，尤其适合那些入门课程常常讲得不够好的图算法。
Abdul Bari 的算法讲座（YouTube）在动态规划和贪心算法上很强——他会先发展每个问题背后的直觉，再给出算法，而这正是正确的教学顺序。对于觉得标准教材中的 DP 展示不透明的学习者，他的 DP 系列尤其值得看。
The Algorithms GitHub 项目提供主流算法的多语言实现。它的价值在于，读者可以比较同一个算法在不同语言中的实现，并并列看到实现习惯。质量和解释会随贡献者而变化，因此它应与课程或教材一起使用，而不能单独作为权威。
Runestone 的 Problem Solving with Algorithms and Data Structures 是一本免费的交互式教材，有 Python 版本和相关版本。它适合那些想要代码优先、练习丰富的数据结构路径的学习者，可以在更偏分析的课程之前或同时使用。
cp-algorithms 是一个紧凑的竞赛导向参考，覆盖算法技术、数据结构、图算法、字符串算法和数论。它不是第一门课程，但在基础到位之后非常优秀，尤其适合学习者需要快速获得实现层细节时使用。
Project Euler 把数学编程变成一系列难度递增的问题。它不系统教授数据结构，但会培养在约束下组合使用数论、组合数学、搜索、动态规划和谨慎实现的习惯。
| 资源 | 平台 | 类型 |
|---|---|---|
| Visualgo（免费） | visualgo.net | 实践 |
| OpenDSA（免费） | opendsa.org | 实践 |
| Algorithm Visualizer（免费） | algorithm-visualizer.org / GitHub | 实践 |
| William Fiset, graph algorithm series（免费） | YouTube | 辅助 |
| Abdul Bari, algorithm lectures（免费） | YouTube | 辅助 |
| The Algorithms（免费） | GitHub / the-algorithms.com | 实践 |
| Runestone, Problem Solving with Algorithms and Data Structures（免费） | Runestone Academy | 实践 |
| cp-algorithms（免费） | cp-algorithms.com | 参考 |
| Project Euler（免费） | projecteuler.net | 辅助 |
陷阱
| 陷阱 | 为什么会误导 | 更好的回应 |
|---|---|---|
| 为面试而学，而不是为理解而学 | 面试准备会训练人在固定题库和时间压力下做模式匹配。这会建立对特定解法的回忆，但不会建立分析成本、证明正确性或设计新东西的能力——一旦问题偏离题库，它就会崩塌。 | 把这两种活动分开。学习时，从第一原则出发证明正确性并推导复杂度；面试准备应叠加在这个基础之上。理解会让面试准备变容易；反过来不成立。 |
| 实现了，却没有分析 | 让一个算法跑起来，会让人感觉自己理解了它。但实质在分析中：如果你不能证明它正确，不能从递推关系推导增长率，不能解释为什么分析结果如此，那么你拥有的是无法迁移到新问题上的表层熟悉。 | 对每个算法都做三件事：实现它，证明它正确，从第一原则推导复杂度且不看答案。推导才是学习；能运行的代码只是证据。 |
| 遇到动态规划就得出“我不行”的结论 | 动态规划击败的学习者比任何其他主题都多，而这种失败几乎总是被误读成个人问题。困难——识别正确子问题、形式化递推、安排计算顺序——是这项技术内在的，不是能力缺陷。教材系统性地低估了它所需的时间。 | 按教材暗示时间的两到三倍来安排。真正技能是识别子问题结构，而这只能通过题量形成，不是靠阅读解答说明形成。持续做题，直到结构在被命名前就变得可见。 |
| 把“渐近最优”读成“最快” | 渐近分析回答的是一个算法是否可扩展；它并不说明它在某个给定输入和某台给定机器上是否快。一个渐近上更差、但缓存行为更好的算法，在实践中可能快好几倍；这不是理论错了，而是理论回答了不同问题。 | 同时明确保留两个问题：哪个更能扩展（理论回答），哪个在这里更快（测量回答）。当二者分歧时，通常原因是内存层级；先 profile，再判断分析是否具有误导性。 |
| 把 NP-completeness 当成理论脚注 | 学习者常常背下定义，却没有学会在实际问题中识别它，然后花数周寻找一个几乎肯定不存在的高效精确算法。 | 当一个优化问题顽固抵抗时，继续之前先检查它是否类似某个已知 NP-complete 问题——Karp 的 21 个问题是经典参考。及早识别难解性，才能有效转向近似或启发式方法。 |
| 把随机算法当成专门方向而跳过 | 随机算法支撑着日常工具：哈希表、quicksort 的实践性能、多数密码学库中的素性测试、局部敏感哈希、reservoir sampling。把它们当成高级选修内容，会让常见基础设施的根基无法解释。 | 把随机算法与确定性核心一起学习。关键思想——期望情形分析、Las Vegas 与 Monte Carlo 保证——并不困难，而且能澄清许多否则看起来任意的东西。 |