📚 IGCSE AQA Computer Science: Algorithms – Key Points | IGCSE AQA 计算机：算法 考点精讲
Algorithms form the backbone of computer science, providing step-by-step procedures for solving problems and processing data. In the AQA IGCSE specification, you are expected to understand, design, and evaluate algorithms using flowcharts and pseudocode, with special emphasis on standard searching and sorting techniques. This guide covers all the essential concepts, from algorithmic thinking to efficiency analysis, with clear explanations and examples written in a style that matches the examination requirements.
算法是计算机科学的支柱，它以逐步执行的过程来解决各类问题并处理数据。AQA IGCSE 课程要求你能够使用流程图和伪代码来理解、设计并评价算法，尤其要掌握标准的搜索与排序技术。本文涵盖了从算法思维到效率分析的全部核心概念，并提供清晰说明与示例，完全贴合考试风格。
1. What Is an Algorithm? | 什么是算法？
An algorithm is a precise, step-by-step set of instructions designed to perform a specific task or solve a particular problem. It must be unambiguous, have a finite number of steps, and produce a result. Everyday examples include cooking recipes and assembly manuals, but in computing, algorithms manipulate data, control program flow, and form the basis of all software.
算法是一组精确的、逐步执行的指令，旨在完成特定任务或解决特定问题。它必须明确无歧义、步骤有限并能产生结果。日常生活中的例子包括菜谱和装配说明，而在计算领域中，算法用来操控数据、控制程序流程，是所有软件的基础。
2. Representing Algorithms: Flowcharts and Pseudocode | 算法表示：流程图与伪代码
Algorithms can be described visually using flowcharts or textually using pseudocode. A flowchart uses standard symbols: an oval for start/end, a rectangle for a process, a parallelogram for input/output, and a diamond for a decision. Arrows indicate the flow of control. Pseudocode, on the other hand, uses structured English-like statements such as IF … THEN … ELSE … ENDIF and WHILE … DO … ENDWHILE to represent logic without worrying about the exact syntax of a programming language.
算法可以用流程图或伪代码来描述。流程图使用标准符号：椭圆形表示开始／结束，矩形表示处理过程，平行四边形表示输入／输出，菱形表示判断。箭头指示控制流。伪代码则使用结构化的类英语语句，如 IF … THEN … ELSE … ENDIF 和 WHILE … DO … ENDWHILE，从而无需考虑编程语言的具体语法即可表示逻辑。
3. Sequence, Selection, and Iteration | 顺序、选择与迭代
All algorithms are built from three fundamental control structures: sequence (executing instructions one after another), selection (choosing between different paths using conditions, e.g., IF statements), and iteration (repeating a block of code using loops such as WHILE, REPEAT…UNTIL, or FOR). Understanding how these structures combine is crucial for designing correct and efficient algorithms.
所有算法均由三种基本控制结构构建而成：顺序（按序执行指令）、选择（利用条件选择不同路径，如 IF 语句）和迭代（使用 WHILE、REPEAT…UNTIL 或 FOR 等循环重复执行代码块）。理解这些结构如何组合，对于设计正确、高效的算法至关重要。
4. Linear Search | 线性搜索
A linear search checks each element of a list one by one until the target value is found or the end of the list is reached. It works on both unsorted and sorted data. In the worst case, it examines every item, making its time complexity O(n). For small datasets it is simple to implement, but it becomes inefficient for large lists.
线性搜索逐个检查列表中的每个元素，直到找到目标值或到达列表末尾。它既适用于未排序数据，也适用于已排序数据。最坏情况下需要检查每一项，时间复杂度为 O(n)。对于小数据集，它易于实现，但对于大型列表则效率不高。
- Example pseudocode: FOR i ← 1 TO LENGTH(list) DO IF list[i] = target THEN OUTPUT i ENDIF NEXT
- 示例伪代码：FOR i ← 1 TO LENGTH(list) DO IF list[i] = target THEN OUTPUT i ENDIF NEXT
5. Binary Search | 二分搜索
A binary search requires the data to be sorted. It repeatedly divides the search interval in half by comparing the middle element with the target. If the target is smaller, the search continues in the lower half; if larger, in the upper half. This systematic halving reduces the number of comparisons dramatically, resulting in a time complexity of O(log n). The AQA specification expects you to trace the algorithm on a given list and understand its preconditions.
二分搜索要求数据必须预先排序。它通过将中间元素与目标值比较，反复将搜索区间对半分。若目标值更小，则在下半部分继续搜索；若更大，则在上半部分继续。这种系统化的对半分割大幅减少了比较次数，时间复杂度为 O(log n)。AQA 大纲要求你能够对给定列表执行该算法的跟踪，并理解其前提条件。
- Pseudocode snippet: low ← 1, high ← LENGTH(list), WHILE low ≤ high DO mid ← (low+high) DIV 2
- 伪代码片段：low ← 1, high ← LENGTH(list), WHILE low ≤ high DO mid ← (low+high) DIV 2
6. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. After each pass, the largest unsorted element “bubbles” to its correct position at the end. This process is repeated until no more swaps are needed, meaning the list is sorted. Bubble sort is easy to understand but inefficient for large datasets, with a worst-case time complexity of O(n²).
冒泡排序反复遍历列表，比较相邻项，并在顺序错误时进行交换。每完成一趟遍历，当前未排序部分的最大元素就会“冒泡”到其正确位置（列表末尾）。重复该过程直到不再需要交换，表示列表已排好序。冒泡排序易于理解，但对大数据集效率低下，最坏时间复杂度为 O(n²)。
Example with array [5, 3, 8, 1] → Pass 1: compare 5 and 3 → swap → [3,5,8,1]; compare 5 and 8 → no swap; compare 8 and 1 → swap → [3,5,1,8]; end pass 1, now the last element is in correct position.
示例数组 [5, 3, 8, 1] → 第一趟：比较 5 和 3 → 交换 → [3,5,8,1]；比较 5 和 8 → 不交换；比较 8 和 1 → 交换 → [3,5,1,8]；第一趟结束，最后一个元素已位于正确位置。
7. Merge Sort | 归并排序
Merge sort is a divide-and-conquer algorithm that splits the list into smaller sublists until each sublist contains only one element (which is trivially sorted). It then repeatedly merges adjacent sublists to produce new sorted sublists until a single sorted list is obtained. Merge sort is much more efficient than bubble sort for large data, with a time complexity of O(n log n), but it requires additional memory space for the merging process.
归并排序是一种分治算法：它将列表拆分为更小的子列表，直到每个子列表只包含一个元素（此时已经有序）。然后反复合并相邻子列表以生成新的有序子列表，最终得到一个完整的有序列表。归并排序处理大数据时远比冒泡排序高效，时间复杂度为 O(n log n)，但合并过程需要额外的内存空间。
Consider splitting [38, 27, 43, 3, 9, 82, 10] into [38,27,43,3] and [9,82,10], further dividing until single elements, then merging in sorted order: [3,27,38,43] and [9,10,82] → final merge → [3,9,10,27,38,43,82].
考虑将 [38, 27, 43, 3, 9, 82, 10] 拆分为 [38,27,43,3] 和 [9,82,10]，再继续划分至单个元素，然后按序合并：[3,27,38,43] 和 [9,10,82] → 最终合并 → [3,9,10,27,38,43,82]。
8. Insertion Sort | 插入排序
Insertion sort builds the final sorted list one item at a time, picking the next element from the unsorted portion and inserting it into the correct position within the already sorted part of the list. It behaves like sorting playing cards in your hand. For nearly sorted data, insertion sort is very fast, with a best-case time complexity of O(n), but its worst-case remains O(n²).
插入排序每一次从待排序部分取出下一个元素，并将其插入到已排序部分的正确位置，从而逐步构建最终的有序列表。它的工作方式类似于整理手中的扑克牌。对于近乎有序的数据，插入排序非常快，最佳时间复杂度为 O(n)，但最坏情况仍为 O(n²)。
For list [4, 3, 2, 10, 12, 1, 5, 6], start with the first element as sorted. Take 3, insert before 4 → [3,4,2,10,12,1,5,6]; take 2, insert at beginning → [2,3,4,10,12,1,5,6]; proceed until the entire list is sorted.
对于列表 [4, 3, 2, 10, 12, 1, 5, 6]，先将第一个元素视为已排序。取出 3，插入到 4 之前 → [3,4,2,10,12,1,5,6]；取出 2，插入到最前面 → [2,3,4,10,12,1,5,6]；继续此过程直至整个列表有序。
9. Comparing Sorting and Searching Algorithms | 排序与搜索算法对比
Choosing the right algorithm depends on the size of the dataset, whether the data is already sorted, and memory constraints. Search algorithms: linear search works unconditionally but is slower; binary search is fast but requires sorting. Sorting algorithms: bubble sort and insertion sort are simple and use little extra memory, but are slow on large lists; merge sort is fast and consistent, yet uses extra space. The AQA exam often asks you to compare these algorithms in terms of efficiency, suitability, and memory usage.
选择正确的算法取决于数据集的大小、是否已排序以及内存限制。搜索算法：线性搜索适用于任何情况，但速度较慢；二分搜索很快，但要求数据有序。排序算法：冒泡排序和插入排序简单且占用极少额外内存，但在大型列表上偏慢；归并排序快速且稳定，但需要额外空间。AQA 考试经常要求你从效率、适用性和内存使用等方面比较这些算法。
| Algorithm | Time (Worst) | Space | Stable? |
|---|---|---|---|
| Linear Search | O(n) | O(1) | N/A |
| Binary Search | O(log n) | O(1) | N/A |
| Bubble Sort | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n) | Yes |
10. Algorithmic Thinking and Problem Decomposition | 算法思维与问题分解
Before coding, it is essential to break down complex problems into smaller, manageable parts — a process called decomposition. Abstraction involves focusing on the essential details while ignoring irrelevant information. Algorithmic thinking then finds the logical sequences and repetitions needed to solve each subproblem. Together, these skills allow you to design structured solutions that are easier to implement and debug.
在编写代码之前，必须将复杂问题拆分为更小、更容易处理的部分，这一过程称为分解（decomposition）。抽象（abstraction）指专注于关键细节而忽略无关信息。算法思维则找出解决每个子问题所需的逻辑序列和重复。这些技能共同使你能够设计出结构化的解决方案，从而更易于实现和调试。
For example, designing a program to manage a library involves decomposing into tasks like adding a book, searching, borrowing, and returning. Each task can then be turned into an algorithm using the structures and patterns already covered.
例如，设计一个图书馆管理程序时，可以将其分解为添加图书、搜索、借阅和归还等任务。然后可以使用前面介绍的结构和模式为每项任务设计算法。
11. Tracing Algorithms and Identifying Errors | 跟踪算法与识别错误
A key exam skill is to trace an algorithm by populating a trace table, which records the values of variables at each step. This helps you understand how an algorithm works, verify its correctness, or find logical errors. You should practice tracing both pseudocode and flowchart-based algorithms, paying attention to loop counters, conditions, and updates. Being able to spot mistakes like off-by-one errors or incorrect assignment sequences is essential for high marks.
一项关键的考试技能是通过填写跟踪表（trace table）来跟踪算法，该表记录每一步的变量值。这有助于你理解算法如何工作、验证其正确性或发现逻辑错误。你应当练习跟踪伪代码和基于流程图的算法，同时注意循环计数器、条件和更新操作。能够发现诸如“差一错误”（off-by-one error）或错误的赋值顺序等问题，对获得高分至关重要。
Example trace table snippet for a loop summing numbers: Step: 1, i=1, sum=0 → 2, i=2, sum=1 → 3, i=3, sum=3 → …
循环求和的跟踪表示例：步骤1：i=1, sum=0 → 步骤2：i=2, sum=1 → 步骤3：i=3, sum=3 → …
12. Efficiency and the Big O Notation | 效率与大 O 表示法
The AQA specification introduces the concept of time complexity using Big O notation as a way of describing how the running time of an algorithm grows relative to the size of the input, n. Constant time O(1) means the algorithm takes the same amount of time regardless of input size. Linear time O(n) means the time grows proportionally with n. Quadratic time O(n²) indicates the time grows as the square of n. Understanding these categories helps you select the most suitable algorithm for a given data size.
AQA 大纲使用大 O 表示法引入时间复杂度的概念，用以描述算法的运行时间相对于输入规模 n 的增长情况。常数时间 O(1) 表示无论输入大小如何，算法用时相同。线性时间 O(n) 表示时间与 n 成正比增长。平方时间 O(n²) 表示时间按 n 的平方增长。理解这些分类有助于你针对给定的数据规模选择最合适的算法。
Common complexities to remember: searching a sorted list with binary search — O(log n); searching an unsorted list — O(n); bubble sort — O(n²); merge sort — O(n log n). In the exam, you may be asked to state the complexity of a given algorithm or to explain why one algorithm is more efficient than another for large data.
需要记住的常见复杂度：对有序列表进行二分搜索 — O(log n)；搜索无序列表 — O(n)；冒泡排序 — O(n²)；归并排序 — O(n log n)。考试中可能会要求你给出给定算法的复杂度，或解释为什么某种算法处理大数据时比另一种更高效。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导