Edexcel Computer Science: Algorithm Key Points Explained | Edexcel 计算机：算法考点精讲

📚 Edexcel Computer Science: Algorithm Key Points Explained | Edexcel 计算机：算法考点精讲

Algorithms form the bedrock of computational thinking and are a central theme in Edexcel Computer Science specifications, from IGCSE to A Level. This revision guide breaks down every essential algorithm concept you need to master, including searching, sorting, pseudocode, flowcharts and efficiency analysis. Each section presents key ideas in both English and Chinese, ensuring bilingual clarity for exam success.

算法是计算思维的基石，也是 Edexcel 计算机科学课程（从 IGCSE 到 A Level）的核心主题。这份考点精讲将带你逐一突破所有必备的算法概念，涵盖搜索、排序、伪代码、流程图以及效率分析。每个小节都以英中双语呈现关键思想，助你清晰理解，决胜考场。

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

An algorithm is a step‑by‑step procedure for solving a problem or completing a task. In computer science, algorithms are expressed in a way that can be implemented on a computer — for example, using pseudocode, flowcharts or programming languages. An effective algorithm must be precise, finite and produce the correct output for all valid inputs.

算法是用于解决问题或完成任务的逐步操作步骤。在计算机科学中，算法要以能够在计算机上实现的方式表达——例如使用伪代码、流程图或编程语言。一个有效的算法必须精确、有限，并且对于所有合法输入都能产生正确的输出。

Key characteristics of a good algorithm include clarity, efficiency and independence from any particular programming language. Algorithms are the backbone of software development, enabling automation, data processing and logical reasoning.

优良算法的关键特征包括清晰、高效且独立于任何特定的编程语言。算法是软件开发的支柱，使自动化、数据处理和逻辑推理成为可能。

2. Pseudocode and Flowcharts | 伪代码与流程图

Pseudocode is a plain‑English‑like notation that outlines an algorithm’s logic without strict syntax. It uses constructs such as IF…ELSE, WHILE…ENDWHILE, FOR…ENDFOR and CASE…ENDCASE. Edexcel exams expect you to both read and write pseudocode, following the style given in the specification’s appendix.

伪代码是一种类似自然语言的记号法，它勾勒出算法的逻辑，没有严格的语法要求。常用的结构包括 IF…ELSE、WHILE…ENDWHILE、FOR…ENDFOR 和 CASE…ENDCASE。Edexcel 考试要求你既能阅读也能书写伪代码，并遵循考纲附录中所给出的风格。

Flowcharts offer a visual representation of an algorithm using standard symbols: ovals for Start/End, parallelograms for input/output, rectangles for processes and diamonds for decisions. Arrows indicate the flow of control. Both pseudocode and flowcharts help programmers design and communicate algorithms before coding.

流程图使用标准化符号来可视化地表示算法：椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理过程，菱形表示判断。箭头指示控制流程。伪代码和流程图都能帮助程序员在编程前设计并沟通算法。

Main flowchart symbols: oval (terminator), rectangle (process), diamond (decision), parallelogram (I/O).
常见流程图符号：椭圆（终止符）、矩形（处理）、菱形（判断）、平行四边形（输入/输出）。
Pseudocode is not tied to any language; it must be unambiguous and structured.
伪代码不依赖任何编程语言；它必须无歧义且结构清晰。

3. Linear Search | 线性搜索

A linear search examines each element in a list sequentially until the target value is found or the end of the list is reached. It is simple to implement and works on unsorted data, but its average and worst‑case time complexity is O(n), making it slow for large datasets.

线性搜索按顺序逐一检查列表中的每个元素，直到找到目标值或到达列表末尾。它实现简单，可以用于未排序的数据，但其平均和最坏情况的时间复杂度为 O(n)，在处理大型数据集时速度较慢。

Pseudocode for a linear search using a WHILE loop: set a pointer i to 0, WHILE i < length AND arr[i] ≠ target, i ← i + 1. If i < length, the target has been found at index i; otherwise the target is not in the list. Edexcel often asks for the number of comparisons made.

使用 WHILE 循环的线性搜索伪代码：设置指针 i 为 0，WHILE i < 长度且 arr[i] ≠ 目标，i ← i + 1。如果 i < 长度，则在索引 i 处找到目标；否则目标不在列表中。Edexcel 常会要求计算比较次数。

A linear search is suitable when the list is small or constantly changing, or when the data is not ordered. However, for sorted data, binary search is far more efficient.

当列表规模较小、频繁变化或数据未排序时，线性搜索是合适的。然而对于已排序的数据，二分搜索的效率要高得多。

4. Binary Search | 二分搜索

Binary search works on a sorted list by repeatedly dividing the search interval in half. It compares the target with the middle element: if they are equal, the search ends; if the target is smaller, the search continues in the left half; otherwise in the right half. The time complexity is O(log n), dramatically faster for large n.

