English
An algorithm describes a method for solving a class of problems. A data structure organizes information so that the method’s operations can be carried out. The two are designed together: asking “what is the fastest way to find an item?” is incomplete until we know how items are represented, which queries occur, and how often the collection changes.
For an unsorted array, exact search can require inspecting every item. Sorting enables binary search, but preprocessing and updates have costs. A hash table can offer expected constant-time lookup under suitable hashing and load assumptions; a balanced search tree supports ordered operations with logarithmic comparison counts. None of these descriptions includes every real cost: comparing long strings, accessing memory, and moving data can dominate.
The subject joins three kinds of reasoning: establish what the method computes, bound its resource use in a stated model, and determine which alternatives are possible. Basic programming and discrete mathematics provide the starting point. Probability supports randomized methods; deeper complexity theory explains limits, but useful algorithm design need not wait until that theory is complete.
How the Study of Procedures Became a Mathematical Discipline
Algorithms long predate computers. Arithmetic procedures and Euclid’s greatest-common-divisor method already made repeatable calculation possible. Electronic computing changed the scale of execution and expanded the objects being processed: records, expressions, graphs, and programs joined numbers. Sorting, searching, and compiler construction were central to this broadening beyond numerical calculation.
The study of algorithms did not begin with one textbook. Knuth’s The Art of Computer Programming, beginning in 1968, helped consolidate a discipline in which concrete programs, mathematical analysis, and careful implementation informed one another. Counting operations and explaining correctness made methods comparable beyond a particular machine or successful demonstration.
Complexity theory added a question about problems rather than individual methods: could any efficient algorithm solve every instance? The Cook–Levin theorem and Karp’s reductions established connections among many decision problems through NP-completeness. These connections did not prove that all such problems require exponential time. They showed that a polynomial-time algorithm for any NP-complete problem would yield polynomial-time algorithms for all problems in NP.
Algorithmic practice also expanded the forms of guarantee: amortized bounds for sequences of operations, expected bounds for randomized methods, approximation guarantees, and models that count communication or external-memory transfers. These developments reflect changing workloads and machines. An algorithmic result is most useful when its cost model answers the engineering question actually being asked.
Correctness, Cost, and the Limits of What Is Possible
Keep the problem specification, the algorithm, and the implementation distinct. “Return a shortest path” is a specification; breadth-first search is an algorithm applicable to unweighted graphs; an adjacency-list representation and queue realize it in code. Changing the specification to weighted paths can invalidate the algorithm even if the implementation is flawless. Changing the representation can preserve the answer while changing the cost.
Proving Correctness and Characterizing Cost
Correctness arguments connect local steps to the specification. A sorting algorithm must produce ordered output and preserve the input’s elements with their multiplicities. An invariant alone establishes neither termination nor the adequacy of the specification. For binary search, the candidate interval must retain any possible answer, and its length must decrease whenever the search continues. Boundary conventions make these claims concrete.
Cost analysis needs an input-size measure and a model of primitive operations. A bound in the numerical value of an integer can be exponential in the number of bits used to encode it. Assuming arithmetic is constant-time can be reasonable for fixed-size machine values, but not for arbitrarily large integers. State what is counted before manipulating asymptotic notation.
O gives an asymptotic upper bound; Θ gives a matching order of growth. Neither specifies whether the function being bounded is a worst-case, expected, or amortized cost. An unsorted search has worst-case Θ(n) inspections but may succeed on the first one. Randomized quicksort has expected O(n log n) comparisons under its randomization, while an individual execution can be quadratic. The source of the expectation must be identified.
Amortized analysis instead bounds an entire sequence without requiring a random-input assumption. When a dynamic array doubles its capacity as needed, an occasional append copies many elements, yet n appends from an initially empty array require only O(n) total work. Amortized constant time does not guarantee low latency for each append. A real-time application may care precisely about the expensive operation hidden by that average over the sequence.
The Landscape of Hardness
P and NP are classes of decision problems, whose answers are yes or no. P admits polynomial-time solving; NP admits polynomial-size certificates for yes-instances, checkable in polynomial time. NP does not mean “non-polynomial,” and it includes P. An NP-complete problem is both in NP and at least as hard as every NP problem under the specified polynomial-time reductions. Optimization versions are commonly described as NP-hard rather than placed directly in these decision classes.
Reduction direction is essential. To show a new problem is hard, transform instances of a known hard problem into it while preserving the answer and controlling the transformation’s cost. A fast solver for the new problem would then solve the known one. Reducing the new problem to an existing solvable problem serves a different purpose: it gives a way to solve the new problem. Drawing this direction explicitly prevents a common reversal.
NP-completeness is evidence about general worst-case difficulty, conditional on the unresolved P versus NP question. It does not make every instance difficult or every exact solver useless. Small instances, restricted graph structure, useful parameters, approximation guarantees, and good heuristics can all change the practical options. A heuristic’s success on a workload and a theorem’s guarantee over a class are different kinds of evidence.
Even lower bounds have a model. The Ω(n log n) bound for comparison sorting concerns sorting by comparisons; it does not forbid linear-time methods for appropriately bounded integer keys using additional operations and storage. A limitation becomes informative only when its domain and allowed operations are stated.
The Design Vocabulary
Design techniques are ways of organizing work, not labels to recognize after memorizing a solution. Divide and conquer splits a problem into smaller instances and combines their answers; the split and combination costs determine the recurrence. Dynamic programming identifies reusable subproblems, a sufficient state, and an order in which dependencies can be evaluated. It applies to counting and feasibility as well as optimization.
Coin change gives a small contrast. With denominations {1, 3, 4} and target 6, choosing the largest available coin gives 4 + 1 + 1, whereas 3 + 3 uses fewer coins. A greedy choice needs a proof that its local decision can be extended to an optimum. Dynamic programming can instead define best[s] as the minimum coins needed for amount s, initialize best[0] = 0, and minimize 1 + best[s-c] over permitted coins c ≤ s. The state definition explains the recurrence; the increasing order of s explains why the dependencies are ready.
Data structures encode equally important commitments. A heap supports retrieving an extremal item without maintaining a complete sorted order. A disjoint-set structure supports merging components and testing membership in the same component, not arbitrary graph queries. Path compression together with union by rank or size yields its celebrated near-constant amortized bound. Choose the operations needed before choosing the structure.
The same graph can have different operation costs depending on its representation. For a simple undirected graph with V vertices and E edges, an adjacency matrix stores whether each pair is connected; an adjacency list stores each vertex’s neighbors. Under constant-time indexing, and with ordinary unsorted neighbor lists:
| Operation or requirement | Adjacency matrix | Adjacency lists |
|---|---|---|
| Storage, measured in entries | Θ(V²) |
Θ(V + E) |
Test whether u and v are adjacent |
Θ(1) |
O(1 + degree(u)) |
Enumerate all neighbors of u |
Θ(V) |
Θ(1 + degree(u)) |
Here degree(u) is the number of neighbors of u. Each undirected edge occurs in two lists, which changes the constant but not the Θ(V + E) storage bound. Scanning every vertex’s neighbors costs Θ(V²) with the matrix and Θ(V + E) with lists. This is why a graph-traversal bound must name the representation. On a sparse graph, lists can avoid examining mostly empty matrix entries; repeated edge-existence queries may favor a matrix. The model specifies the relationships, while the representation determines the work needed to access them.
Randomization can change the path of execution while preserving an exact answer, as with randomized quicksort, or trade controlled error probability for lower cost in other algorithms. Approximation algorithms instead provide a bound relating the returned objective value to the optimum under stated assumptions. These are distinct guarantees. The design task is to select a guarantee that meets the problem’s needs and can actually be justified.
What Studying This Changes
The useful habit is to explain cost from total work. Nested loops are not automatically quadratic: in a sliding-window algorithm, an inner pointer may move at most n times across the entire execution. Conversely, a single line calling a library routine may hide substantial computation. Count operations and data movement rather than judging visual syntax.
Recognition becomes valuable when accompanied by checking conditions. A dependency problem may permit topological sorting if the graph is acyclic; some assignment problems become bipartite matching; particular scheduling formulations admit flow algorithms. Similar vocabulary is not enough to establish a reduction.
For practice, keep a simple correct baseline, derive a better method’s invariant and cost, and compare outputs on small generated cases. Then measure representative workloads. The proof explains the guarantee, the comparison catches implementation mistakes, and the measurements expose costs omitted by the model. This combination is more durable than either memorized patterns or timing results alone.
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, Motwani and Raghavan’s Randomized Algorithms develops the probability tools and design ideas behind methods used in hashing, sorting, primality testing, and many streaming algorithms. Williamson and Shmoys’s The Design of Approximation Algorithms (free online) studies efficiently computable solutions with provable bounds relative to the optimum. It is a route to understanding tradeoffs for NP-hard optimization problems, not a claim that efficient exact algorithms have been ruled out unconditionally for all of them.
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 |
|---|---|---|
| Memorizing patterns without conditions | A familiar-looking problem may violate the algorithm’s assumptions. | Explain the specification, representation, and reason each step is valid. |
| Treating running code as a complete analysis | Successful cases establish neither a general guarantee nor a resource bound. | Pair implementation with a correctness argument and an explicit cost model. |
| Guessing complexity from loop nesting | Total iterations depend on how indices progress across the entire run. | Count total work, including library operations and preprocessing. |
| Assuming dynamic programming starts with a recurrence | A recurrence is meaningful only after the state and dependencies are defined. | Describe the subproblem in words, find what information it needs, then order the computation. |
| Reading NP-completeness as proven practical impossibility | The claim concerns a general decision problem and an unresolved complexity question. | Inspect instance size, structure, exact solvers, and approximation options; verify reduction direction. |
| Equating asymptotic, expected, amortized, and measured costs | These answer different questions and rely on different assumptions. | Label the guarantee and test the workload and latency requirements that actually matter. |
中文
算法描述解决一类问题的方法；数据结构组织信息，使方法所需的操作能够执行。两者需要一起设计：在不知道数据如何表示、会出现哪些查询、集合多久变化一次之前，“怎样查找最快”这个问题还不完整。
对于无序数组，精确查找可能需要查看每个元素。排序后可以使用二分查找，但预处理和更新也有成本。在适当的散列与负载假设下，哈希表可以提供期望常数时间的查找；平衡搜索树则以对数级比较次数支持有序操作。这些说法都没有包含所有实际成本：比较长字符串、访问内存和搬运数据，都可能占主要开销。
这一领域结合三种推理：确定方法算出的是什么，在明确模型下约束资源消耗，以及判断还可能有哪些替代方案。基础编程与离散数学是起点，概率支持随机化方法，更深入的复杂性理论解释边界；但不必先学完所有理论，才能开始有效的算法设计。
对过程的研究如何成为一门数学学科
算法远早于计算机。算术步骤和 Euclid 最大公约数算法，已经让可重复的计算成为可能。电子计算改变了执行规模，也扩展了处理对象：记录、表达式、图与程序加入了数值之列。排序、查找和编译器构造，是计算走出纯数值计算的重要部分。
算法研究并非从某一本教材才开始。Knuth 自 1968 年起出版的《计算机程序设计艺术》，帮助整合了一种研究方式：具体程序、数学分析和细致实现相互促进。计算操作次数、解释正确性，使不同方法能够超越某台机器或某次成功演示进行比较。
复杂性理论进一步把问题从具体方法转向问题本身：是否可能有某个高效算法，解决它的每一个实例？Cook–Levin 定理与 Karp 的归约，通过 NP 完全性把许多判定问题连接起来。这些联系没有证明所有此类问题都需要指数时间；它们表明，只要任意一个 NP 完全问题存在多项式时间算法，NP 中的所有问题就都有多项式时间算法。
算法实践也扩展了保证的形式：操作序列的摊还界、随机化方法的期望界、近似保证，以及统计通信量或外存传输次数的模型。这些发展反映了工作负载和机器的变化。当成本模型回答了实际的工程问题时，算法结论才最有用。
正确性、成本与可能性的边界
区分问题规格、算法和实现。“返回最短路径”是规格；广度优先搜索是适用于无权图的算法；邻接表与队列则把它落实为代码。把规格改成带权路径，即使实现完全无误，也可能使算法不再适用。改变表示则可能保持答案不变，却改变成本。
证明正确性与刻画成本
正确性论证把局部步骤连接到规格。排序算法既要产生有序输出，也要保留输入元素及其出现次数。只有不变式，并不能证明终止性，也不能保证规格本身合适。对二分查找，候选区间必须保留任何可能的答案，而且只要搜索继续，区间长度就必须缩小。明确边界约定，才能把这些主张落实。
成本分析需要输入规模的度量，以及基本操作的模型。以整数数值为规模得到的界，换成编码该整数所需的位数后，可能是指数级的。对固定大小的机器数，把算术操作看成常数时间可能合理；对任意大的整数则未必。在处理渐近记号前，先说清统计什么。
O 给出渐近上界，Θ 给出相匹配的增长量级。它们本身都不说明被约束的是最坏、期望还是摊还成本。无序查找最坏需要 Θ(n) 次检查，也可能在第一个元素就成功。随机化快速排序在其随机选择下具有期望 O(n log n) 比较次数，但某次执行仍可能达到平方级。必须说清期望针对哪一种随机性。
摊还分析约束整个操作序列，不要求输入随机。如果动态数组在容量不足时翻倍，某次追加可能复制大量元素，但从空数组开始追加 n 次，总工作量仍只有 O(n)。摊还常数时间，不保证每次追加的延迟都小。实时应用可能恰好关心被序列平均值掩盖的那次昂贵操作。
困难性的景观
P 和 NP 是判定问题的类别，答案为是或否。P 中的问题可以在多项式时间内求解；NP 中的问题，其肯定答案具有长度为多项式、可在多项式时间内检查的证书。NP 不是“非多项式”，而且包含 P。NP 完全问题既属于 NP，又在指定的多项式时间归约下，至少和所有 NP 问题一样难。优化版本通常被称为 NP 困难，而不是直接放入这些判定问题类别。
归约方向至关重要。要证明新问题很难，应把已知困难问题的实例转成新问题实例，同时保持答案对应，并控制转换成本。这样，新问题的快速求解器就能用于解决已知困难问题。反过来，把新问题归约到一个已有解法的问题，是为了获得求解新问题的方法。明确画出这个方向，可以避免常见的颠倒。
NP 完全性提供的是关于一般最坏情形困难程度的证据，其含义取决于尚未解决的 P 与 NP 问题。它不使每个实例都困难，也不使所有精确求解器都失去用途。小实例、受限图结构、有用参数、近似保证和良好启发式，都可能改变实际选择。启发式在某种工作负载上的成功，与定理对一类问题的保证，是不同性质的证据。
即使下界也依赖模型。比较排序的 Ω(n log n) 下界约束的是依靠比较的排序；它并不禁止利用额外操作与存储，对范围适当受限的整数键进行线性时间排序。只有说明适用对象和允许的操作，限制才具有信息价值。
设计词汇
设计技巧是组织工作的方式，不是背熟解法后辨认的标签。分治把问题拆成较小实例，再合并答案；拆分与合并成本决定递推关系。动态规划识别可以复用的子问题、信息足够的状态，以及能够依次计算依赖的顺序。它不仅用于优化，也用于计数和可行性判断。
找零提供了一个小对比。面额为 {1, 3, 4}，目标为 6 时，每次选最大的可用硬币会得到 4 + 1 + 1，而 3 + 3 用得更少。贪心选择需要证明：局部决定能够扩展成最优解。动态规划则可以定义 best[s] 为凑出金额 s 所需的最少硬币数，令 best[0] = 0，再对所有满足 c ≤ s 的可用硬币，取 1 + best[s-c] 的最小值。状态定义解释递推关系，按 s 递增计算则解释依赖为什么已经就绪。
数据结构也包含重要的取舍。堆支持取出极值元素，无需维护完整的排序。并查集支持合并连通分量、判断是否属于同一分量，并不支持任意图查询。路径压缩配合按秩或大小合并，才得到其著名的近常数摊还界。先确定需要哪些操作，再选择结构。
同一张图采用不同表示，操作成本也会不同。对于具有 V 个顶点、E 条边的简单无向图，邻接矩阵记录每对顶点是否相连，邻接表则记录每个顶点的邻居。假设按索引访问的成本为常数，邻居表采用普通的未排序列表：
| 操作或需求 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 按条目数计的存储量 | Θ(V²) |
Θ(V + E) |
判断 u、v 是否相邻 |
Θ(1) |
O(1 + degree(u)) |
枚举 u 的全部邻居 |
Θ(V) |
Θ(1 + degree(u)) |
这里 degree(u) 是 u 的邻居数。每条无向边会出现在两个列表中，这改变常数，但不改变 Θ(V + E) 的存储界。扫描每个顶点的邻居，矩阵需要 Θ(V²)，邻接表需要 Θ(V + E)。因此，图遍历的复杂度必须说明采用哪种表示。对于稀疏图，邻接表能避免检查矩阵中大量表示无边的条目；如果经常查询两点是否相连，矩阵可能更合适。模型规定关系，表示方式则决定访问这些关系需要多少工作。
随机化可以在保留精确答案的同时改变执行路径，例如随机化快速排序；也可以在其他算法中，用受控的错误概率交换更低成本。近似算法则在明确条件下，给出返回目标值与最优值之间的界。这些保证并不相同。设计任务是选择既符合问题需求，又能够得到论证的保证。
学习这一部分会改变什么
有用的习惯是从总工作量解释成本。嵌套循环并不自动等于平方复杂度：在滑动窗口算法中，内层指针在整个执行过程中可能至多移动 n 次。反过来，调用库函数的一行代码也可能隐藏大量计算。应统计操作与数据搬运，而不是凭代码外观判断。
识别模式需要同时检查条件。如果图无环，依赖问题可以使用拓扑排序；某些分配问题能转化为二分图匹配；特定的调度形式可以使用流算法。措辞相似，并不足以建立归约。
练习时，保留一个简单且正确的基准方法，推导改进方法的不变式和成本，并在生成的小实例上比较输出。随后测量有代表性的工作负载。证明解释保证，对照发现实现错误，测量暴露模型遗漏的成本。三者结合，比只背模式或只看运行时间更持久有用。
资源
书籍与文本
标准综合参考是 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 页覆盖核心内容，概念压缩得很不寻常——一旦基础已经到位，它是很有价值的重读材料。
对于随机算法，Motwani 和 Raghavan 的 Randomized Algorithms 发展了散列、排序、素性测试和许多流式算法背后的概率工具与设计思路。Williamson 和 Shmoys 的 The Design of Approximation Algorithms（免费在线）研究能够高效计算、并对结果与最优值的关系给出可证明界的方法。它帮助理解 NP 困难优化问题中的取舍，并不意味着已经无条件排除了所有此类问题的高效精确算法。
有两本书应放在参考书架上。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 | 辅助 |
陷阱
| 陷阱 | 为什么会误导 | 更好的做法 |
|---|---|---|
| 记住模式，却不记适用条件 | 外观熟悉的问题可能违反算法前提。 | 解释规格、表示，以及每一步为什么有效。 |
| 把能运行的代码当成完整分析 | 成功实例既不能建立一般保证，也不能给出资源界。 | 给实现配上正确性论证和明确的成本模型。 |
| 根据循环嵌套猜复杂度 | 总迭代次数取决于索引在整个运行中怎样前进。 | 统计总工作量，包括库操作与预处理。 |
| 认为动态规划从写递推式开始 | 只有先定义状态和依赖，递推式才有含义。 | 用语言描述子问题，确定所需信息，再安排计算顺序。 |
| 把 NP 完全性读成已证明的实际不可能 | 结论针对一般判定问题，并涉及未解决的复杂性问题。 | 检查实例大小、结构、精确求解器与近似选择，并核对归约方向。 |
| 混同渐近、期望、摊还和实测成本 | 它们回答不同问题，依赖不同前提。 | 标明保证类型，检验真正关心的工作负载与延迟要求。 |