📚 IB Math: Algorithms Key Points Review | IB 数学：算法考点精讲
Algorithms form a vital part of the IB Mathematics curriculum, especially within the Analysis and Approaches (AA) and Applications and Interpretation (AI) courses at Higher Level. From numerical methods that approximate solutions to equations and differential equations, to graph theory routines that optimise networks and schedules, the ability to apply step-by-step procedures with precision is essential. This guide consolidates the most examined algorithm topics, explaining each method clearly, comparing alternatives where relevant, and linking theory to the typical question styles seen in IB exams.
算法是 IB 数学课程的重要组成部分，尤其是在分析与方法 (AA) 以及应用与解释 (AI) 的高级课程中。无论是近似求解方程和微分方程的数值方法，还是优化网络与日程的图论程序，严谨地应用逐步求解的过程至关重要。本指南汇集了最常考的算法专题，清晰解释每一种方法，在相关处对比不同算法的优劣，并将理论联系 IB 考试中常见的题型风格。
1. What Is an Algorithm? | 什么是算法？
An algorithm is a finite, well-defined sequence of instructions designed to solve a specific problem or perform a computation. In IB Mathematics, algorithms appear in contexts such as root-finding (Newton-Raphson), numerical integration, solving differential equations (Euler's method), graph optimisation (Prim, Kruskal, Dijkstra), scheduling (critical path analysis), sorting, and searching. Each algorithm has specified input, output, and a series of unambiguous steps that guarantee a result, provided certain conditions are met. Understanding the underlying logic, not just the mechanical execution, is frequently tested through tracing, modification, and efficiency analysis questions.
算法是用于解决特定问题或执行计算的一组有限且明确的指令序列。在 IB 数学中，算法出现在求根（牛顿-拉夫森法）、数值积分、解微分方程（欧拉法）、图优化（普里姆、克鲁斯卡尔、迪杰斯特拉算法）、日程安排（关键路径分析）、排序和搜索等情境中。每一种算法都有规定的输入、输出和一系列清晰的步骤，只要满足特定条件就能保证得到结果。考试不仅考查算法的机械执行，还常常通过跟踪执行过程、修改步骤和分析效率等问题来测试对底层逻辑的理解。
When studying algorithms, pay attention to prerequisites (e.g. differentiability for Newton-Raphson, a weighted connected graph for Dijkstra), special cases that may cause failure, and the computational cost measured by Big O notation.
学习算法时，要注意前提条件（如牛顿-拉夫森法要求可微，迪杰斯特拉算法需要带权连通图）、可能导致算法失败的特殊情况，以及以大 O 记号衡量的计算成本。
2. Newton-Raphson Method | 牛顿-拉夫森法
The Newton-Raphson method iteratively finds approximations to the roots of a real-valued function f(x). Starting from an initial guess x₀, successive approximations are generated using the tangent line at the current point:
xₙ₊₁ = xₙ − f(xₙ) / f '(xₙ)
牛顿-拉夫森法通过迭代求实函数 f(x) 的根的近似值。从一个初始猜测值 x₀ 开始，利用当前点处的切线生成逐次近似值：
xₙ₊₁ = xₙ − f(xₙ) / f '(xₙ)
Convergence is usually fast (quadratic) near a simple root, but the method can fail if f ' om the initial guess is far from the actual root, or if the function exhibits oscillatory behaviour. IB questions typically ask you to perform two or three iterations, to demonstrate that the sequence converges to a given accuracy, or to discuss why the method might diverge. Always store intermediate results to the required degree of accuracy to avoid rounding errors that can affect subsequent steps.
在单根附近，该方法通常收敛很快（二次收敛），但如果 f '(xₙ) = 0、初始猜测值离实际根太远，或函数呈现振荡行为，算法可能会失败。IB 考题一般要求进行两到三次迭代，证明序列收敛到指定精度，或讨论方法可能发散的原因。中间结果需要存储到要求的精度，以避免舍入误差影响后续步骤。
quations such as x³ − 2x − 5 = 0. Suppose we start with x₀ = 2, then f(x) = x³ − 2x − 5, f ' −5)/(12−2) = 2 − (−1)/10 = 2.1. Further iterations quickly approach the root near 2.09455.
一个常见应用是求解如 x³ − 2x − 5 = 0 的方程。假设从 x₀ = 2 开始，f(x) = x³ − 2x − 5，f '(x) = 3x² − 2。第一次迭代得到 x₁ = 2 − (8−4−5)/(12−2) = 2 − (−1)/10 = 2.1。继续迭代将迅速逼近 2.09455 附近的根。
3. Euler's Method for Differential Equations | 解微分方程的欧拉法
Euler' = y₀. Using a fixed step size h, the method advances the solution by linear extrapolation:
yₙ₊₁ = yₙ + h · f(xₙ, yₙ), xₙ₊₁ = xₙ + h
欧拉法为带有初始条件 y(x₀) = y₀ 的一阶常微分方程 dy/dx = f(x, y) 提供数值解。使用固定的步长 h，该方法通过线性外推推进解：
yₙ₊₁ = yₙ + h · f(xₙ, yₙ), xₙ₊₁ = xₙ + h
ive rounding error. IB problems often supply a table with columns for xₙ, yₙ, and f(xₙ, yₙ), and ask you to complete a few steps or to compare the Euler approximation with an exact solution. Always calculate f(xₙ, yₙ) at the current point before computing the next y-value. If the differential equation is expressed as dy/dx = g(x, y), rewrite it correctly before plugging numbers.
精度取决于步长：h 越小，局部截断误差（与 h² 成正比）越小，但步骤增多，累积的舍入误差也会增加。IB 试题常提供一个包含 xₙ、yₙ 和 f(xₙ, yₙ) 的表格，要求完成若干步，或者将欧拉近似值与精确解进行比较。计算下一组值时，一定要先计算当前点的 f(xₙ, yₙ)。如果微分方程以 dy/dx = g(x, y) 给出，代入数值前应正确写出表达式。
4. Dijkstra's Shortest Path Algorithm | 迪杰斯特拉最短路径算法
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It maintains a set of unvisited vertices and a table of tentative distances. At each step, the unvisited vertex with the smallest tentative distance is marked as visited, and the distances to its neighbours are updated (relaxed) if a shorter path is found via the current vertex. This greedy approach guarantees optimality.
迪杰斯特拉算法在边权非负的加权图中找出从源顶点到其余所有顶点的最短路径。算法维护一个未访问顶点集合和一张临时距离表。每一步，选择未访问顶点中临时距离最小的顶点标记为已访问，并通过当前顶点更新（松弛）其邻居的距离，如果找到更短路径。这种贪心策略能保证最优解。
IB examinations often present a network diagram and require you to construct the distance table, showing the order in which vertices become permanent. Common pitfalls include missing multiple path updates when a vertex's distance can be lowered multiple times before being made permanent, and forgetting that once a vertex is made permanent its distance is final. The algorithm is typically terminated when the destination vertex is made permanent or when all vertices have been visited.
IB 考试常给出网络图，要求构建距离表并标出顶点被永久标记的顺序。常见错误包括：在某顶点被永久标记之前，其距离可能多次降低但未及时记录更新；忘记一旦顶点被永久标记其距离就不再改变。算法通常在目标顶点被永久标记或所有顶点都访问完时终止。
. Relax: B via C yields 2+1=3 < 4, update B=3; D via C yields 2+3=5, update D=5. Next smallest unvisited is B (3). Relax D via B: 3+5=8 >5, no change. Finally D (5). Shortest paths: A→B=3, A→D=5.
例如，一个包含顶点 A, B, C, D 的图，边权为 AB=4, AC=2, BC=1, BD=5, CD=3。从 A 出发，距离：A=0, B=4, C=2, D=∞。选 C(2)。松弛：经 C 到 B 得 2+1=3 < 4，更新 B=3；经 C 到 D 得 2+3=5，更新 D=5。下一个最小的未访问顶点是 B(3)。经 B 松弛 D：3+5=8 >5，不变。最后选 D(5)。最短路径：A→B=3，A→D=5。
5. Minimum Spanning Tree: Prim and Kruskal | 最小生成树：普里姆与克鲁斯卡尔算法
A minimum spanning tree (MST) connects all vertices in a connected, undirected, weighted graph with the smallest possible total edge weight. Two classic algorithms are Prim's and Kruskal's, both greedy but differing in approach.
最小生成树（MST）以尽可能小的总边权连接连通无向加权图中的所有顶点。两种经典算法是普里姆算法和克鲁斯卡尔算法，都是贪心算法但方法不同。
Prim's algorithm starts at an arbitrary vertex and grows the tree one edge at a time. At each step, it selects the cheapest edge that connects a vertex already in the tree to a vertex outside the tree. This requires tracking the nearest distance from tree to outside vertices, making it efficient for dense graphs.
普里姆算法 从任意顶点开始，每次添加一条边扩展树。每一步，选择一条连接树内顶点和树外顶点且权重最小的边。这需要跟踪树外顶点到树的最短距离，适用于稠密图。
Kruskal's algorithm sorts all edges by weight in ascending order and then considers them one by one. An edge is added to the MST if it does not form a cycle with already selected edges. Cycle checking is done by tracking connected components. Kruskal's is often easier to apply manually for sparse graphs.
克鲁斯卡尔算法 将所有边按权重升序排列，然后逐一考察。如果一条边与已选边不构成环，则将其加入 MST。通过跟踪连通分量来检查是否成环。克鲁斯卡尔算法对稀疏图手工操作常常更简单。
IB questions may ask you to list the edges in the order they are added for a given graph, compare the two algorithms, or identify the total weight of the MST. Make sure to draw a clear diagram when tracing Kruskal's to avoid accidental cycles. For Prim's, you can use a table or a graphic approach; either way, justify the order by showing the candidates at each step.
IB 考题可能要求按顺序列出给定图中添加的边、比较两种算法，或找出 MST 的总权重。在追踪克鲁斯卡尔算法时一定要画出清晰的图，避免无意中形成环路。对于普里姆算法，可以使用表格或图示方法；无论哪种，都要通过展示每步的候选边来说明顺序。
6. Critical Path Analysis | 关键路径分析
Critical path analysis (CPA) is a project management technique that models activities as a directed network (activity-on-node or activity-on-arrow). Each activity has a duration and possibly predecessors. The earliest start time (EST) and earliest finish time (EFT) are calculated by a forward pass from the start node. The latest start time (LST) and latest finish time (LFT) come from a backward pass from the end node. The total float of an activity is LST − EST (or LFT − EFT). Activities with zero total float lie on the critical path. Any delay in a critical activity delays the entire project.
关键路径分析（CPA）是一种项目管理技术，将活动建模为有向网络（节点表示活动或箭线表示活动）。每个活动有持续时间和可能的前驱活动。通过从起始节点正推计算最早开始时间 (EST) 和最早完成时间 (EFT)。通过从结束节点逆推计算最晚开始时间 (LST) 和最晚完成时间 (LFT)。活动的总时差为 LST − EST（或 LFT − EFT）。总时差为零的活动位于关键路径上。关键活动的任何延迟都会延迟整个项目。
Standard IB questions provide an activity table with dependencies and durations. You may be asked to draw the network, complete the forward and backward passes, find the minimum project completion time, and list the critical path. A common mistake is misreading dependencies, so always draw an accurate precedence diagram first. The minimum completion time is the EFT of the finish activity, often called "project duration".
标准的 IB 考题会提供一张包含依赖关系和持续时间的活动表。可能要求画出网络图、完成正推和逆推计算、找出最短项目完成时间，并列出关键路径。一个常见错误是误读依赖关系，因此首先要画出准确的前驱图。最短完成时间就是结束活动的 EFT，通常称为“项目工期”。
7. Sorting Algorithms: Bubble Sort and Quicksort | 排序算法：冒泡排序与快速排序
Sorting algorithms arrange a list of values into a specified order. Two commonly taught methods in IB are bubble sort and quicksort, each illustrating different algorithmic paradigms.
排序算法将一列数值按指定顺序排列。IB 课程中常教的两种方法是冒泡排序和快速排序，它们分别展示了不同的算法范式。
Bubble sort repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element "bubbles" to its correct position. The algorithm terminates when a complete pass occurs without any swaps. Its worst-case and average time complexity is O(n²), making it inefficient for large lists, but it is simple to understand and implement.
冒泡排序 反复遍历列表，比较相邻元素，若顺序错误则交换。每完成一趟完整的遍历，最大的未排序元素“冒泡”到其正确位置。当某趟遍历没有发生任何交换时算法终止。最坏和平均时间复杂度为 O(n²)，对于大列表效率较低，但易于理解和实现。
Quicksort is a divide-and-conquer algorithm. It picks a pivot element from the list and partitions the remaining elements into two sublists: those less than the pivot and those greater than the pivot. The sublists are then recursively sorted. The in-place version uses pointer movements to avoid extra storage. Average time complexity is O(n log n), but worst-case (e.g., already sorted list with poor pivot choice) is O(n²). IB questions may ask you to perform one pass of quicksort or describe the partitioning process.
快速排序 是分治算法。它从列表中选择一个枢轴元素，将其余元素划分为两个子列表：小于枢轴的和大于枢轴的，然后递归排序子列表。原地版本通过移动指针避免额外存储。平均时间复杂度为 O(n log n)，但最坏情况（例如已排序列表且枢轴选择不佳）为 O(n²)。IB 试题可能要求执行一趟快速排序或描述划分过程。
8. Binary Search | 二分查找
Binary search locates a target value within a sorted array by repeatedly dividing the search interval in half. Compare the target with the middle element; if they are not equal, eliminate the half in which the target cannot lie and repeat on the remaining half. The algorithm terminates when the target is found or the interval is empty. Because the search space is halved each time, the time complexity is O(log n), vastly more efficient than linear search for large datasets.
二分查找通过在已排序数组中反复将查找区间减半来定位目标值。将目标值与中间元素比较；若不相等，则排除不可能包含目标的那一半，并继续在另一半上查找。当找到目标或区间为空时算法终止。由于每次将查找空间减半，时间复杂度为 O(log n)，对于大数据集远比线性查找高效。
IB Mathematical Studies and AI courses include binary search as an example of an efficient algorithm. Questions may involve tracing through a list, stating the number of comparisons needed, or writing pseudocode for the iterative or recursive version. Always ensure the list is sorted before applying binary search.
IB 数学研究及 AI 课程将二分查找作为一种高效算法的例子。考题可能涉及在列表中跟踪查找过程、说明所需比较次数，或为迭代或递归版本编写伪代码。务必确保列表已排序再应用二分查找。
9. Algorithm Complexity and Big O Notation | 算法复杂度与 Big O 记号
The efficiency of an algorithm is measured by how its time or space requirements grow with input size n. Big O notation expresses the upper bound of this growth, ignoring constants and lower-order terms. Common complexities include:
算法的效率通过其时间或空间需求随输入规模 n 的增长方式来衡量。Big O 记号表示这种增长的上界，忽略常数和低阶项。常见复杂度包括：
- O(1) – constant time (accessing an array element)
- O(log n) – logarithmic (binary search)
- O(n) – linear (simple loop through a list)
- O(n log n) – linearithmic (efficient sorting like quicksort, merge sort)
- O(n²) – quadratic (bubble sort, simple nested loops)
- O(2ⁿ) – exponential (some recursive solutions to combinatorial problems)
- O(1) – 常量时间（访问数组元素）
- O(log n) – 对数时间（二分查找）
- O(n) – 线性时间（遍历列表的简单循环）
- O(n log n) – 线性对数时间（快速排序、归并排序等高效排序）
- O(n²) – 二次时间（冒泡排序、简单嵌套循环）
- O(2ⁿ) – 指数时间（某些组合问题的递归解法）
IB questions might give you a pseudocode of a routine and ask you to determine its Big O complexity based on nested loops or recursion, or to compare algorithms and justify which is more scalable. When analysing code, count the number of elementary operations as a function of n and find the dominant term.
IB 试题可能给出一个例程的伪代码，要求根据嵌套循环或递归确定其 Big O 复杂度，或者比较算法并论证哪个扩展性更好。分析代码时，可将基本操作数表示为 n 的函数并找出主导项。
10. Common Exam Techniques and Pitfalls | 考试技巧与常见错误
Success in algorithm questions relies on careful step-by-step execution and clear presentation. Here are some exam-tested strategies:
要想在算法题中取得好成绩，关键在于逐步执行、清晰呈现。以下是一些经过考试检验的策略：
- Show full working for iterations: For Newton-Raphson or Euler's method, write the substituted formula before evaluating each approximation. This earns method marks even if a later arithmetic slip occurs. 迭代过程展示完整步骤： 对于牛顿-拉夫森法或欧拉法，在计算每个近似值前写出代入公式。这样即使后续出现算术错误，也能得到方法分。
- Check conditions: Before applying Dijkstra, verify all edge weights are non‑negative. For binary search, confirm the list is sorted. 检查条件： 在应用迪杰斯特拉算法前，验证所有边权非负。对于二分查找，确认列表已排序。
- Use tables for graph algorithms: A well-organised distance table for Dijkstra or a forward‑pass table for CPA helps avoid omission and makes your reasoning easy to follow. 图算法使用表格： 迪杰斯特拉算法的距离表或 CPA 的正推表格组织良好，有助于避免遗漏，并使推理过程易于追踪。
- Beware of premature rounding: Round only at the final step or as instructed; intermediate values should retain extra precision to prevent error propagation. 注意不要过早舍入： 只在最后一步或按照要求舍入；中间值应保留额外精度，以防误差传播。
- Trace algorithms with small examples: Even if the question doesn't ask, mentally test an algorithm on a tiny dataset to reinforce understanding. 用小例子跟踪算法： 即使题目未要求，也可以在脑中用小数据集测试算法以加深理解。
- Link complexity to problem size: When justifying algorithm choice, reference Big O notation and expected input size. 将复杂度与问题规模挂钩： 当论证算法选择时，引用 Big O 记号和预期输入规模。
By mastering these core algorithms and being meticulous in their application, you will be well-prepared for the algorithmic reasoning required in IB Mathematics examinations.
通过掌握这些核心算法并在应用中做到一丝不苟，你将为 IB 数学考试所需的算法推理做好充分准备。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图