📚 Algorithm for A-Level AQA Maths: Key Points | A-Level AQA 数学：算法考点精讲
Algorithms form a fundamental part of AQA Decision Mathematics, providing systematic methods to solve problems from sorting data to optimizing resource allocation. Mastering algorithm tracing and understanding their efficiency is essential for the exam.
算法是 AQA 决策数学的基础部分，提供解决排序数据和优化资源分配等问题的系统方法。掌握算法追踪并理解其效率对考试至关重要。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous instructions to solve a problem or perform a computation. Each step must be precise and executable, leading to a required output after a finite number of steps. An algorithm must always terminate.
算法是一组有限、定义明确且无歧义的指令序列，用于解决问题或执行计算。每个步骤必须精确且可执行，在有限步骤后产生所需输出。算法必须总能终止。
Algorithms can be expressed in various forms including structured English, flowcharts, or pseudocode. In AQA Decision Maths, you will encounter algorithms for sorting, searching, and packing, and you need to be able to trace and interpret them precisely.
算法可以用多种形式表达，包括结构化英语、流程图或伪代码。在 AQA 决策数学中，你将遇到排序、搜索和装箱等算法，并需要能够准确地追踪和解读它们。
2. Flowcharts and Pseudocode | 流程图与伪代码
A flowchart visually represents an algorithm using standard symbols: rounded boxes (or ovals) for start/end, parallelograms for input/output, rectangles for processes, and diamonds for decisions. Arrow lines show the flow of control.
流程图使用标准符号直观地表示算法：圆角矩形（或椭圆形）表示开始/结束，平行四边形表示输入/输出，矩形表示处理步骤，菱形表示判断。箭头线表示控制流。
Pseudocode is a textual description resembling a simplified programming language. Keywords like INPUT, OUTPUT, IF…THEN…ELSE, FOR…NEXT, WHILE…ENDWHILE are used. It allows clear, step-by-step expression without strict syntax, making it ideal for exam questions.
伪代码是一种类似简化编程语言的文本描述。使用 INPUT、OUTPUT、IF…THEN…ELSE、FOR…NEXT、WHILE…ENDWHILE 等关键字。它允许清晰、逐步的表达而不要求严格语法，是考试题目中的理想形式。
3. Tracing Algorithms | 算法追踪
Tracing an algorithm involves systematically recording the values of variables at each step in a trace table. This helps verify correctness, find logic errors, and understand how the output is produced.
追踪算法涉及在一个追踪表中系统地记录每一步变量的值。这有助于验证正确性、发现逻辑错误并理解输出是如何产生的。
When tracing, carefully follow each instruction, update the table after every variable change, and note any conditional branches taken. A complete trace is often required to show the final state of all variables.
追踪时，仔细遵循每条指令，在每次变量变化后更新表格，并记录所采取的任何条件分支。通常需要一个完整的追踪来展示所有变量的最终状态。
4. Euclidean Algorithm | 欧几里得算法
The Euclidean Algorithm efficiently finds the greatest common divisor (GCD) of two positive integers. It repeatedly writes the larger number as a multiple of the smaller plus a remainder: a = bq + r, then replaces a with b and b with r until r = 0. The last non-zero remainder is the GCD.
欧几里得算法高效地求两个正整数的最大公约数（GCD）。它反复将较大数写成较小数的倍数加余数：a = bq + r，然后用 b 替换 a，用 r 替换 b，直到 r = 0。最后一个非零余数即为 GCD。
GCD(a, b) = GCD(b, a mod b)
For example, to find GCD(252, 105): 252 = 105×2 + 42; 105 = 42×2 + 21; 42 = 21×2 + 0, so GCD = 21. This algorithm is a must-know for AQA Decision Maths.
例如，求 GCD(252, 105)：252 = 105×2 + 42；105 = 42×2 + 21；42 = 21×2 + 0，因此 GCD = 21。该算法是 AQA 决策数学必考内容。
5. Bubble Sort | 冒泡排序
Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. Each full traversal is called a pass, and after each pass the next largest element ‘bubbles’ to its correct position at the end.
冒泡排序是一种简单的排序算法，反复遍历列表，比较相邻元素，若顺序错误则交换它们。每次完整遍历称为一趟，每趟之后下一个最大元素会“冒泡”到列表末尾的正确位置。
1. Start from the left and compare the first two items. If the left item is greater than the right (for ascending order), swap them.
1. 从最左侧开始，比较前两个项目。如果左侧项目大于右侧项目（对于升序排列），交换它们。
2. Move to the next pair (items 2 and 3), compare and swap if needed. Continue until the end of the list is reached; this finishes one pass. After a pass, the last element is sorted and need not be checked again.
2. 移至下一对（第 2 和第 3 项），比较并根据需要交换。继续直到列表末尾，这完成一趟。一趟之后，最后一个元素已排序，无需再检查。
3. Repeat the process for the unsorted portion of the list. If a complete pass is made with no swaps, the algorithm can terminate early.
3. 对列表未排序部分重复此过程。如果某一趟中没有发生任何交换，算法可提前终止。
The maximum number of comparisons is n(n-1)/2 for a list of length n, giving a time complexity of O(n²).
长度为 n 的列表最多需要比较 n(n-1)/2 次，时间复杂度为 O(n²)。
6. Shuttle Sort | 穿梭排序
Shuttle Sort, also known as a variant of insertion sort, builds a sorted sublist by shuttling each new element leftwards through adjacent swaps until it is in the correct position relative to the already sorted part.
穿梭排序，也称为插入排序的一种变体，通过将每个新元素向左穿梭，进行相邻交换，直到它相对于已排序部分处于正确位置，从而构建有序子列表。
1. The first element is initially considered sorted. Take the next element (starting from position 2) and compare it with the element to its left. If it is smaller (for ascending), swap them and continue comparing leftwards.
1. 初始将第一个元素视为已排序。取下一个元素（从位置 2 开始），将其与左边的元素比较。如果较小（升序），交换它们并继续向左比较。
2. Continue shuttling the element left until it reaches a position where the element to its left is not larger, or it becomes the first item. This places the element in its correct place in the sorted sublist.
2. 持续向左穿梭该元素，直到它到达左边元素不大于它的位置，或者它成为第一项。这样就将该元素放入有序子列表的正确位置。
3. Return to the original position from which the element was taken and move one step right to the next unsorted element. Repeat the shuttle process until all elements are sorted.
3. 回到原位置，向右移动一步到下一个未排序元素。重复穿梭过程，直到所有元素排序完毕。
Shuttle Sort performs fewer comparisons than Bubble Sort on average but still has a worst-case complexity of O(n²).
穿梭排序平均比较次数少于冒泡排序，但最坏时间复杂度仍为 O(n²)。
7. Quick Sort | 快速排序
Quick Sort is a recursive divide-and-conquer algorithm. It selects a pivot element from the list and partitions the remaining elements into two sublists: those less than or equal to the pivot, and those greater than the pivot. These sublists are then sorted recursively.
快速排序是一种递归的分治算法。它从列表中选择一个枢轴元素，将剩余元素划分为两个子列表：小于等于枢轴的元素和大于枢轴的元素。然后递归地对这些子列表排序。
1. Choose a pivot (often the first element or the middle element as per exam specification). Create two empty lists: ‘left’ and ‘right’.
1. 选择一个枢轴（通常根据考试要求选择第一个元素或中间元素）。创建两个空列表：“左”和“右”。
2. Go through all other elements; if an element is less than or equal to the pivot, place it in the left list; if greater, place it in the right list. This partitions the data.
2. 遍历所有其他元素；如果元素小于等于枢轴，放入左列表；如果大于，放入右列表。这样就完成了分区。
3. Recursively apply Quick Sort to the left list and to the right list. Combine the sorted left list, the pivot, and the sorted right list to produce the final sorted list.
3. 递归地对左列表和右列表应用快速排序。将排序后的左列表、枢轴和排序后的右列表合并，得到最终有序列表。
Quick Sort is very efficient on average with a complexity of O(n log n), but the worst-case (e.g. already sorted data with first-element pivot) can degrade to O(n²).
快速排序平均效率很高，复杂度为 O(n log n)，但最坏情况（例如已排序数据且使用首元素作为枢轴）可能退化到 O(n²)。
8. Binary Search | 二分搜索
Binary search finds a target value within an already sorted list by repeatedly dividing the search interval in half. It compares the target to the middle element and discards the half where the target cannot lie.
二分搜索通过在已排序的列表中反复将搜索区间减半，来查找目标值。它将目标与中间元素比较，并丢弃目标不可能存在的那一半。
1. Set low = 1, high = length of list. While low ≤ high, compute mid = (low+high) div 2 (integer division). Compare the target with the item at position mid.
1. 设定 low = 1，high = 列表长度。当 low ≤ high 时，计算 mid = (low+high) div 2（整数除法）。将目标与位置 mid 处的项比较。
2. If target = item(mid), the search is successful and the algorithm stops. If target < item(mid), set high = mid - 1 (discard upper half). If target > item(mid), set low = mid + 1 (discard lower half). Repeat.
2. 若目标 = item(mid)，搜索成功，算法停止。若目标 < item(mid)，设定 high = mid - 1（丢弃上半部分）。若目标 > item(mid)，设定 low = mid + 1（丢弃下半部分）。重复。
3. If low becomes greater than high, the target is not in the list. The algorithm terminates with a ‘not found’ result.
3. 如果 low 大于 high，目标不在列表中。算法终止，结果为“未找到”。
Binary search halves the search space each iteration, giving a time complexity of O(log n). It is far more efficient than linear search for large datasets.
二分搜索每次迭代将搜索空间减半，时间复杂度为 O(log n)。对于大数据集，它远比线性搜索高效。
9. Bin Packing Algorithms | 装箱算法
Bin packing addresses the problem of fitting items of given sizes into bins of fixed capacity, aiming to minimise the number of bins used. Three heuristics are examined in AQA Decision Maths: first-fit, first-fit decreasing, and full-bin packing.
装箱问题处理将给定大小的物品装入固定容量的箱子中，旨在最小化所用箱子的数量。AQA 决策数学考查三种启发式算法：首次适应、首次适应递减和满箱装箱。
First-fit: Take items in the order given. Place each item into the first bin that has enough remaining capacity. Only open a new bin if the item does not fit any existing bins.
首次适应：按给定顺序处理物品。将每个物品放入第一个剩余容量足够的箱子中。仅当物品不适合任何已有箱子时才开启新箱子。
First-fit decreasing: First sort all items into descending order of size. Then apply the first-fit algorithm. This often produces a better (lower) number of bins.
首次适应递减：首先将所有物品按大小降序排列。然后应用首次适应算法。这通常能产生更好的（更少的）箱子数。
Full-bin packing: Inspect items to find combinations that exactly fill a bin (or fill it as much as possible). Remove those items and repeat. Remaining items are packed by first-fit or another method. This can be combined with first-fit strategies.
满箱装箱：检查物品，找出恰好装满一个箱子（或尽可能装满）的组合。移除这些物品并重复。剩余物品用首次适应或其他方法装箱。这可以与首次适应策略结合使用。
These algorithms are heuristic and do not guarantee an optimal solution, but they are fast and often effective in practice. Exam questions may ask you to apply them to a list and compare the number of bins used.
这些算法是启发式的，不保证最优解，但在实践中快速且通常有效。考题可能会要求你对列表应用这些算法并比较所用箱子的数量。
10. Efficiency and Order of Algorithms | 算法的效率与阶
The efficiency of an algorithm is measured by how its run time or number of key operations grows with the input size n. This is expressed using Big-O notation, which describes the upper bound of the growth rate.
算法的效率通过其运行时间或关键操作次数如何随输入规模 n 增长来衡量。这用大 O 记号表示，描述增长速率的上界。
Common orders from most to least efficient: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) log-linear, O(n²) quadratic, O(2ⁿ) exponential. In AQA Decision Maths, you must identify the order of standard algorithms.
常见阶从高到低：O(1) 常数阶，O(log n) 对数阶，O(n) 线性阶，O(n log n) 线性对数阶，O(n²) 平方阶，O(2ⁿ) 指数阶。在 AQA 决策数学中，你必须识别标准算法的阶。
Bubble Sort and Shuttle Sort require up to n(n-1)/2 comparisons, so they are O(n²). Quick Sort typically performs around n log n comparisons on random data, hence is O(n log n) on average, though worst-case is O(n²). Binary Search halves the list each time, yielding O(log n).
冒泡排序和穿梭排序最多需要 n(n-1)/2 次比较，因此是 O(n²)。快速排序在随机数据上通常执行约 n log n 次比较，因此平均为 O(n log n)，但最坏情况为 O(n²)。二分搜索每次将列表减半，得到 O(log n)。
Understanding the order helps you choose the most suitable algorithm for a given situation and is a key part of the algorithm section in the exam.
理解阶有助于你为给定情况选择最合适的算法，也是考试中算法部分的关键组成部分。
Published by TutorHao | AQA Decision Maths Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply