Algorithm Essentials for AQA A-Level Computer Science | A-Level AQA 计算机：算法考点精讲

📚 Algorithm Essentials for AQA A-Level Computer Science | A-Level AQA 计算机：算法考点精讲

Algorithms sit at the heart of computer science and the AQA A-Level specification demands a rigorous understanding of how they work, how to evaluate them, and how to select the right tool for a given problem. This revision guide unpacks the essential algorithmic concepts: sorting and searching, big O notation, recursion, and graph traversal — all aligned with the AQA pseudocode style. By mastering these ideas, you will not only excel in Paper 1 but also build the analytical thinking required for the Non-Exam Assessment (NEA).

算法是计算机科学的核心，AQA A-Level 大纲要求透彻理解算法的工作原理、如何评估算法以及如何为特定问题选择合适的工具。本复习指南将解析核心算法概念：排序与搜索、大 O 表示法、递归以及图遍历——全部与 AQA 伪代码风格一致。掌握这些内容不仅能帮助你在 Paper 1 中脱颖而出，也能培养 NEA（非考试评估）所需的分析思维。

1. What is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of unambiguous, well-defined instructions designed to solve a specific problem or perform a computation. Every algorithm must have a clear starting state, a series of discrete steps that an executor can follow, and a guaranteed termination after a finite number of operations. In the AQA context, algorithms are expected to be deterministic: for the same input, they always produce the same output.

算法是一个有限的、无歧义的、定义明确的指令序列，旨在解决特定问题或完成某种计算。每个算法都必须有清晰的初始状态、一系列执行者可遵循的离散步骤，并在有限次操作后保证终止。在 AQA 的语境中，算法被要求是确定性的：对于相同的输入，总是产生相同的输出。

Algorithms can be expressed in multiple forms. Natural language is useful for initial design, whereas flowcharts offer a visual map of decisions and loops. In the exam, however, the standard medium is pseudocode — a structured, language-agnostic notation that resembles AQA’s reference language. This allows you to concentrate on logic without getting tangled in syntax. For instance, a simple algorithm to find the maximum value in a list can be written as:

算法可以用多种形式表达。自然语言适合初步设计，流程图则提供决策和循环的可视化映射。然而在考试中，标准媒介是伪代码——一种结构化的、与语言无关的记法，类似于 AQA 的参考语言。这使你能够专注于逻辑，而非拘泥于语法。例如，一个寻找列表中最大值的简单算法可以写成：

Pseudocode:
FUNCTION FindMax(arr)
max ← arr[0]
FOR i ← 1 TO LENGTH(arr)-1
IF arr[i] > max THEN
max ← arr[i]
ENDIF
ENDFOR
RETURN max
ENDFUNCTION

伪代码：
FUNCTION FindMax(arr)
max ← arr[0]
FOR i ← 1 TO LENGTH(arr)-1
IF arr[i] > max THEN
max ← arr[i]
ENDIF
ENDFOR
RETURN max
ENDFUNCTION

2. Representing Algorithms: Pseudocode and Flowcharts | 算法的表示：伪代码与流程图

AQA assesses your ability to interpret and write pseudocode that uses standard constructs such as IF…ELSE…ENDIF, FOR…ENDFOR, WHILE…ENDWHILE, and REPEAT…UNTIL. All variables are considered local unless specified otherwise, and array indices start at zero. Subroutines are declared with PROCEDURE or FUNCTION; the latter returns a value using RETURN. Indentation is used to show block structure, but braces or other block markers (apart from ENDIF, ENDFOR) are not required in AQA’s style.

AQA 会评估你解读和书写伪代码的能力，这些伪代码使用标准的程序结构，如 IF…ELSE…ENDIF、FOR…ENDFOR、WHILE…ENDWHILE 和 REPEAT…UNTIL。所有变量默认视为局部变量，数组索引从零开始。子程序用 PROCEDURE 或 FUNCTION 声明；后者通过 RETURN 返回值。缩进用于表示块结构，但在 AQA 风格中不需要大括号或其他块标记（除了 ENDIF、ENDFOR 等）。

Flowcharts complement pseudocode by providing a graphical representation. A parallelogram denotes input/output, a rectangle indicates a process, a diamond shows a decision, and arrows connect the flow. While flowcharts are less common in AQA exam questions, being able to trace through one or draw a simple flowchart still appears in specification requirements. Both methods enforce the same logical rigor, and learning to switch between them strengthens your algorithmic thinking.

流程图作为伪代码的补充，提供图形化表示。平行四边形表示输入/输出，矩形表示处理，菱形表示判断，箭头连接流程。尽管流程图在 AQA 试题中较少出现，但能够追踪流程图或绘制简单流程图仍是大纲要求的一部分。两种方法都强制同样的逻辑严谨性，学会在它们之间切换有助于强化你的算法思维。