二分搜索适用于已排序的列表，通过反复将搜索区间一分为二来工作。将目标值与中间元素比较：如果相等，搜索结束；如果目标值较小，则在左半部分继续搜索；否则在右半部分。时间复杂度为 O(log n)，对于大量数据速度极快。

Edexcel pseudocode for binary search uses low, high and mid variables. While low ≤ high, mid ← (low + high) DIV 2. If arr[mid] = target, return mid; if arr[mid] < target, low ← mid + 1; else high ← mid – 1. You must be able to trace this algorithm with a trace table.

Edexcel 二分搜索的伪代码使用 low、high 和 mid 三个变量。当 low ≤ high 时，mid ← (low + high) DIV 2。如果 arr[mid] = 目标，返回 mid；如果 arr[mid] < 目标，则 low ← mid + 1；否则 high ← mid – 1。你必须能够用跟踪表来追踪该算法。

Binary search requires random access to the elements, so it is ideal for arrays but not for linked lists. It also requires the data to be ordered first, which might add an initial sorting cost.

二分搜索要求能够随机访问元素，因此非常适用于数组，但不适合链表。它还要求数据事先有序，这可能额外增加排序的开销。

5. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. After each full pass, the largest unsorted element “bubbles” to its correct position at the end of the list. The process repeats until no swaps are needed in a pass.

冒泡排序反复遍历列表，比较相邻元素，并在顺序错误时交换它们。每完成一趟完整遍历，未排序部分的最大元素就会“冒泡”到列表末尾的正确位置。重复该过程，直到一趟遍历中没有发生任何交换为止。

Its worst‑case and average time complexity is O(n²), making it inefficient on large lists. However, bubble sort is simple to understand and can be optimised by stopping early if a pass makes zero swaps. Edexcel may ask you to draw each pass and count the number of comparisons and swaps.

其最坏情况和平均时间复杂度都是 O(n²)，因此在处理大型列表时效率低下。但冒泡排序易于理解，并且可以通过在一趟遍历未发生交换时提前终止来优化。Edexcel 可能会要求你画出每一趟遍历并统计比较和交换的次数。

A variation includes sorting from both ends or comparing bubble sort with other quadratic sorts. In pseudocode, nested loops are used: FOR i ← 0 TO n‑2, FOR j ← 0 TO n‑i‑2, IF arr[j] > arr[j+1] THEN SWAP.

冒泡排序的变体包括从两端同时进行，或将其与其他平方级别的排序进行比较。伪代码中使用嵌套循环：FOR i ← 0 TO n‑2, FOR j ← 0 TO n‑i‑2, IF arr[j] > arr[j+1] THEN SWAP。

6. Insertion Sort | 插入排序

Insertion sort builds the final sorted list one element at a time by taking each new element and inserting it into its correct relative position within the already sorted portion. It resembles how many people sort playing cards in their hands. The algorithm is stable and performs well on small or nearly sorted datasets.

插入排序通过逐个取出新元素并将其插入到已排序部分中的正确相对位置，来逐步构建最终的排序列表。它类似于许多人手中整理扑克牌的方式。该算法是稳定的，对于小型或基本有序的数据集表现良好。

Worst‑case time complexity is O(n²), but best‑case (already sorted) is O(n). Insertion sort requires very little additional memory and is efficient for online sorting where items arrive one by one.

最坏情况时间复杂度为 O(n²)，但最好情况（已经有序）为 O(n)。插入排序仅需极少的额外内存，并且对于逐个元素到达的在线排序十分高效。

In pseudocode, a FOR loop increments an index i from 1 to n‑1, while a WHILE loop shifts elements greater than the current key to the right. Edexcel questions often provide a partially filled trace table for insertion sort.

在伪代码中，FOR 循环将索引 i 从 1 递增到 n‑1，而 WHILE 循环将大于当前键值的元素向右移动。Edexcel 的考题通常会为插入排序提供一个部分完成的跟踪表。

7. Merge Sort | 归并排序

Merge sort is a divide‑and‑conquer algorithm that recursively splits the list into two halves until each sub‑list contains a single element, then repeatedly merges the sub‑lists to produce newly sorted sub‑lists. Its time complexity is O(n log n) in all cases, making it far more scalable than quadratic sorts.

归并排序是一种分治算法：它将列表递归地分成两半，直到每个子列表只包含一个元素，然后反复合并这些子列表以生成新的有序子列表。它在所有情况下的时间复杂度都是 O(n log n)，因此比平方级别的排序具有更好的可扩展性。

Merge sort is stable and particularly efficient for large datasets, although it requires extra memory proportional to n for the merging process. Edexcel requires you to understand the recursive splitting and how the “merge” step works using two pointers.

归并排序是稳定的，对大型数据集尤其高效，尽管它在合并过程中需要与 n 成正比的额外内存。Edexcel 要求你理解递归拆分的过程，以及如何使用两个指针来完成“合并”步骤。

