Algorithms in IB and Edexcel Mathematics: Key Exam Topics | IB与Edexcel数学算法考点精讲

📚 Algorithms in IB and Edexcel Mathematics: Key Exam Topics | IB与Edexcel数学算法考点精讲

Algorithms are the backbone of computational mathematics, linking pure logic to practical problem‑solving. In the IB Diploma Programme and Edexcel A‑Level Mathematics, algorithmic thinking is tested through tracing, designing, and comparing step‑by‑step procedures. This guide breaks down every essential algorithmic topic, highlights syllabus differences, and sharpens your exam technique.

算法是计算数学的支柱，将纯粹的逻辑与实际问题的解决联系起来。在IB文凭项目和Edexcel A‑Level数学中，算法思维通过追踪、设计和对比逐步程序来考查。本指南将逐一解析每个核心算法专题，突出考纲差异，并磨炼你的应试技巧。

---

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

An algorithm is a finite, well‑defined sequence of instructions that takes an input and produces an output. For it to be valid, every step must be unambiguous, feasible, and the process must terminate after a finite number of steps. Both IB and Edexcel exams expect you to recognise these properties and to trace unfamiliar algorithms presented as pseudocode or flowcharts.

算法是一组有限且明确定义的指令序列，接受输入并产生输出。要使其有效，每一步都必须明确、可行，且整个过程必须在有限步内终止。IB和Edexcel考试均要求你识别这些性质，并能追踪以伪代码或流程图给出的陌生算法。

A quick comparison of algorithm topics across IB and Edexcel Mathematics shows the depth required in each syllabus.

Algorithm Topic	IB Mathematics (Analysis & Approaches / Applications)	Edexcel A‑Level Mathematics (Decision 1)
Sorting	Basic understanding; trace a simple sort such as bubble sort.	Detailed: bubble sort, quick sort, shuttle sort; number of comparisons, swaps, tracing tables.
Searching	Binary search may appear in algorithmic thinking questions.	Binary search on an ordered list; tracing and determining the order of checking.
Graph algorithms	Minimal spanning trees and shortest paths are not core but may be explored.	Prim’s, Kruskal’s, Dijkstra’s algorithms on networks; full tracing required.
Critical path analysis	Rarely examined except in extended projects.	Forward/backward passes, float calculations, Gantt charts; exam staple.
Linear programming	Graphical method for two variables; embedding in real‑world problems.	Simplex method, integer programming, including Big‑M and two‑stage simplex.
Bin packing	Not typically assessed.	First‑fit, first‑fit decreasing, full‑bin packing; calculating waste.
Euclidean algorithm	Core in number theory; solving linear Diophantine equations.	May appear in D1 as an example of an iterative algorithm; less emphasis.

快速对比IB与Edexcel数学中的算法主题，可以看出每个考纲所要求的深度。

---

2. Algorithm Representation and Tracing | 算法的表示与追踪

Algorithms are written in pseudocode, flowcharts, or programming‑like statements. You need to follow each instruction meticulously, updating variables in a trace table. A trace table typically records the values of key variables as the algorithm progresses, making it easier to spot patterns or errors.

算法用伪代码、流程图或类似编程的语句编写。你需要一丝不苟地执行每一条指令，在追踪表中更新变量。追踪表通常随着算法的推进记录关键变量的值，便于发现规律或错误。

• English: Use a column for each variable and record the value after each iteration or decision.

• 中文：为每个变量设置一列，并在每次迭代或决策后记录数值。

• English: When tracing loops, check the stopping condition carefully to avoid off‑by‑one mistakes.

• 中文：追踪循环时，仔细检查终止条件，避免差一错误。

• English: For recursive algorithms, draw a tree diagram to visualise function calls and backtracking.

• 中文：对于递归算法，画出树状图以可视化函数调用与回溯。

Example trace: i ← 1, sum ← 0, while i ≤ 5 { sum ← sum + i; i ← i + 1 }

Step	i	sum
Initial	1	0
After 1st loop	2	1
After 2nd loop	3	3
After 3rd loop	4	6
After 4th loop	5	10
After 5th loop	6	15