3. Efficiency and Big O Notation | 效率与大 O 表示法

Big O notation provides a high-level mathematical language to describe the performance or complexity of an algorithm. It focuses on how the time (or space) requirement grows as the size of the input, typically denoted n, increases. Constant factors and lower-order terms are ignored to reveal the dominant trend. Common complexities in AQA include O(1) — constant time, O(log n) — logarithmic, O(n) — linear, O(n log n) — linearithmic, O(n²) — quadratic, and O(2ⁿ) — exponential.

大 O 表示法提供了一种高层次的数学语言，用于描述算法的性能或复杂度。它关注随着输入规模（通常用 n 表示）的增长，时间（或空间）需求如何变化。常数因子和低阶项被忽略，以揭示主导趋势。AQA 中常见的复杂度包括 O(1)——常数时间，O(log n)——对数，O(n)——线性，O(n log n)——线性对数，O(n²)——平方，以及 O(2ⁿ)——指数。

To determine the time complexity, count the number of fundamental operations as a function of n. For a simple loop that iterates through an array of length n, the body executes n times, giving O(n). Nested loops often lead to O(n²). A divide-and-conquer algorithm that halves the problem size each step typically yields O(log n) if the conquer step is O(1). Understanding these patterns allows you to compare algorithms quickly; for instance, a binary search (O(log n)) scales far better than a linear search (O(n)).

要确定时间复杂度，需将基本操作的次数表示为 n 的函数。对于一个遍历长度为 n 的数组的简单循环，循环体执行 n 次，故为 O(n)。嵌套循环通常导致 O(n²)。每一步将问题规模减半的分治算法，如果组合步骤为 O(1)，一般产生 O(log n)。理解这些模式能让你快速比较算法；例如，二分查找（O(log n)）比线性查找（O(n)）的扩展性好得多。

4. Linear Search | 线性查找

A linear search examines each element of a list sequentially until the target value is found or the end of the list is reached. It does not require the data to be sorted. This makes it applicable to any data set, but its worst-case performance is O(n), which becomes inefficient for large collections. In the best case, the target is at the very first position, yielding O(1).

线性查找按顺序检查列表的每个元素，直到找到目标值或抵达列表末尾。它不要求数据是有序的，这使其适用于任何数据集，但最坏情况性能为 O(n)，对大规模集合效率低下。在最好情况下，目标位于第一个位置，产生 O(1)。

Consider an array [7, 2, 9, 4, 1] with target 4. The algorithm checks 7, then 2, then 9, and finally 4 at index 3, where it stops. AQA questions may ask you to trace the search, writing out each comparison. A typical pseudocode structure is:

考虑数组 [7, 2, 9, 4, 1] 和目标值 4。算法先检查 7，再检查 2，接着检查 9，最终在索引 3 处找到 4 后停止。AQA 题目可能要求你追踪查找过程，写出每一次比较。典型的伪代码结构如下：

Pseudocode:
FUNCTION LinearSearch(arr, target)
FOR i ← 0 TO LENGTH(arr)-1
IF arr[i] = target THEN
RETURN i
ENDIF
ENDFOR
RETURN -1
ENDFUNCTION

伪代码：
FUNCTION LinearSearch(arr, target)
FOR i ← 0 TO LENGTH(arr)-1
IF arr[i] = target THEN
RETURN i
ENDIF
ENDFOR
RETURN -1
ENDFUNCTION

5. Binary Search | 二分查找

Binary search works on a sorted array by repeatedly dividing the search interval in half. Compare the target with the middle element. If they match, the search ends. If the target is smaller, the search continues in the left subarray; if larger, the right subarray is explored. This logarithmic reduction gives a worst-case time complexity of O(log₂ n), making binary search extremely efficient for large, sorted data sets. However, the initial sorting step or maintaining order introduces an overhead.

二分查找在有序数组上通过反复将搜索区间一分为二来工作。将目标值与中间元素比较；若匹配则查找结束。若目标较小，则在左子数组中继续搜索；若较大，则探索右子数组。这种对数缩减使最坏时间复杂度为 O(log₂ n)，令二分查找对于大规模有序数据集极为高效。但初始排序步骤或维持有序性会引入额外开销。

When tracing binary search, track the lower and upper bounds. For array [2, 5, 8, 12, 16, 23, 38] and target 16, start with low=0, high=6. Mid=3 (value 12). Since 16>12, low becomes 4. Next mid=(4+6)//2=5 (value 23); 16<23 so high becomes 4. Next mid=4 (value 16) — found. AQA often asks for the sequence of comparisons or to implement the algorithm, including the case when the target is absent.

