📚 AS Mathematics: Algorithms Key Points | AS 数学：算法 考点精讲
Algorithms form the backbone of decision mathematics, providing systematic methods for solving problems ranging from sorting data to packing boxes. In AS-level exams, you are expected to understand, trace, and compare algorithms using flowcharts, pseudocode, and trace tables. This article distils the essential concepts and typical exam questions to help you master this topic.
算法是决策数学的骨架，为从数据排序到装箱等问题提供了系统化的解决步骤。在 AS 阶段考试中，你需要理解、追踪并比较算法，能够使用流程图、伪代码和追踪表格来展示过程。本文将提炼核心概念与常见考题，帮你扎实掌握这一主题。
1. What Is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of step-by-step instructions designed to solve a specific problem. It must be unambiguous, terminating after a finite number of steps, and produce a correct output for any valid input. In AS mathematics, algorithms are usually applied to sorting numbers, searching lists, or packing items of given sizes into bins.
算法是一组有限的、为求解特定问题而设计的分步指令。它必须清晰无歧义，在有限步后终止，并对任意有效输入都能产生正确输出。在 AS 数学中，算法通常用于对数字排序、搜索列表，或将给定尺寸的物品装入箱子中。
2. Expressing Algorithms: Flowcharts and Pseudocode | 算法的表达：流程图与伪代码
Flowcharts use standard symbols: an oval for 'Start/End', a rectangle for a process or instruction, a diamond for a decision (yes/no), and arrows to show the flow. Pseudocode is a text-based representation using keywords like INPUT, OUTPUT, IF...THEN...ELSE, FOR...NEXT, WHILE...ENDWHILE. Both forms appear on exam papers, and you may be asked to convert between them or to dry-run a given algorithm.
流程图使用标准符号：椭圆形表示“开始/结束”，矩形表示处理或指令，菱形表示判断（是/否），箭头表示流程方向。伪代码是基于文本的表示，使用诸如 INPUT, OUTPUT, IF...THEN...ELSE, FOR...NEXT, WHILE...ENDWHILE 等关键词。两种形式都可能出现在试卷中，你可能需要互相转换，或对给定算法进行人工执行。
3. Linear Search Algorithm | 线性搜索算法
A linear search checks every element of an unordered list one by one until the target item is found or the end of the list is reached. It is simple but inefficient for large lists. The maximum number of comparisons is equal to the length of the list, n. In pseudocode, a linear search looks for item T in list L[1...n]:
线性搜索逐个检查无序列表中的每个元素，直到找到目标项或到达列表末尾。它原理简单，但对于大型列表效率很低。最大比较次数等于列表长度 n。在伪代码中，在线性搜索查找列表 L[1...n] 中的项 T 可表示为：
FOR i = 1 TO n
IF L[i] = T THEN OUTPUT i; STOP
NEXT i
OUTPUT 'Not found'
4. Binary Search Algorithm | 二分搜索算法
Binary search works on a sorted list by repeatedly comparing the target with the middle element and discarding the half where the target cannot lie. It halves the search space each time, giving logarithmic time complexity. To locate value T in a sorted list of length n, the maximum number of comparisons is approximately log₂(n). Remember to show each step clearly, updating the lower and upper bounds.
二分搜索用于已排序的列表，它重复将目标与中间元素比较，并舍弃不可能包含目标的那一半。每次都将搜索空间减半，因此具有对数时间复杂度。在长度为 n 的已排序列表中查找 T，最大比较次数约为 log₂(n)。务必清晰地展示每一步，更新下界和上界。
Let low ← 1, high ← n
WHILE low ≤ high
mid ← (low + high) DIV 2
IF L[mid] = T THEN OUTPUT mid; STOP
IF T < L[mid] THEN high ← mid − 1
ELSE low ← mid + 1
ENDWHILE
OUTPUT 'Not found'
5. Bubble Sort Algorithm | 冒泡排序算法
Bubble sort repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. The pass continues until no swaps are needed. After each pass, the largest unsorted element 'bubbles' to its correct position. The maximum number of passes for a list of length n is n−1, with the total number of comparisons approximately ½n(n−1).
冒泡排序反复遍历列表，比较相邻项，若顺序错误则交换它们。每一趟遍历持续进行，直到不再需要交换。每趟之后，最大的无序元素会“冒泡”到正确位置。对于长度为 n 的列表，最大趟数为 n−1，总比较次数约为 ½n(n−1)。
FOR i = 1 TO n−1
FOR j = 1 TO n−i
IF L[j] > L[j+1] THEN SWAP L[j] and L[j+1]
NEXT j
NEXT i
6. Quick Sort Algorithm | 快速排序算法
Quick sort picks a pivot (often the first item) and partitions the remaining items into two sublists: those less than the pivot and those greater than the pivot. These sublists are then sorted recursively using the same process. The algorithm ends when all sublists contain one or zero items. Quicksort is generally faster than bubble sort for large lists, but you must be able to trace the partitioning steps accurately.
快速排序选取一个枢轴（通常是第一个项），将剩余项划分为两个子列表：小于枢轴的项和大于枢轴的项。然后对这些子列表递归地使用相同的过程。当所有子列表包含一个或零个项时算法结束。对于大型列表，快速排序通常比冒泡排序更快，但你必须能够准确地追踪划分步骤。
If the list has at most one element, stop.
Else select pivot p = L[1].
Partition L[2...n] into Left (items ≤ p) and Right (items > p).
Recursively apply quicksort to Left and Right.
Combine: quicksort(Left) + [p] + quicksort(Right).
7. Algorithm Efficiency and Comparison | 算法效率与比较
Efficiency is measured by counting the number of fundamental operations (comparisons, swaps) as a function of input size n. Bubble sort performs O(n²) comparisons in the worst case, while quicksort averages O(n log n). Binary search uses O(log n) comparisons, whereas linear search needs O(n). Exam questions often ask you to state the maximum number of comparisons for given values of n.
效率通过计算基本操作（比较、交换）次数来度量，它是输入规模 n 的函数。冒泡排序最坏情况下进行 O(n²) 次比较，而快速排序平均为 O(n log n)。二分搜索使用 O(log n) 次比较，而线性搜索需要 O(n) 次。考题常要求你针对给定的 n 值陈述最大比较次数。
| Algorithm | Best case | Worst case |
|---|---|---|
| Linear search | 1 comparison | n comparisons |
| Binary search | 1 comparison | ⌊log₂ n⌋ + 1 comparisons |
| Bubble sort | n−1 comparisons (already sorted) | ½n(n−1) comparisons |
| Quicksort | n log₂ n comparisons | ½n(n−1) comparisons |
8. Bin-Packing Algorithms: First-Fit and First-Fit Decreasing | 装箱算法：首次适应与首次适应递减
Bin packing aims to pack items of given sizes into bins of fixed capacity using the fewest bins. The first-fit algorithm places each item into the earliest bin that has enough room. If no existing bin can accommodate it, a new bin is opened. The first-fit decreasing algorithm sorts items into descending order of size before applying first-fit, often yielding a better packing.
装箱问题旨在将给定尺寸的物品放入固定容量的箱子中，使用最少的箱子。首次适应算法将每个物品放入第一个有足够空间的箱子中。如果没有现有箱子可以容纳，则开启一个新箱子。首次适应递减算法先将物品按尺寸降序排列，再应用首次适应，通常能得到更好的装箱方案。
ecreasing sorts to 8,5,4,4,3,2; bins: [8,2], [5,4], [4,3] same here, but often FFD uses fewer bins. Be prepared to show the list after each placement.
示例：箱子容量 = 10，物品 8, 5, 4, 4, 3, 2。首次适应得到箱子：[8,2], [5,4], [4,3] → 3 个箱子。首次适应递减排序后为 8,5,4,4,3,2；箱子：[8,2], [5,4], [4,3] 此处相同，但 FFD 通常使用更少的箱子。要准备好展示每次放置后的列表状态。
9. Trace Tables in Algorithm Execution | 算法执行中的追踪表格
A trace table is used to follow the values of variables as each step of an algorithm is executed. It is a crucial exam skill: you list variables as columns and fill in rows after each line of the algorithm. This method helps verify correctness and is commonly required when dry-running a pseudocode routine. Always update variables in the order the algorithm processes them.
追踪表格用于跟踪算法每一步执行时变量的值。这是一项关键的应试技能：将变量列为列，在算法的每一行后填入行。该方法有助于验证算法的正确性，并且在人工执行伪代码时经常被要求。务必按照算法处理变量的顺序更新它们。
For example, tracing a swap in bubble sort with L = [5, 3]:
例如，追踪冒泡排序中的交换，L = [5, 3]：
| Line | i | j | L[j] | L[j+1] | L |
|---|---|---|---|---|---|
| start | – | – | – | – | [5,3] |
| i=1, j=1 | 1 | 1 | 5 | 3 | [5,3] |
| swap | 1 | 1 | – | – | [3,5] |
10. Common Mistakes and Exam Tips | 常见错误与考试技巧
Many students forget to re-sort sublists independently in quicksort, or they misplace the pivot when combining. In bubble sort, ensure you label each pass and stop early if no swaps occur. For binary search, always round down the midpoint and update bounds correctly. Show all working: trace tables, clearly marked sublists, and final outputs. Time management is key—practice tracing under timed conditions.
许多学生在快速排序中忘记对子列表独立重新排序，或在合并时错误放置枢轴。冒泡排序中，确保标注每一趟，若未发生交换则提前停止。二分搜索始终向下取整中点，并正确更新边界。展示全部解题过程：追踪表格、清晰标注的子列表以及最终输出。时间管理是关键——在计时条件下练习追踪。
In bin packing, always note the order of items and the bin list after each placement. If the question asks for a specific algorithm (e.g., first-fit), do not change to decreasing unless instructed. Finally, double-check that your flowchart or pseudocode exactly matches the given logic before attempting to trace.
在装箱问题中，每次放置后都要记录物品顺序和箱子列表。如果题目指定某个算法（如首次适应），除非要求，否则不要改为递减方式。最后，在开始追踪之前，再次确认你的流程图或伪代码与给定的逻辑完全吻合。
Published by TutorHao | AS Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图