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

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

Algorithms form the very foundation of computer science. In the IGCSE Edexcel specification, you are expected to understand, design, trace, and evaluate algorithms using pseudocode and flowcharts. This article consolidates all essential algorithm concepts — from searching and sorting to efficiency and trace tables — so you can approach your exam with confidence.

算法是计算机科学的基石。在 Edexcel 的 IGCSE 大纲中，你需要理解、设计、追踪和评估算法，并熟练运用伪代码和流程图。本文梳理了所有关键的算法考点——从搜索排序到效率分析与追踪表——帮助你在考试中游刃有余。

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

An algorithm is a precise, step-by-step sequence of instructions designed to solve a problem or perform a task. It must be unambiguous, finite, and capable of producing the correct output for all valid inputs. Real‑world examples include recipes, assembly manuals, and the steps you follow to log into a social media account.

算法是为解决问题或完成任务而设计的一系列精确、逐步执行的指令。它必须无歧义、有限，并且对所有有效输入都能产生正确输出。现实生活中的例子包括菜谱、组装说明书，以及登录社交媒体账号的步骤。

2. Algorithm Representation | 算法的表示方法

Edexcel expects you to interpret and construct algorithms in two main forms: pseudocode and flowcharts. Pseudocode uses structured English‑like statements and is close to Python syntax, while flowcharts give a visual representation using standard symbols (ovals for start/end, parallelograms for input/output, rectangles for processes, diamonds for decisions).

Edexcel 要求你能够阅读和构建两种主要的算法表示形式：伪代码和流程图。伪代码采用结构化的类英语语句，接近 Python 语法；流程图则通过标准图形符号（椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理，菱形表示判断）提供直观的可视化表示。

Flowchart symbols you must know:
- Oval: Start / End
- Parallelogram: INPUT / OUTPUT
- Rectangle: Process (e.g. calculation)
- Diamond: Decision (Yes/No branches)
必须掌握的流程图符号：
- 椭圆：开始 / 结束
- 平行四边形：输入 / 输出
- 矩形：处理（如计算）
- 菱形：判断（是/否分支）

3. Pseudocode Conventions for Edexcel | Edexcel 伪代码规范

Edexcel uses a Python‑like pseudocode. Key conventions include: variables are assigned using ← or =; input with INPUT; output with OUTPUT or PRINT; selection with IF … THEN … ELSE … ENDIF; and iteration with FOR … TO … NEXT or WHILE … ENDWHILE. String‑handling functions such as LENGTH, SUBSTRING, and concatenation (+) are also tested.

Edexcel 使用类似 Python 的伪代码。主要规范包括：变量赋值使用 ← 或 =；用 INPUT 输入；用 OUTPUT 或 PRINT 输出；选择结构用 IF … THEN … ELSE … ENDIF；循环用 FOR … TO … NEXT 或 WHILE … ENDWHILE。考试还会涉及 LENGTH、SUBSTRING 和连接符（+）等字符串处理函数。

Example – sum of 1 to N:

示例 – 求 1 到 N 的和：

INPUT N
Sum ← 0
FOR i ← 1 TO N
    Sum ← Sum + i
NEXT i
OUTPUT Sum

4. Linear Search | 线性搜索

A linear search checks each element in a list one by one until the target is found or the end of the list is reached. It works on unsorted data and is simple to implement, but its worst‑case and average‑case time complexity is O(n).

线性搜索逐个检查列表中的每个元素，直到找到目标或到达列表末尾。它适用于未排序的数据，实现简单，但其最坏和平均情况的时间复杂度为 O(n)。

Pseudocode for linear search:

线性搜索的伪代码：

FUNCTION linearSearch(list, target)
    FOR i ← 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            RETURN i
        ENDIF
    NEXT i
    RETURN -1
END FUNCTION

Explanation: The function returns the index of target if found, otherwise -1. Each comparison has an equal cost, so searching 1000 items takes up to 1000 steps.

解释：该函数在找到目标时返回其索引，否则返回 -1。每次比较的代价相同，因此搜索 1000 个项目最多需要 1000 步。