在追踪二分查找时，需记录下界和上界。对于数组 [2, 5, 8, 12, 16, 23, 38] 和目标值 16，起始 low=0，high=6。mid=3（值 12）。由于 16>12，low 变为 4。下一个 mid=(4+6)//2=5（值 23）；16<23，所以 high 变为 4。下一个 mid=4（值 16）——找到。AQA 经常要求给出比较序列或实现算法，包括目标不存在的情况。

6. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element ‘bubbles up’ to its correct position. The algorithm stops when no swaps are made during a pass, indicating the list is sorted. While intuitive, bubble sort has a worst-case and average time complexity of O(n²), making it impractical for large data sets. The best-case scenario (already sorted list) is O(n) if the algorithm includes an early-exit check.

冒泡排序反复遍历列表，比较相邻元素并在顺序错误时交换它们。每完成一次完整遍历，最大的未排序元素就会“冒泡”到其正确位置。当某次遍历未发生任何交换时，算法停止，表明列表已有序。虽然冒泡排序直观，但其最坏和平均时间复杂度为 O(n²)，对于大数据集不实用。如果算法包含提前退出检查，最佳情况（已排序列表）为 O(n)。

A typical trace for [5, 1, 4, 2] would show: Pass 1: (5,1) swap → [1,5,4,2]; (5,4) swap → [1,4,5,2]; (5,2) swap → [1,4,2,5]. Pass 2: (1,4) ok, (4,2) swap → [1,2,4,5]; (4,5) ok. Pass 3: no swaps → done. In pseudocode:

对于 [5, 1, 4, 2] 的典型追踪会展示：第 1 趟：(5,1) 交换 → [1,5,4,2]；(5,4) 交换 → [1,4,5,2]；(5,2) 交换 → [1,4,2,5]。第 2 趟：(1,4) 不变，(4,2) 交换 → [1,2,4,5]；(4,5) 不变。第 3 趟：无交换 → 结束。伪代码：

Pseudocode:
PROCEDURE BubbleSort(arr)
n ← LENGTH(arr)
REPEAT
swapped ← FALSE
FOR i ← 0 TO n-2
IF arr[i] > arr[i+1] THEN
SWAP arr[i], arr[i+1]
swapped ← TRUE
ENDIF
ENDFOR
UNTIL NOT swapped
ENDPROCEDURE

伪代码：
PROCEDURE BubbleSort(arr)
n ← LENGTH(arr)
REPEAT
swapped ← FALSE
FOR i ← 0 TO n-2
IF arr[i] > arr[i+1] THEN
SWAP arr[i], arr[i+1]
swapped ← TRUE
ENDIF
ENDFOR
UNTIL NOT swapped
ENDPROCEDURE

7. Insertion Sort | 插入排序

Insertion sort builds the sorted list one element at a time. It iterates through the input, removes the next element and inserts it into its correct position within the already-sorted portion. This is analogous to sorting playing cards in your hand. The algorithm works efficiently on small or nearly sorted data sets, with a best-case O(n) and worst-case O(n²). In the worst case, each insertion may require shifting all previously sorted elements.

插入排序一次一个元素地构建有序列表。它迭代输入，取出下一个元素并将其插入到已排序部分的正确位置。这类似于整理手中的扑克牌。该算法在小型或近似有序的数据集上效率很高，最佳情况为 O(n)，最坏情况为 O(n²)。在最坏情况下，每次插入可能需要移动所有先前已排序的元素。

Tracing insertion sort on [4, 3, 2, 1]: Start with sorted portion [4]. Take 3, compare, shift: [4,4] → insert 3 → [3,4]. Next insert 2: [3,4] → [3,3,4] → [3,3,4] then [2,3,4]. Next insert 1 yields [1,2,3,4]. AQA examination questions often ask you to complete the trace table for the intermediate steps and to identify the number of comparisons made.

对 [4, 3, 2, 1] 追踪插入排序：起始已排序部分 [4]。取出 3，比较，移动：[4,4] → 插入 3 → [3,4]。接着插入 2：[3,4] → [3,3,4] → 然后 [2,3,4]。最后插入 1 得到 [1,2,3,4]。AQA 试题常要求补全中间步骤的追踪表，并识别所做的比较次数。

8. Merge Sort | 归并排序

Merge sort is a classic divide-and-conquer algorithm. It recursively splits the array into halves until each subarray contains a single element (which is inherently sorted). Then it repeatedly merges two sorted subarrays into a larger sorted array. The merging step compares the front elements of the two subarrays, placing the smaller one into the result. This yields a consistent O(n log n) time complexity in all cases, making merge sort highly reliable. However, it requires O(n) additional space for the temporary arrays.

归并排序是经典的分治算法。它递归地将数组分成两半，直到每个子数组只含一个元素（天然有序）。然后反复将两个有序子数组合并成一个更大的有序数组。合并步骤比较两个子数组的首元素，将较小者放入结果中。这使得在所有情况下都具有稳定的 O(n log n) 时间复杂度，使归并排序非常可靠。但它需要 O(n) 额外空间用于临时数组。