A simplified merge pseudocode: if low < high, mid ← (low+high) DIV 2, mergeSort(low, mid), mergeSort(mid+1, high), then merge the two halves. Exam trace tables usually follow the merge process on an array.

简化的归并伪代码：如果 low < high，则 mid ← (low+high) DIV 2，调用 mergeSort(low, mid) 和 mergeSort(mid+1, high)，然后合并这两半。考试中的跟踪表通常会追踪数组上的合并过程。

8. Algorithm Efficiency and Big O Notation | 算法效率与大O表示法

Algorithm efficiency measures how the resources used — normally time or memory — grow as the size of the input (n) increases. Big O notation describes the upper bound of an algorithm’s growth rate, ignoring constant factors and lower‑order terms. Common classes include O(1), O(log n), O(n), O(n log n) and O(n²).

算法效率衡量的是随着输入规模 (n) 的增长，所使用的资源（通常是时间或内存）如何增长。大O表示法描述算法增长率的上界，忽略常数因子和低阶项。常见的等级包括 O(1)、O(log n)、O(n)、O(n log n) 和 O(n²)。

Constant time O(1) means the algorithm takes the same time regardless of n. Linear time O(n) grows proportionally to n. Quadratic time O(n²) appears in nested loops. A logarithmic time O(log n) halves the problem size at each step — binary search is the classic example.

常数时间 O(1) 表示无论 n 多大，算法都花费相同的时间。线性时间 O(n) 与 n 成正比增长。平方级时间 O(n²) 出现在嵌套循环中。对数时间 O(log n) 每步将问题规模减半——二分搜索就是典型例子。

Edexcel candidates must be able to identify the efficiency class of common algorithms and justify their answer by counting comparisons or loop iterations. You may also need to compare two algorithms and choose the more suitable one for a given scenario.

Edexcel 考生必须能够识别常用算法的效率等级，并通过统计比较次数或循环迭代次数来证明自己的答案。你可能还需要比较两种算法，并针对特定场景选出更合适的那个。

Time (T) ≈ c × f(n) → O(f(n))

时间 (T) ≈ c × f(n) → O(f(n))

9. Common Standard Algorithms | 常见标准算法

Edexcel expects you to know several standard algorithms that act as building blocks: finding the largest or smallest value, counting occurrences, calculating a sum or average, and linear search on a condition. These are often used inside larger programs.

Edexcel 要求你掌握若干作为构建块的标准算法：寻找最大值或最小值、统计出现次数、计算总和或平均值，以及按条件进行线性搜索。这些算法常被用在更大的程序内部。

Finding the maximum: initialise max ← first element, then iterate through the list, updating max if a larger value is found. Counting: initialise count ← 0, and for each element matching the condition, count ← count + 1. These patterns must be memorised and reproduced in pseudocode.

寻找最大值：初始化 max ← 第一个元素，然后遍历列表，如果发现更大的值则更新 max。计数：初始化 count ← 0，对于每个符合条件的元素，执行 count ← count + 1。这些模式必须熟记，并能在伪代码中复现。

Sum and average: sum ← 0, FOR each value, sum ← sum + value; average ← sum / count. Edexcel may embed these in a scenario, such as calculating the average mark of students or finding the youngest person from a record.

求和与平均值：sum ← 0，对于每个值，sum ← sum + value；average ← sum / count。Edexcel 可能将这些算法嵌入到具体场景中，例如计算学生的平均分数，或找出记录中最年轻的人。

10. Testing and Trace Tables | 测试与跟踪表

Testing algorithms with trace tables is a fundamental skill in Edexcel exams. A trace table records the step‑by‑step change in variable values and the output as the algorithm executes. It helps identify logic errors, verify correctness and understand the flow of control.

使用跟踪表测试算法是 Edexcel 考试的一项基本技能。跟踪表记录算法执行过程中变量值与输出的逐步变化。它有助于发现逻辑错误、验证正确性并理解控制流程。

To complete a trace table, start with the initial values, then step through each line of pseudocode, updating variables and output columns. Common mistakes include forgetting to update the loop counter or missing a condition branch. Practice with loops, arrays and nested decisions is essential.

要完成跟踪表，从初始值开始，然后逐行执行伪代码，更新变量和输出列。常见的错误包括忘记更新循环计数器，或遗漏了某个条件分支。针对循环、数组和嵌套判断进行练习至关重要。

Edexcel often gives an incomplete trace table and asks you to fill missing values, or asks for the expected output. Always check whether the question expects the final state or the values after a specific iteration.

Edexcel 通常会提供一个不完整的跟踪表，让你填入缺失的值，或者要求给出预期的输出。务必看清题目是要求最终状态，还是特定迭代后的值。

Step / 步骤	i	target / 目标	arr[i]	Output / 输出
1	0	5	3	—

Simple linear search trace example. / 线性搜索的简单跟踪示例。

Published by TutorHao | Computer Science Revision Series | aleveler.com

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

Edexcel Computer Science: Algorithm Key Points Explained | Edexcel 计算机：算法考点精讲