---

3. Sorting Algorithms: Bubble Sort and Quick Sort | 排序算法：冒泡排序与快速排序

Sorting algorithms are fundamental in both syllabi, especially in Edexcel D1 where you must compare their efficiency. Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each pass, the next largest element “bubbles” to its correct position.

排序算法是两个考纲的基础，尤其是Edexcel D1要求比较它们的效率。冒泡排序反复遍历列表，比较相邻元素，若顺序错误则交换。每趟遍历后，下一个最大元素“冒泡”到正确位置。

Quick sort uses a divide‑and‑conquer strategy. It selects a pivot, partitions the list into sub‑lists of elements less than and greater than the pivot, then recursively sorts the sub‑lists. When implemented well, it has an average time complexity of O(n log₂ n), compared to bubble sort’s O(n²).

快速排序采用分治策略。它选取一个基准值，将列表划分为小于和大于基准值的子列表，然后递归排序子列表。实现良好时，平均时间复杂度为O(n log₂ n)，而冒泡排序为O(n²)。

Bubble sort comparisons per pass: C = ½ n(n−1) → O(n²)

Quick sort: T(n) = 2T(n/2) + n → O(n log₂ n) on average

In the exam, trace bubble sort and quick sort on a small array (e.g., 6 numbers) explicitly, showing each swap and the final arrangement. For quick sort, show the pivot selection and the sub‑lists at each level.

考试中，要对小数组（如6个数字）明确追踪冒泡排序和快速排序，展示每次交换和最终顺序。对于快速排序，展示基准值的选择及每层的子列表。

---

4. Searching Algorithms: Linear and Binary Search | 搜索算法：线性搜索与二分查找

Linear search examines each element in turn until the target is found. It is simple but inefficient for large lists, with complexity O(n). Binary search, on the other hand, requires a sorted list and repeatedly divides the search interval in half. Its time complexity is O(log₂ n), making it much faster for large datasets.

线性搜索依次检查每个元素，直到找到目标。它简单，但对于大列表效率低下，复杂度为O(n)。而二分查找要求列表已排序，并反复将搜索区间减半。时间复杂度为O(log₂ n)，对大数集快得多。

To trace binary search, maintain low, high, and mid indices. Compare the target with the middle value; discard the half that cannot contain the target. Be precise about the new boundaries—common mistakes involve off‑by‑one updates or incorrect termination conditions.

进行二分查找追踪时，维护low、high和mid索引。将目标值与中间值比较，丢弃不可能包含目标的半边。精确设定新边界——常见错误包括边界的差一更新或终止条件不正确。

Binary search interval update: if target > data[mid], low ← mid + 1; else if target < data[mid], high ← mid − 1

要注意二分查找仅适用于有序数组，否则结果无意义。

---

5. Bin Packing Algorithms | 装箱算法

Bin packing is a classic optimisation problem in Edexcel Decision 1. You are given items of various sizes and bins of fixed capacity, and you must pack all items into as few bins as possible. The three examined heuristics are: first‑fit, first‑fit decreasing, and full‑bin packing.

装箱是Edexcel决策数学1中的经典优化问题。给定不同尺寸的物品和等容量的箱子，要求将全部物品装入尽可能少的箱子。三个考查的启发式算法为：首次适应、降序首次适应和满箱装箱。

In first‑fit, you take items in the given order and place each into the first bin that has enough space. First‑fit decreasing sorts items in descending size order first, often yielding a better packing. Full‑bin packing looks for combinations of items that exactly fill a bin, then applies first‑fit to the remainder. You must calculate the wasted space and compare heuristics.

在首次适应中，按给定顺序取物品，放入第一个有足够空间的箱子。降序首次适应先按尺寸降序排列物品，通常可得到更好的装箱。满箱装箱寻找能刚好装满一个箱子的物品组合，然后对剩余物应用首次适应。你必须计算浪费的空间并比较启发式算法。

---