5. Binary Search | 二分搜索

Binary search is a much faster algorithm that works only on sorted lists. It repeatedly divides the search interval in half by comparing the middle element with the target. Its time complexity is O(log₂ n), making it ideal for large datasets.

二分搜索是一种快得多的算法，但仅适用于已排序的列表。它通过比较中间元素与目标值，反复将搜索区间减半。其时间复杂度为 O(log₂ n)，非常适合大型数据集。

Pseudocode (iterative):

伪代码（迭代版）：

FUNCTION binarySearch(list, target)
    low ← 0
    high ← LENGTH(list) - 1
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
END FUNCTION

You must be able to trace binary search manually. For a list of 16 items, the maximum number of comparisons is log₂16 = 4.

你必须能够手动追踪二分搜索。对于包含 16 个项的列表，最大比较次数为 log₂16 = 4。

6. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed. It is simple but inefficient with a worst‑case time complexity of O(n²).

冒泡排序反复遍历列表，比较相邻项，如果顺序错误则交换它们。这一遍历过程重复进行，直到没有交换发生。它简单但效率较低，最坏情况时间复杂度为 O(n²)。

Pseudocode for bubble sort (optimised with a swap flag):

冒泡排序的伪代码（使用交换标志优化）：

PROCEDURE bubbleSort(list)
    n ← LENGTH(list)
    REPEAT
        swapped ← FALSE
        FOR i ← 0 TO n - 2
            IF list[i] > list[i+1] THEN
                temp ← list[i]
                list[i] ← list[i+1]
                list[i+1] ← temp
                swapped ← TRUE
            ENDIF
        NEXT i
    UNTIL NOT swapped
END PROCEDURE

Exam questions often ask you to show the state of the list after each pass. After the first pass, the largest element “bubbles” to the end.

考题常要求你展示每次遍历后列表的状态。第一次遍历后，最大的元素会“冒泡”到末尾。

7. Insertion Sort | 插入排序

Insertion sort builds the final sorted list one item at a time. It takes each element from the input and inserts it into its correct position in the already‑sorted part of the list. Its average complexity is also O(n²), but it performs very well on small or nearly sorted datasets.

插入排序一次构建一个有序元素。它从输入中取出每个元素，并将其插入已排序部分的正确位置。其平均时间复杂度也是 O(n²)，但在小型或接近有序的数据集上表现优异。

Pseudocode example:

伪代码示例：

PROCEDURE insertionSort(list)
    FOR i ← 1 TO LENGTH(list) - 1
        currentValue ← list[i]
        position ← i
        WHILE position > 0 AND list[position-1] > currentValue
            list[position] ← list[position-1]
            position ← position - 1
        ENDWHILE
        list[position] ← currentValue
    NEXT i
END PROCEDURE

Trace tables for insertion sort typically track the current element and how earlier elements shift right to make room.

插入排序的追踪表通常跟踪当前元素以及前方元素如何向右移动以腾出空间。

8. Merge Sort | 归并排序

Merge sort is a divide‑and‑conquer algorithm that splits the list into halves recursively, sorts each half, and then merges the two sorted halves back together. It guarantees O(n log₂ n) time complexity regardless of the input. The main trade‑off is the additional memory required for merging.

归并排序是一种分治算法：递归地将列表对半拆分，分别排序，再将两个有序的半部分合并。无论输入如何，它都能保证 O(n log₂ n) 的时间复杂度。主要代价是合并时需要额外内存。

Key steps: split, recursively sort left, recursively sort right, merge. You do not need to write the full pseudocode in the exam, but you must understand how the merge process works and be able to identify merge sort from a description or a diagram.

关键步骤：拆分，递归排序左半部分，递归排序右半部分，合并。考试中不一定需要写出完整伪代码，但必须理解合并过程，并能根据描述或示意图识别归并排序。

9. Algorithm Efficiency & Time Complexity | 算法效率与时间复杂度

Time complexity describes how the running time of an algorithm grows with the size of the input (n). Edexcel focuses on the big‑O notation as an upper bound. Common complexities:

