📚 A-Level Edexcel Computer Science: Algorithms Key Points | A-Level Edexcel 计算机：算法 考点精讲
Algorithms form the core of computational thinking and problem-solving in Edexcel A-Level Computer Science. From fundamental searching and sorting methods to more advanced graph traversal and efficiency analysis, a solid grasp of how algorithms work, compare, and scale is essential for the examination. This guide walks you through each critical algorithm, its pseudocode structure, time complexity, and common pitfalls, ensuring you are fully prepared for both theory questions and practical coding tasks.
在 Edexcel A-Level 计算机科学中，算法是计算思维和解决问题的核心。从基础的查找、排序方法到更高级的图遍历和效率分析，扎实掌握算法的工作原理、比较方式和规模增长对考试至关重要。本指南将逐一梳理每个关键算法，涵盖其伪代码结构、时间复杂度和常见易错点，确保你为理论题和实践编程任务做好充分准备。
1. Understanding Algorithms | 理解算法
An algorithm is a finite sequence of well-defined, unambiguous instructions designed to solve a specific problem or perform a computation. In Edexcel Computer Science, algorithms must be expressed using clear constructs: sequencing, selection, and iteration. They are independent of any programming language, though you may encounter them in pseudocode or flowcharts.
算法是用来解决特定问题或执行计算的、有限的有序、无歧义的指令序列。在 Edexcel 计算机科学中，算法必须使用清晰的结构表达：顺序、选择和迭代。算法独立于任何编程语言，不过你会经常在伪代码或流程图中见到它们。
Every algorithm has inputs (data to be processed) and outputs (the results). The design process often involves decomposition (breaking a problem into smaller parts) and abstraction (filtering out unnecessary detail). For the exam, you need to be able to both trace an algorithm’s execution step-by-step and reason about its efficiency.
每个算法都有输入（待处理的数据）和输出（结果）。设计过程通常包括分解（将问题拆分为较小部分）和抽象（过滤掉不必要的细节）。在考试中，你需要既能逐步跟踪算法的执行，又能分析其效率。
2. Searching Algorithms: Linear Search | 线性搜索
Linear search is the simplest method: start at the first element and check each item in turn until the target is found or the collection ends. It works on unsorted and sorted lists alike, making no assumptions about data order.
线性搜索是最简单的方法：从第一个元素开始，逐项检查，直到找到目标或遍历完整个集合。它既适用于未排序列表，也适用于已排序列表，不依赖数据的顺序假设。
The algorithm can be described in pseudocode as: for each element, if element equals target, return its position; after the loop, if not found, return a failure indicator. In the worst case, it examines all n elements, giving a time complexity of O(n).
该算法的伪代码可描述为：对每个元素，若元素等于目标值，返回其位置；循环结束后若未找到，返回失败指示。在最坏情况下，它检查全部 n 个元素，时间复杂度为 O(n)。
Although inefficient for large datasets, linear search is straightforward to implement and is the fallback when data is unsorted or when searching in linked lists where direct indexing is impossible.
虽然线性搜索在大数据集上效率不高，但它易于实现，并且在数据未排序或在不支持直接索引的链表中搜索时，是备用方案。
3. Searching Algorithms: Binary Search | 二分搜索
Binary search dramatically reduces the number of comparisons by repeatedly dividing the search interval in half. It requires the list to be sorted in ascending (or descending) order. The algorithm compares the target value to the middle element, eliminating half of the remaining elements each time.
二分搜索通过将搜索区间反复对半分，大幅减少比较次数。它要求列表已按升序（或降序）排序。算法将目标值与中间元素比较，每次排除剩余一半的元素。
In pseudocode: set low to 0, high to n-1; while low ≤ high, mid = (low + high) div 2; if target equals list[mid], return mid; if target is smaller, high = mid – 1; else low = mid + 1. The time complexity is O(log n), which is extremely efficient for large n.
伪代码如下：设 low 为 0，high 为 n-1；当 low ≤ high，mid = (low + high) div 2；若目标等于 list[mid]，返回 mid；若目标更小，high = mid – 1；否则 low = mid + 1。时间复杂度为 O(log n)，对于较大 n 极为高效。
Remember that binary search can be implemented recursively or iteratively. Edexcel often asks you to trace the algorithm on a small array, so practice identifying the mid index at each step and drawing the decision tree.
记住二分搜索可用递归或迭代实现。Edexcel 常要求你在小型数组上跟踪算法，因此要练习识别每一步的 mid 索引并画出判定树。
4. Sorting Algorithms: Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest unsorted element “bubbles up” to its correct position at the end of each pass. The process repeats until no swaps are needed.
冒泡排序重复遍历列表，比较相邻元素，如果顺序错误则交换它们。每轮遍历后，最大的未排序元素会“冒泡”到其正确位置。重复该过程直到不需要任何交换。
A standard optimized bubble sort stops early if a pass completes with zero swaps. Its worst-case and average time complexity is O(n²), making it unsuitable for large datasets. However, it is stable and can be useful on nearly sorted lists.
标准优化版的冒泡排序如果某轮遍历没有发生交换，则提前终止。最坏和平均时间复杂度均为 O(n²)，不适合大数据集。但它具有稳定性，并且在近乎有序的列表上可能有用。
In the exam, you may be asked to perform a dry run, counting comparisons and swaps. Note that Edexcel pseudocode often uses nested loops: a FOR loop from bottom to top or a WHILE loop with a swapped flag.
考试中可能要求你进行纸上演算，计算比较和交换次数。注意 Edexcel 伪代码常使用嵌套循环：从底部到顶部的 FOR 循环，或带有 swapped 标志的 WHILE 循环。
5. Sorting Algorithms: Insertion Sort | 插入排序
Insertion sort builds the final sorted array one item at a time. It iterates through the input, removing one element per iteration and inserting it into its correct position within the sorted portion of the list. Elements to the left are always sorted.
插入排序每次处理一个元素，逐步构建最终有序数组。它遍历输入，每次取一个元素并将其插入到列表已排序部分的正确位置。左侧元素始终有序。
The algorithm can be visualized like sorting playing cards. Starting from the second element, shift larger sorted elements to the right until the correct slot is found. Its time complexity is O(n²) in the worst case, but it performs well on small or nearly sorted datasets, with a best case of O(n).
该算法可类比整理扑克牌。从第二个元素开始，将已排序部分中较大的元素向右移动，直到找到合适的插入位置。最坏时间复杂度为 O(n²)，但在小规模或近乎有序的数据上表现良好，最好情况为 O(n)。
Insertion sort is stable, in‑place, and often used as the final stage of more advanced algorithms like quicksort on small partitions. You should be comfortable writing the loop that shifts elements and inserting the key.
插入排序是稳定的、原地排序，常被用作更高级算法（如快速排序处理小分区）的最终步骤。你应能熟练编写移动元素并插入关键字的循环。
6. Sorting Algorithms: Merge Sort | 归并排序
Merge sort follows the divide-and-conquer paradigm. It recursively splits the unsorted list into n sublists, each containing one element (a list of one element is considered sorted), then repeatedly merges sublists to produce new sorted sublists until only one remains.
归并排序遵循分治范式。它递归地将未排序列表拆分成 n 个子列表，每个子列表包含一个元素（单元素列表视为已排序），然后反复合并子列表生成新的有序子列表，直到最终仅剩一个。
The merging step compares the front elements of two sorted halves and appends the smaller to the result. This requires extra memory for the merged array, so merge sort is not in‑place. Its time complexity is consistently O(n log n) regardless of the initial order.
合并步骤比较两个有序半部分的前端元素，将较小者追加到结果中。这需要为合并后的数组分配额外内存，因此归并排序不是原地排序。无论初始顺序如何，其时间复杂度恒为 O(n log n)。
Merge sort is stable and ideal for large datasets where a guaranteed worst-case performance is needed, such as sorting linked lists or external storage. For Edexcel, understand how to trace the recursive splitting tree and the merging process.
归并排序是稳定的，适合需要保证最坏性能的大数据集，例如对链表或外部存储排序。对于 Edexcel，要理解如何跟踪递归拆分树及合并过程。
7. Sorting Algorithms: Quick Sort | 快速排序
Quick sort also uses divide-and-conquer. It selects a pivot element from the list and partitions the other elements into two sublists: those less than the pivot and those greater than (or equal to) the pivot. It then recursively sorts the sublists.
快速排序也采用分治法。它从列表中选取一个枢轴元素，将其他元素划分为两个子列表：小于枢轴的和大于（等于）枢轴的，然后递归排序子列表。
Pivot selection critically affects performance. If the pivot consistently divides the list into two roughly equal halves, the time complexity is O(n log n). In the worst case (e.g., already sorted list with a poor pivot choice), it degrades to O(n²). Quick sort is in‑place but not stable.
枢轴的选择极大影响性能。如果枢轴始终将列表大致均分，时间复杂度为 O(n log n)。在最坏情况下（如已排序列表且枢轴选择不佳），它会退化至 O(n²)。快速排序是原地排序但不稳定。
Edexcel questions may ask you to apply the partition step on a small array, showing how elements are swapped around the pivot. Be clear on the Lomuto or Hoare partition scheme if specified, though pseudocode is usually provided.
Edexcel 试题可能会要求你对小数组执行划分步骤，展示元素如何围绕枢轴交换。若指定了 Lomuto 或 Hoare 划分方案，需明确，但通常提供伪代码。
8. Graph Traversal: Breadth-First and Depth-First Search | 图遍历：广度优先与深度优先
Graphs model networks, and traversal algorithms explore nodes in a systematic way. Breadth-first search (BFS) explores all neighbors of the current node before moving to the next level, using a queue. Depth-first search (DFS) plunges as deep as possible along a branch before backtracking, typically using a stack or recursion.
图对网络建模，遍历算法以系统化方式探索节点。广度优先搜索（BFS）在进入下一层之前探索当前节点的所有邻居，使用队列。深度优先搜索（DFS）沿一条分支尽可能深入，然后回溯，通常使用栈或递归。
Both algorithms start from a given source vertex and mark nodes as visited to avoid cycles. BFS is ideal for finding the shortest path in unweighted graphs. DFS is useful for topological sorting, detecting cycles, or solving puzzles like mazes.
两种算法都从给定的源顶点开始，并将节点标记为已访问以避免循环。BFS 适合在无权图中寻找最短路径。DFS 可用于拓扑排序、检测环或解决迷宫类谜题。
You must be able to trace BFS and DFS on a given adjacency list or matrix, showing the order of node visits and the data structure contents at each step. Time complexity for both is O(V + E), where V is vertices and E is edges.
你必须能在给定的邻接列表或矩阵上跟踪 BFS 和 DFS，显示节点访问顺序及每一步数据结构的内容。两者的时间复杂度均为 O(V + E)，其中 V 为顶点数，E 为边数。
9. Shortest Path: Dijkstra’s Algorithm | 最短路径：迪杰斯特拉算法
Dijkstra’s algorithm finds the shortest path from a start node to all other nodes in a graph with non‑negative edge weights. It maintains a table of the shortest known distance to each vertex, initially set to infinity except the source (0), and iteratively selects the unvisited vertex with the smallest tentative distance.
迪杰斯特拉算法在边权重非负的图中寻找从起点到所有其他节点的最短路径。它维护一个记录到每个顶点的已知最短距离的表，初始设为无穷大（源点除外设为 0），并迭代选择未访问顶点中试探距离最小的顶点。
After selecting a vertex, the algorithm relaxes its outgoing edges: if the distance to a neighbor via the current vertex is less than the previously recorded distance, it updates the distance and predecessor. This continues until all reachable vertices have been visited.
选中一个顶点后，算法对其出边进行松弛：如果经过当前顶点到达邻居的距离小于先前记录的距离，则更新距离和前驱。持续该过程直到所有可达顶点均已访问。
You need to be able to fill in a distance/predecessor table step by step, often for a small weighted graph. The time complexity can be O(V²) with a simple array, or improved using a priority queue. Note that Dijkstra fails if negative weights exist.
你需要能够逐步填写距离/前驱表，通常用于小型加权图。使用简单数组时时间复杂度为 O(V²)，使用优先队列可优化。注意若存在负权重，迪杰斯特拉算法会失效。
10. Algorithm Efficiency and Big O Notation | 算法效率与大O表示法
Big O notation describes the upper bound of an algorithm’s time or space complexity as the input size n grows, focusing on the dominant term without constants. It helps compare scalability: an O(n) algorithm grows linearly, O(log n) logarithmically, and O(n²) quadratically.
大 O 表示法描述随着输入规模 n 增长，算法时间或空间复杂度的上界，关注主导项并忽略常数因子。它有助于比较可扩展性：O(n) 算法线性增长，O(log n) 对数增长，O(n²) 平方增长。
Common complexities you must know for Edexcel: constant O(1), linear O(n), logarithmic O(log n), linearithmic O(n log n), quadratic O(n²), and exponential O(2ⁿ). You should be able to identify which part of an algorithm contributes to the overall complexity.
Edexcel 要求掌握常见复杂度：常数 O(1)、线性 O(n)、对数 O(log n)、线性对数 O(n log n)、平方 O(n²) 和指数 O(2ⁿ)。你应能识别算法的哪一部分贡献了整体复杂度。
When comparing sorting algorithms, use the summary table below. Also note the difference between worst-case, best-case, and average-case complexity. Space complexity (memory usage) is equally important, especially for merge sort (O(n) extra space).
比较排序算法时参考下表。另需注意最坏、最好和平均情况复杂度的区别。空间复杂度（内存使用）同样重要，特别是归并排序需要 O(n) 额外空间。
| Algorithm | Worst Time | Average Time | Space | Stable |
|---|---|---|---|---|
| Linear Search | O(n) | O(n) | O(1) | N/A |
| Binary Search | O(log n) | O(log n) | O(1) | N/A |
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n²) | O(n log n) | O(log n)¹ | No |
¹ Space for Quick Sort refers to the call stack depth for in‑place partition. | ¹ 快速排序的空间指原地划分的调用栈深度。
11. Recursion vs Iteration | 递归与迭代
Recursion is a technique where a function calls itself to solve smaller instances of the same problem. It relies on a base case to stop and a recursive step that reduces the problem size. Many algorithms, such as binary search, merge sort, and tree traversals, are naturally expressed recursively.
递归是一种函数调用自身以解决同一问题更小实例的技术。它依赖基例来终止，以及一个减小问题规模的递归步骤。许多算法，如二分搜索、归并排序和树遍历，都可以自然地用递归表示。
Iteration uses loops (FOR, WHILE) to repeat instructions. While recursion can be more elegant and mirror mathematical definitions, it consumes stack space and may cause stack overflow for large depths. Every recursive solution can be converted to an iterative one, though it may require an explicit stack.
迭代使用循环（FOR、WHILE）重复执行指令。虽然递归更优雅且反映数学定义，但它消耗栈空间，深度较大时可能导致栈溢出。每个递归解都可以转换为迭代解，尽管可能需要显式栈。
For Edexcel, you may be given a recursive function and asked to trace it, or to identify the base case and recursive call. Understanding tail recursion and the trade-offs between recursion and iteration is part of the algorithm analysis.
在 Edexcel 考试中，可能会给一个递归函数让你跟踪，或让你识别基例与递归调用。理解尾递归以及递归与迭代之间的权衡是算法分析的一部分。
12. Exam Tips and Common Pitfalls | 考试技巧与常见误区
When tracing algorithms, show all variable updates clearly. Use a table to record changes to array elements, indices, and flags. For sorting, always indicate when swaps occur. Many marks are lost by incomplete dry runs.
跟踪算法时，清晰展示所有变量更新。用表格记录数组元素、索引和标志的变化。对于排序，始终标注何时发生交换。很多分数因不完整的纸上演算而丢失。
In pseudocode questions, Edexcel expects precise syntax: consistent indentation, correct use of ← for assignment, and proper loop structures. Avoid mixing programming language keywords; stick to the exam board’s pseudocode guide.
在伪代码题中，Edexcel 期望精确的语法：一致的缩进、使用 ← 表示赋值，以及正确的循环结构。避免混合编程语言关键字；遵循考试局伪代码指南。
A common pitfall is confusing the best, average, and worst cases of an algorithm. Remember that merge sort is O(n log n) in all cases, while quick sort varies. Also, verifying whether a sort is stable can be tested, so know that bubble, insertion, and merge are stable, while quick and heap sort are not.
常见误区是混淆算法的最好、平均和最坏情况。牢记归并排序在所有情况下均为 O(n log n)，而快速排序则不然。此外，对排序稳定性也可能考查，因此要知道冒泡、插入和归并排序是稳定的，而快速排序和堆排序不是。
Finally, when comparing algorithms, always justify with complexity or characteristics. Don’t just say “algorithm X is faster”; relate it to the data size, structure, and requirements (e.g., memory availability, need for stability). Practice with past paper questions to master these reasoning skills.
最后，比较算法时，一定要用复杂度或特性来论证。不要只说“算法 X 更快”；要将其与数据规模、结构及需求（如内存可用性、稳定性需求）联系起来。通过历年真题练习，掌握这些推理技巧。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导