6. Prim’s Algorithm for Minimum Spanning Trees | Prim最小生成树算法

Prim’s algorithm grows a minimum spanning tree (MST) from a starting vertex by repeatedly adding the cheapest edge that connects a new vertex to the tree. It is ideal for dense networks. You must maintain a table listing every vertex, its current cheapest connection cost, and the edge from which it came.

Prim算法从起始顶点出发，不断添加将新顶点连入树的最便宜边，从而生成最小生成树。它适用于稠密网络。你必须维护一个表格，列出每个顶点、当前最便宜的连接成本和来源边。

To trace Prim: pick any start vertex, initialise its cost as 0 and others as ∞. At each step, choose the unvisited vertex with the smallest cost, add it to the tree, and update the costs for all vertices adjacent to this new vertex. The algorithm stops when all vertices are included. Remember to record the order of vertex selection and the edges added, as exam marks often depend on the completion of the trace table.

追踪Prim：选取任意起始顶点，将其成本初始化为0，其他为∞。每一步，选择未访问的最小成本顶点，将其加入树，并更新与该新顶点相邻的所有顶点的成本。当所有顶点都被包括时算法停止。记得记录顶点选择的顺序和添加的边，因为考试分数常取决于追踪表的完整性。

---

7. Kruskal’s Algorithm for Minimum Spanning Trees | Kruskal最小生成树算法

Kruskal’s algorithm builds an MST by scanning all edges in non‑decreasing order of weight, and adding an edge to the tree if it does not create a cycle. It works well on sparse graphs. You must check for cycles systematically, often by drawing the partial tree or listing connected components.

Kruskal算法通过按权重不减顺序扫描所有边，若加入该边不构成环则将其加入树，从而构建MST。它适用于稀疏图。你必须系统地检查环，通常通过画出部分树或列出连通分量。

Tracing Kruskal: list all edges sorted by weight. Work down the list; for each edge, determine whether its endpoints are already connected. If not, add the edge and merge the two components. Continue until the tree contains (n−1) edges. Common pitfalls include forgetting to check for cycles or missing edges of equal weight where the choice may affect the tree shape (but not the total weight).

追踪Kruskal：列出按权重排序的所有边。沿列表进行；对每条边，判断端点是否已连通。若否，则加入该边并合并两个分量。持续进行直至树包含(n−1)条边。常见陷阱包括忘记检查环，或漏掉权重相等的边，其选择可能影响树的形状（但不影响总权重）。

---

8. Dijkstra’s Shortest Path Algorithm | Dijkstra最短路径算法

Dijkstra’s algorithm finds the shortest path from a source vertex to every other vertex in a weighted graph with non‑negative weights. It is a core Edexcel D1 algorithm, often appearing with a trace table that records working values, permanent labels, and the path.

Dijkstra算法在非负权图中寻找从源点到其他每个顶点的最短路径。它是Edexcel D1的核心算法，常与记录工作值、永久标号和路径的追踪表一同出现。

At each iteration, select the unvisited vertex with the smallest temporary (working) label and make it permanent. Then update the working labels of its neighbours. The algorithm guarantees that the final permanent value at each vertex is the length of the shortest path from the source. You must also be able to backtrack the actual route using the “from” column.

每次迭代，选择具有最小临时（工作）标号的未访问顶点并将其变为永久标号。然后更新其邻居的工作标号。该算法保证每个顶点的最终永久值是到源点的最短路径长度。你还必须能够利用“来源”列回溯出实际路径。

Order of permanent labelling reflects the growing shortest-path tree.

---

9. Critical Path Analysis | 关键路径分析

Critical path analysis (CPA) models projects as activity networks (A‑on‑N or A‑on‑A). You must calculate earliest start times, latest start times, and float for each activity. The critical path consists of activities with zero float, and any delay to them delays the whole project.

关键路径分析（CPA）将项目建模为活动网络（节点法或箭线法）。你需要计算每个活动的最早开始时间、最迟开始时间和浮动时间。关键路径由浮动时间为零的活动组成，它们的任何延误都将推迟整个项目。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

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