时间复杂度描述算法的运行时间如何随输入规模（n）增长。Edexcel 重点考查大 O 表示法作为上限。常见复杂度：

Complexity	Name	Example
O(1)	Constant	Accessing an array element by index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Linear search, finding max
O(n²)	Quadratic	Bubble sort, insertion sort
O(n log n)	Log‑linear	Merge sort

You should be able to compare algorithms and justify which one is more suitable for a given scenario. For example, binary search is preferable for large sorted datasets because O(log n) grows much slower than O(n).

你应当能够比较算法，并说明在给定场景下哪种算法更合适。例如，对于大型有序数据集，二分搜索更可取，因为 O(log n) 的增长速度远慢于 O(n)。

10. Common Algorithmic Problems | 常见算法问题

Edexcel frequently asks you to write or trace algorithms for fundamental tasks. You must be comfortable with:

Edexcel 经常要求你为基本任务编写或追踪算法。你需要熟练掌握：

Finding the maximum / minimum – initialise a variable with the first element, iterate and compare.
求最大值 / 最小值 – 用第一个元素初始化一个变量，遍历并比较。
Counting occurrences – use a counter that increments when a condition is met.
计数出现次数 – 使用计数器，在满足条件时递增。
Calculating the average – sum all elements, then divide by the count.
计算平均值 – 累加所有元素，然后除以元素个数。
Linear search with conditions (e.g. find the first even number).
带条件的线性搜索（例如查找第一个偶数）。

These building blocks also appear in larger programming tasks. Ensure your pseudocode uses correct loops and decision structures.

这些基本构件也会出现在更大的编程任务中。请确保你的伪代码使用了正确的循环和判断结构。

11. Testing Algorithms with Trace Tables | 使用追踪表测试算法

A trace table is a manual testing technique where you record the values of all variables as you step through an algorithm line by line. It helps identify logical errors and understand how the algorithm runs. You will often be asked to complete a trace table for a given algorithm in the exam.

追踪表是一种手动测试技术：逐行执行算法并记录所有变量的值。它有助于发现逻辑错误并理解算法的运行过程。考试中常要求你为给定算法填写追踪表。

Example trace table for a simple loop that finds the sum of even numbers from 1 to 5:

以下是一个简单循环的追踪表示例，该循环求 1 到 5 中偶数的和：

Total ← 0
FOR i ← 1 TO 5
    IF i MOD 2 = 0 THEN
        Total ← Total + i
    ENDIF
NEXT i

Line no.	i	Total	i MOD 2 = 0?
1	–	0	–
2	1	0	False
2	2	2	True
2	3	2	False
2	4	6	True
2	5	6	False
6	out of loop	6	–

Always update cells in a trace table in the correct order and be careful with loop boundaries.

请始终按正确顺序更新追踪表中的单元格，并注意循环边界。

12. Exam Tips for Algorithm Questions | 算法题的考试技巧

When tackling algorithm questions, start by reading the problem statement carefully. Identify the inputs, desired outputs, and any constraints. For tracing tasks, use a trace table even if the question does not explicitly ask for one — it prevents careless mistakes. For writing pseudocode, keep your logic clear and use indentation exactly as shown in Edexcel materials.

解答算法题时，首先要仔细阅读问题描述。识别输入、期望输出和任何约束条件。对于追踪题，即使题目没有明确要求，也建议使用追踪表——它能避免粗心错误。编写伪代码时，保持逻辑清晰，并严格按照 Edexcel 资料中的方式缩进。

Memorise the search and sort algorithms; you may be asked to fill in missing lines or correct errors. Practice past‑paper questions where you are given a trace table and must identify what the algorithm does. And always check whether the algorithm uses 0‑based or 1‑based indexing; Edexcel usually uses 0‑based indexing for lists but read the question carefully.

熟记搜索和排序算法；考试中可能让你补全缺失的代码行或纠正错误。多做真题，练习根据追踪表识别算法功能。还要注意算法使用的是 0‑based 索引还是 1‑based 索引；Edexcel 通常对列表使用从 0 开始的索引，但务必仔细审题。

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

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

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