📚 Algorithm Key Points in A-Level Computer Science | A-Level 计算机：算法 考点精讲
Algorithms form the very backbone of computer science, providing step-by-step procedures to solve problems efficiently. In A-Level Computer Science, a solid grasp of algorithmic concepts is essential, as they underpin everything from programming tasks to theoretical analysis. This article breaks down the key topics you must master, covering definitions, representation, core searching and sorting algorithms, complexity analysis using Big O notation, recursion, divide-and-conquer, and an introduction to graph algorithms – all presented with clear bilingual explanations to support your revision.
算法是计算机科学的基石，它为高效解决问题提供了一步一步的过程。在 A-Level 计算机科学中，扎实掌握算法概念至关重要，因为它们支撑着从编程实践到理论分析的方方面面。本文将逐一剖析你必须掌握的核心考点，涵盖定义、表示方法、基本搜索与排序算法、使用大 O 符号进行的复杂度分析、递归、分治策略，以及图算法简介——所有内容都配有清晰的双语解释，助力你的复习备考。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous instructions designed to solve a specific problem or perform a computation. It takes an input, processes it through a series of steps, and produces an output. In everyday life, a recipe for baking a cake or a manual for assembling furniture can be thought of as algorithms. In computing, algorithms are implemented as programs or functions that manipulate data. The key idea is that an algorithm must terminate after a finite number of steps and should be precise enough to be carried out by a machine without any human intuition.
算法是一组有限的、定义明确且无歧义的指令序列，旨在解决特定问题或执行某种计算。它接受输入，通过一系列步骤进行处理，并产生输出。在日常生活中，烘焙蛋糕的食谱或组装家具的说明书都可以看作是算法。在计算领域，算法被实现为操作数据的程序或函数。核心思想在于，算法必须经过有限步骤后终止，并且应足够精确，使得机器无需任何人类直觉即可执行。
2. Characteristics of Algorithms | 算法的特性
All valid algorithms share five essential characteristics: Input (zero or more quantities are externally supplied), Output (at least one quantity is produced), Definiteness (each instruction is clear and unambiguous), Finiteness (the algorithm terminates after a finite number of steps), and Effectiveness (every operation must be basic enough to be carried out, in principle, by a person using pencil and paper). Without these properties, a set of instructions cannot be considered an algorithm. For A-Level exams, you will often be asked to evaluate whether a given procedure meets these criteria, especially finiteness and definiteness.
所有有效算法都具备五个基本特性：输入（外部提供零个或多个量）、输出（至少产生一个量）、明确性（每条指令清晰无歧义）、有限性（算法在有限步后终止）和有效性（每个操作都必须足够基本，原则上可由人用纸笔完成）。缺少这些性质，一组指令就不能被视为算法。在 A-Level 考试中，你经常会被要求评估一个给定过程是否满足这些标准，尤其是有限性和明确性。
3. Expressing Algorithms: Pseudocode and Flowcharts | 表达算法：伪代码与流程图
Algorithms can be expressed in several ways, but the two most common for A-Level are pseudocode and flowcharts. Pseudocode is a structured, language-independent description that uses common programming constructs like IF...ELSE, WHILE loops, and assignment arrows (←). It omits syntax-specific details, allowing the logic to shine through. Flowcharts use standard symbols – ovals for start/end, parallelograms for input/output, rectangles for processes, and diamonds for decisions – connected by arrows to show the flow of control. Both methods help in planning programs and communicating ideas before coding begins.
算法可以用多种方式表达，但在 A-Level 中最常见的两种是伪代码和流程图。伪代码是一种结构化的、与语言无关的描述，使用类似编程的构造，如 IF...ELSE、WHILE 循环和赋值箭头（←）。它省略了语法特定细节，让逻辑清晰展现。流程图则使用标准符号——椭圆表示开始/结束、平行四边形表示输入/输出、矩形表示处理步骤、菱形表示判断——通过箭头连接以显示控制流。这两种方法都有助于在编写代码之前规划程序并传递思想。
4. Basic Search Algorithms | 基本搜索算法
Searching for an item in a data structure is one of the most fundamental operations. The simplest approach is linear search, which sequentially checks each element of a list until a match is found or the end is reached. Its time complexity is O(n) in the worst case, where n is the number of elements. For sorted data, binary search offers a much faster alternative. Starting with the middle element, it repeatedly halves the search interval, discarding half of the remaining elements each time. This algorithm runs in O(log n) time, but it requires random access and a sorted array. Understanding the preconditions and performance of each method is a classic exam topic.
在数据结构中搜索某个元素是最基本的操作之一。最简单的方法是线性搜索，它依次检查列表中的每一个元素，直到找到匹配项或到达末尾。在最坏情况下，其时间复杂度为 O(n)，其中 n 是元素数量。对于已排序的数据，二分搜索提供了一种快得多的替代方案。它从中间元素开始，反复将搜索区间减半，每次丢弃剩余元素的一半。该算法以 O(log n) 时间运行，但需要随机访问和有序数组。理解每种方法的前提条件和性能是经典的考试主题。
5. Basic Sorting Algorithms | 基本排序算法
Sorting algorithms arrange data into a particular order, typically ascending or descending. Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order; passes continue until no swaps are needed. Although easy to understand, its worst-case performance is O(n²). Insertion sort builds the sorted list one item at a time by inserting each new element into its correct position among the previously sorted ones. It is efficient for small or nearly sorted datasets, also with O(n²) worst-case. Merge sort, a recursive divide-and-conquer algorithm, splits the list into halves, sorts them recursively, and then merges the sorted halves. Merge sort guarantees O(n log n) time but uses additional memory. Comparisons of these algorithms form a core part of the curriculum.
排序算法将数据按特定顺序（通常是升序或降序）排列。冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们；遍历持续进行，直到不需要任何交换。虽然容易理解，但其最坏情况性能为 O(n²)。插入排序逐个构建已排序列表，将每个新元素插入到前面已排好序部分的正确位置。它对小型或近乎有序的数据集很高效，最坏情况也为 O(n²)。归并排序是一种递归的分治算法，它将列表分成两半，递归排序每一半，然后合并已排序的两半。归并排序保证 O(n log n) 时间，但使用额外内存。对这些算法的比较构成课程的核心部分。
6. Time Complexity Analysis | 时间复杂度分析
Time complexity measures the amount of time an algorithm takes to complete as a function of the input size n. It is not measured in seconds but in the number of elementary operations performed. We typically focus on the worst-case scenario, which provides an upper bound on the running time. For example, searching an unsorted list may require checking all n elements, so worst-case time is proportional to n. Complexity is expressed using asymptotic notations like Big O, which describes the growth rate while ignoring constants and lower-order terms. This allows us to compare algorithms independently of hardware or implementation details.
时间复杂度衡量算法完成所需的时间与输入规模 n 的函数关系。它不是以秒为单位测量，而是以执行的基本操作次数来度量。我们通常关注最坏情况，它为运行时间提供了一个上界。例如，搜索一个未排序列表可能需要检查所有 n 个元素，因此最坏情况时间与 n 成正比。复杂度使用渐近符号（如大 O）表示，它描述增长率，同时忽略常数项和低阶项。这使我们能够独立于硬件或实现细节来比较算法。
7. Big O Notation | 大 O 符号
Big O notation formally describes the upper bound of an algorithm's time or space complexity. Common classes include O(1) (constant time, e.g., array index access), O(log n) (logarithmic, e.g., binary search), O(n) (linear, e.g., linear search), O(n log n) (linearithmic, e.g., efficient sorting algorithms like merge sort), O(n²) (quadratic, e.g., bubble sort), and O(2ⁿ) (exponential, e.g., recursive calculation of Fibonacci numbers without memoization). When analyzing an algorithm, you count the number of loop iterations and recursive calls, summarising the dominant term. For A-Level exams, you must be able to identify the complexity of a given piece of pseudocode and justify your answer by explaining how the number of operations grows with input size.
大 O 符号形式上描述算法时间复杂度或空间复杂度的上界。常见的类别包括 O(1)（常数时间，如数组索引访问）、O(log n)（对数时间，如二分搜索）、O(n)（线性时间，如线性搜索）、O(n log n)（线性对数时间，如归并排序等高效排序算法）、O(n²)（二次方时间，如冒泡排序）和 O(2ⁿ)（指数时间，如无记忆化的递归斐波那契数列计算）。分析算法时，你需统计循环迭代和递归调用的次数，概括主导项。在 A-Level 考试中，你必须能够识别给定伪代码的复杂度，并通过解释操作次数如何随输入规模增长来证明你的答案。
8. Space Complexity | 空间复杂度
Space complexity refers to the total memory space required by an algorithm relative to the input size. This includes memory for input values, auxiliary variables, and the call stack in recursive implementations. An algorithm that operates in-place, like many implementations of insertion sort, uses O(1) extra space beyond the input storage. On the other hand, merge sort requires additional arrays to hold the merged results, leading to O(n) auxiliary space. In recursive algorithms, each recursive call adds a frame to the call stack, so the maximum depth of recursion contributes to space complexity. Being able to analyse both time and space trade-offs is an important skill.
空间复杂度是指算法相对于输入规模所需的总内存空间。这包括输入值的内存、辅助变量以及递归实现中的调用栈。原地算法，如插入排序的许多实现，除了输入存储外仅使用 O(1) 额外空间。而另一方面，归并排序需要额外的数组来存放合并结果，导致 O(n) 辅助空间。在递归算法中，每次递归调用都会向调用栈添加一个帧，因此最大递归深度影响空间复杂度。能够分析时间和空间的权衡关系是一项重要技能。
9. Recursive Algorithms | 递归算法
he base case is a condition that stops the recursion, preventing infinite loops. Classic examples include calculating factorials (n! = n × (n-1)! with 0! overlapping subproblems are recomputed many times. Techniques like memoization (caching results) and tail recursion can mitigate some drawbacks. Comparing iterative and recursive solutions is a common examination task.
递归算法通过将问题分解为同一问题的更小子实例来解决问题，调用自身直到达到基本情况。基本情况是停止递归的条件，可防止无限循环。经典例子包括计算阶乘（n! = n × (n-1)!，其中 0! = 1）和遍历树结构。递归通常能产生优雅简洁的代码，但如果重叠子问题被多次重复计算，则在时间和空间上可能较低效。记忆化（缓存结果）和尾递归等技术可以缓解一些缺陷。比较迭代与递归解法是常见的考试任务。
10. Common Algorithm Design Paradigms | 常用算法设计范式
Divide and conquer is a powerful paradigm that breaks a problem into independent subproblems, solves them recursively, and then combines their solutions. Merge sort and binary search are prime examples. The greedy approach makes the locally optimal choice at each step, hoping to find a global optimum. Dijkstra's shortest path algorithm (for non-negative weights) uses a greedy strategy, as does the minimum spanning tree algorithm of Prim. Dynamic programming (DP) is used when subproblems overlap; it solves each subproblem once and stores the solution, often using a table. Classic DP examples include the Fibonacci sequence and the 0/1 knapsack problem. Recognising which paradigm fits a problem is a key higher-order skill.
分治是一种强大的范式，它将问题分解为独立的子问题，递归求解，然后合并它们的解。归并排序和二分搜索是典型例子。贪心方法在每一步做出局部最优选择，希望找到全局最优解。Dijkstra 最短路径算法（针对非负权重）使用了贪心策略，Prim 的最小生成树算法也是如此。动态规划用于子问题重叠的情况；它只求解每个子问题一次并存储解，通常使用表格。经典的 DP 例子包括斐波那契数列和 0/1 背包问题。识别哪种范式适合某个问题是一项关键的高阶技能。
11. Introduction to Graph Algorithms | 图算法简介
Graphs model pairwise relationships between objects, with vertices (nodes) and edges. Important algorithms include breadth-first search (BFS) and depth-first search (DFS), which traverse or search a graph in different orders. BFS uses a queue to explore neighbours level by level, finding the shortest path in an unweighted graph. DFS uses a stack (or recursion) to go as far as possible along each branch before backtracking. For weighted graphs, Dijkstra's algorithm finds the shortest path from a single source to all other nodes, using a priority queue. These algorithms are often examined through step-by-step tracing on small graphs, so practising manual simulation is vital.
图用顶点（节点）和边来建模对象之间的成对关系。重要算法包括广度优先搜索（BFS）和深度优先搜索（DFS），它们以不同顺序遍历或搜索图。BFS 使用队列逐层探索邻居，可在无权图中找到最短路径。DFS 使用栈（或递归）沿每条分支尽可能深入，然后再回溯。对于带权图，Dijkstra 算法使用优先队列查找从单一源到所有其他节点的最短路径。这些算法常通过在小型图上逐步追踪的方式进行考查，因此练习手动模拟至关重要。
12. Algorithm Correctness and Testing | 算法正确性与测试
An algorithm must not only be efficient but also correct – it must produce the right output for all valid inputs. Verification involves reasoning about the logic, often using loop invariants or induction. Testing complements verification by running the algorithm with carefully chosen test cases: typical cases, boundary cases (empty list, single element, very large values), and erroneous inputs. Trace tables are a valuable exam tool; they record the values of variables during step-by-step execution of an algorithm, helping to identify logic errors. Being able to construct a trace table for a given algorithm and a set of inputs is a frequently tested skill.
算法不仅必须高效，还必须正确——它必须为所有有效输入产生正确的输出。验证涉及对逻辑的推理，通常使用循环不变量或归纳法。测试通过使用精心挑选的测试用例运行算法来补充验证：典型情况、边界情况（空列表、单元素、极大值）以及错误输入。跟踪表是一种有价值的考试工具；它记录在算法逐步执行过程中变量的值，有助于识别逻辑错误。能够为给定算法和一组输入构建跟踪表是一项经常被测试的技能。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图