AQA often asks you to illustrate the merge sort process, showing the tree of splits and subsequent merges. For [5, 2, 4, 7, 1, 3, 2, 6], the split goes until 8 single elements, then merges pairwise back. You may need to write a simplified pseudocode showing the recursive approach. A common pattern is:

AQA 经常要求演示归并排序过程，展示分割树和随后的合并。对于 [5, 2, 4, 7, 1, 3, 2, 6]，分割至 8 个单元素，再成对合并回来。你可能需要写出展示递归方法的简化伪代码。常见模式如下：

Pseudocode:
FUNCTION MergeSort(arr)
IF LENGTH(arr) <= 1 THEN RETURN arr ENDIF
mid ← LENGTH(arr) DIV 2
left ← MergeSort(arr[0..mid-1])
right ← MergeSort(arr[mid..END])
RETURN Merge(left, right)
ENDFUNCTION

伪代码：
FUNCTION MergeSort(arr)
IF LENGTH(arr) <= 1 THEN RETURN arr ENDIF
mid ← LENGTH(arr) DIV 2
left ← MergeSort(arr[0..mid-1])
right ← MergeSort(arr[mid..END])
RETURN Merge(left, right)
ENDFUNCTION

9. Quick Sort | 快速排序

Quick sort is another divide-and-conquer algorithm that selects a ‘pivot’ element from the array and partitions the other elements into two subarrays — those less than the pivot and those greater than (or equal to) the pivot. The algorithm then recursively sorts the subarrays. With a good pivot selection (e.g., random or median-of-three), quick sort achieves an average time of O(n log n). However, the worst-case (e.g., already sorted array with naive pivot) is O(n²). It sorts in-place, requiring O(log n) auxiliary space on the call stack.

快速排序是另一种分治算法，它从数组中选择一个“基准”元素，并将其他元素划分到两个子数组中——小于基准的元素和大于（或等于）基准的元素。然后算法递归地对子数组排序。通过良好的基准选择（例如随机或三数取中），快速排序平均时间为 O(n log n)。然而最坏情况（如对已排序数组使用朴素基准选择）为 O(n²)。它是原地排序，只需 O(log n) 栈上辅助空间。

Tracing quick sort involves showing the pivot choice, the partition step, and the resulting arrays. For instance, pivot=4 on [3,6,1,4,2]: partition yields left [3,1,2], pivot [4], right [6]; then recursively sort left and right. AQA may ask for a trace that includes the recursive calls and the state of the array at each stage. A high-level pseudocode is:

追踪快速排序需展示基准选择、划分步骤及结果数组。例如，在 [3,6,1,4,2] 上取 pivot=4：划分产生 left [3,1,2]，pivot [4]，right [6]；然后递归排序左右部分。AQA 可能要求包含递归调用和各阶段数组状态的追踪。高层伪代码：

Pseudocode:
PROCEDURE QuickSort(arr, low, high)
IF low < high THEN
pi ← Partition(arr, low, high)
QuickSort(arr, low, pi-1)
QuickSort(arr, pi+1, high)
ENDIF
ENDPROCEDURE

伪代码：
PROCEDURE QuickSort(arr, low, high)
IF low < high THEN
pi ← Partition(arr, low, high)
QuickSort(arr, low, pi-1)
QuickSort(arr, pi+1, high)
ENDIF
ENDPROCEDURE

10. Recursion and Its Role in Algorithms | 递归及其在算法中的作用

Recursion is a technique where a function calls itself to solve smaller instances of the same problem until a base case is reached. Many elegant algorithms, such as merge sort, quick sort, and tree traversals, rely on recursion. A recursive solution must have a base case that stops the recursion and a recursive step that moves toward that base. For example, a recursive factorial function: FACT(0)=1 (base), else FACT(n)=n×FACT(n-1).

递归是一种技术，函数调用自身来求解同一问题的更小实例，直至达到基准情形。许多优雅的算法，如归并排序、快速排序和树遍历，都依赖递归。递归解决方案必须有一个停止递归的基准情形，以及向基准情形靠近的递归步骤。例如，递归阶乘函数：FACT(0)=1（基准），否则 FACT(n)=n×FACT(n-1)。

Recursion can simplify code but must be used carefully because each call allocates stack memory; too deep a recursion leads to stack overflow. Iterative equivalents often exist and may be more memory efficient. In AQA exams, you may be asked to trace a recursive call, identify the base case, or compare a recursive algorithm with its iterative counterpart in terms of readability and efficiency.

递归能简化代码

Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Algorithm Essentials for AQA A-Level Computer Science | A-Level AQA 计算机：算法考点精讲