📚 Algorithms in IB CCEA Computer Science | IB CCEA 计算机：算法考点精讲
Algorithms form the backbone of computer science. In the IB and CCEA curricula, a strong grasp of algorithmic thinking—from designing simple sequences to analysing complex search and sort routines—is essential. This revision guide covers every major topic: algorithm representation, control structures, standard algorithms, recursion, efficiency, and common exam-style pitfalls. Each explanation is paired in English and Chinese, helping bilingual learners solidify both terminology and conceptual understanding.
算法是计算机科学的基石。在 IB 与 CCEA 课程体系中，牢固掌握算法思维——从设计简单的顺序结构到分析复杂的搜索与排序例程——都至关重要。本复习指南涵盖所有主要专题：算法的表示、控制结构、标准算法、递归、效率以及常见考试易错点。每段讲解均以英文和中文配对呈现，帮助双语学习者同时巩固术语和概念理解。
1. What is an Algorithm? | 什么是算法？
An algorithm is a step-by-step procedure or a finite set of well-defined instructions for solving a problem or completing a task. It must be unambiguous, have a clear stopping point, and produce the correct output for any valid input.
算法是解决问题的分步过程或一组有限的、定义明确的指令。它必须明确无歧义、有清晰的终止点，并且对任何有效输入都能产生正确输出。
Key properties of a good algorithm include finiteness (it always terminates), definiteness (each step is precisely stated), input (zero or more values), output (at least one result), and effectiveness (every operation is basic enough to be carried out in finite time).
优良算法的关键属性包括有穷性（总会终止）、确定性（每一步精确陈述）、输入（零个或多个值）、输出（至少一个结果）和可行性（每个操作都足够基本，可在有限时间内完成）。
For example, a recipe is an everyday algorithm: combine flour, sugar, and eggs, then bake at 180 °C for 30 minutes. In computing, a sorting routine or a pathfinding process is an algorithm.
例如，食谱就是日常生活中的算法：混合面粉、糖和鸡蛋，然后在 180 °C 下烘烤 30 分钟。在计算领域，排序例程或路径探寻过程就是算法。
2. Representing Algorithms | 算法的表示方法
Algorithms can be expressed in various forms. The three most common examined representations are structured English, flowcharts, and pseudocode. Each has its strengths: written descriptions are flexible, flowcharts are visual, and pseudocode bridges human language with programming syntax.
算法可以用多种形式表达。考试中最常见的三种表示法是结构化英语、流程图和伪代码。每种都有其优点：文字描述灵活，流程图直观，伪代码则在人类语言和编程语法之间架起桥梁。
A flowchart uses standard symbols: oval for start/end, parallelogram for input/output, rectangle for process, diamond for decision, and arrows to show the flow of control. Flowcharts are especially useful for illustrating selection and iteration visually.
流程图使用标准符号：椭圆形表示开始/结束，平行四边形表示输入/输出，矩形表示处理步骤，菱形表示判断，箭头表示控制流。流程图特别适合直观展示选择与循环结构。
Pseudocode is a simplified, half-English, half-code notation that omits strict syntax details. Typical constructs include IF…THEN…ELSE…ENDIF, WHILE…DO…ENDWHILE, FOR…TO…NEXT, and OUTPUT. IB/CCEA examiners expect students to write clear, indented pseudocode that mirrors logical structure without worrying about semicolons or specific language rules.
伪代码是一种简化的、半英语半代码的记法，省略了严格的语法细节。典型结构包括 IF…THEN…ELSE…ENDIF、WHILE…DO…ENDWHILE、FOR…TO…NEXT 和 OUTPUT。IB/CCEA 阅卷人期望学生写出清晰、缩进恰当的伪代码，反映逻辑结构，而不必担心分号或特定语言规则。
3. Basic Control Structures | 基本控制结构
Every algorithm is built from three fundamental constructs: sequence, selection, and iteration. Sequence means executing instructions one after another in order. Selection makes decisions using conditions, typically with IF, ELSE, or SWITCH statements. Iteration repeats a block of code while a condition holds true or for a set number of times.
所有算法都由三种基本结构构建：顺序、选择和循环。顺序意味着按照先后次序执行指令。选择使用条件进行判断，通常通过 IF、ELSE 或 SWITCH 语句实现。循环则在条件为真或执行设定次数的情况下重复执行一段代码。
- Sequence: step A → step B → step C.
- 顺序：步骤 A → 步骤 B → 步骤 C。
- Selection: IF score >= 50 THEN grade = ‘Pass’ ELSE grade = ‘Fail’.
- 选择：IF score >= 50 THEN grade = ‘Pass’ ELSE grade = ‘Fail’。
- Iteration: WHILE temperature < 100 DO heat water or FOR i = 1 TO 10 DO OUTPUT i.
- 循环：WHILE temperature < 100 DO heat water 或 FOR i = 1 TO 10 DO OUTPUT i。
Examiners frequently ask students to trace pseudocode containing nested loops and conditional branches. Mastering the dry-run technique—manually stepping through with a trace table that records variable values at each stage—is vital for avoiding logic errors.
考官经常要求学生追踪包含嵌套循环和条件分支的伪代码。掌握手工逐行执行的技术——使用记录每一步变量值的追踪表——对于避免逻辑错误至关重要。
4. Standard Algorithms: Sum, Count, Min, Max, Average | 标准算法：求和、计数、最小值、最大值、平均值
Many exam questions build upon five elementary accumulator-based algorithms. These are so fundamental that they are often integrated into larger problems without being explicitly identified.
许多考题都建立在五个基于累加器的基本算法之上。它们非常基础，常常被整合进更大的问题中而不被单独指出。
Sum: initialise total ← 0; for each value, add it to total. Count: initialise count ← 0; increment count for each item meeting a condition. Maximum: set max ← first item; compare each subsequent item and update if larger. Minimum: analogous to max, but update if smaller. Average: compute sum and count, then divide sum by count, being careful to avoid division by zero.
求和：初始化 total ← 0；对每个值，将其累加到 total。计数：初始化 count ← 0；对每个符合条件的项，递增 count。最大值：设 max ← 第一项；依次比较后续每一项，若更大则更新。最小值：与最大值类似，但更小时更新。平均值：先计算总和与数量，然后用总和除以数量，注意避免除零错误。
In pseudocode, the max algorithm might look like this:
在伪代码中，求最大值的算法可能如下：
max ← list[0]
FOR i ← 1 TO LENGTH(list)-1
IF list[i] > max THEN max ← list[i]
NEXT i
OUTPUT max
5. Linear Search | 线性搜索
Linear search examines each element in a list sequentially until the target is found or the end is reached. It works on both sorted and unsorted data, making it versatile but, in the worst case, slow for large datasets.
线性搜索按顺序逐一检查列表中的每个元素，直到找到目标或到达末尾。它既适用于已排序数据，也适用于未排序数据，因此通用性好，但对大数据集在最坏情况下速度较慢。
The algorithm uses a loop and a Boolean flag or index variable. When the target matches an element, the search can exit early. If the list is exhausted without a match, the result is typically a sentinel value such as -1.
该算法使用循环和一个布尔标志或索引变量。当目标与某个元素匹配时，搜索可以提前退出。如果遍历完整列表仍未匹配，结果通常是一个哨兵值，如 -1。
Time complexity: O(n) in the worst case, where n is the number of elements. For small lists or data that is frequently unsorted, linear search remains a practical choice.
时间复杂度：最坏情况为 O(n)，其中 n 是元素个数。对于小列表或经常未排序的数据，线性搜索仍然是一个实用的选择。
| Step | Operation |
|---|---|
| 1 | Start at index 0 |
| 2 | If current element equals target, return index |
| 3 | Else move to next index; repeat until end |
| 4 | If end reached without match, return ‘not found’ |
6. Binary Search | 二分搜索
Binary search is a divide-and-conquer algorithm that requires a sorted list. It repeatedly halves the search interval by comparing the target to the middle element. If the target equals the middle, the search ends. If the target is smaller, the search continues in the left half; if larger, in the right half.
二分搜索是一种分治算法，要求列表已排序。它通过将目标与中间元素比较，不断将搜索区间减半。若目标等于中间元素，搜索结束。若目标更小，则在左半部分继续；若更大，则在右半部分继续。
Because each comparison eliminates roughly half the remaining elements, binary search runs in O(log₂ n) time—a dramatic improvement over linear search for large n. However, the overhead of keeping the list sorted must be considered.
因为每次比较大约消除剩余元素的一半，二分搜索的时间复杂度为 O(log₂ n)——对于较大的 n，这比线性搜索有显著提升。但是必须考虑维护列表有序性的开销。
A typical pseudocode implementation uses two pointers, low and high, and a loop that continues while low ≤ high. The midpoint is calculated with integer division: mid ← (low + high) DIV 2. Care is needed to avoid infinite loops when the target is absent.
典型的伪代码实现使用两个指针 low 和 high，并在 low ≤ high 时循环。中点通过整数除法计算：mid ← (low + high) DIV 2。需要注意当目标不存在时避免无限循环。
7. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through the list, compares adjacent items, and swaps them if they are in the wrong order. Each pass through the list “bubbles” the largest unsorted element to its correct position at the end.
冒泡排序反复遍历列表，比较相邻项，如果顺序错误就交换它们。每一次遍历都将未排序部分的最大元素“冒泡”到它在末尾的正确位置。
The algorithm can be optimised with a flag to detect whether any swap occurred during a pass; if no swaps occur, the list is already sorted and the algorithm can terminate early. Even with this optimisation, the worst-case and average time complexity remain O(n²).
该算法可以通过一个标志位优化：检测在一次遍历中是否发生了交换；如果没有发生交换，列表已经有序，算法可提前终止。即使如此优化，最坏和平均时间复杂度仍为 O(n²)。
Bubble sort is rarely used in practice for large datasets due to its inefficiency, but it is a staple of introductory computer science because it is simple to implement and analyse. Exam questions might ask students to trace a bubble sort on a small array or identify the state of the array after a given number of passes.
冒泡排序因其效率低下，在大数据集上很少实际使用，但由于实现和分析简单，它是计算机科学入门的核心内容。考题可能要求学生追踪一个小数组上的冒泡排序，或识别经过指定次数遍历后数组的状态。
8. Insertion Sort and Selection Sort | 插入排序与选择排序
Insertion sort builds the final sorted list one element at a time. It takes the next element from the unsorted portion and inserts it into the correct position within the already sorted portion, shifting larger elements to the right as needed. Its time complexity is O(n²) in the worst case, but it performs well on nearly sorted data (O(n) best case). Insertion sort is stable, meaning equal elements retain their relative order.
插入排序逐个元素地构建最终有序列表。它从未排序部分取出下一个元素，将其插入已排序部分的正确位置，必要时将较大元素右移。最坏时间复杂度为 O(n²)，但在几乎有序的数据上表现良好（最好情况 O(n)）。插入排序是稳定的，即相等元素保持相对顺序。
Selection sort divides the list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first unsorted element, growing the sorted region by one. Regardless of input, selection sort always performs O(n²) comparisons. It is not stable but has the property of making the minimum possible number of swaps (O(n)), which can be beneficial when write operations are expensive.
选择排序将列表分为已排序区域和未排序区域。它反复从未排序区域中选择最小（或最大）元素，并将其与第一个未排序元素交换，使已排序区域增长一个元素。无论输入如何，选择排序始终执行 O(n²) 次比较。它不稳定，但具有交换次数最少（O(n)）的特性，这在写操作开销较大时可能有益。
Understanding the differences between these elementary sorts helps students recognise trade-offs in algorithm design. On exams, you might be asked to implement or compare the number of swaps vs comparisons.
理解这些基本排序之间的差异有助于学生认识算法设计中的权衡。考试中，可能要求实现或比较交换次数与比较次数。
9. Quicksort and Merge Sort | 快速排序与归并排序
Quicksort and merge sort are efficient divide-and-conquer sorting algorithms with average time complexity O(n log n). They are frequently contrasted in exam questions about recursive algorithms and efficiency.
快速排序和归并排序是高效的分治排序算法，平均时间复杂度为 O(n log n)。在关于递归算法和效率的考题中，它们经常成对出现。
Quicksort selects a pivot element and partitions the array so that elements less than the pivot come before it and elements greater come after. It then recursively sorts the sub-arrays. In the worst case (e.g., already sorted data with a poorly chosen pivot), quicksort degrades to O(n²), but random pivoting or median-of-three strategies mitigate this risk. It sorts in-place, requiring minimal extra memory.
快速排序选择一个基准元，将数组分区，使小于基准元的元素在其前面，大于的在其后面，然后递归地对子数组排序。在最坏情况下（如已排序数据且基准选择不当），快速排序退化至 O(n²)，但随机基准或三数取中策略可降低风险。它原地排序，所需额外内存极少。
Merge sort recursively splits the list into halves until sublists contain a single element. Then it merges these sublists back together in sorted order. Merge sort guarantees O(n log n) performance in all cases and is stable. The main drawback is that it requires O(n) auxiliary space for the merging process.
归并排序递归地将列表对半分，直到子列表只含单个元素，然后将这些子列表按序合并回来。归并排序在所有情况下都保证 O(n log n) 的性能，并且稳定。主要缺点是需要 O(n) 的辅助空间用于合并过程。
T(n) = 2T(n/2) + O(n)
This recurrence relation describes merge sort’s divide, conquer, and combine steps.
这个递推关系描述了归并排序的分、治、合步骤。
10. Recursion | 递归
Recursion is a technique where a function calls itself to solve smaller instances of the same problem. A recursive algorithm must have a base case that stops the recursion and a recursive case that moves towards the base case.
递归是一种函数调用自身以解决同一问题的较小实例的技术。递归算法必须有一个停止递归的基准情形，以及一个向基准情形推进的递归情形。
Classic examples include calculating factorial (n! = n × (n-1)! with base 0! = 1), Fibonacci numbers, and the Tower of Hanoi. In trees and graphs, recursion provides elegant solutions for traversal (pre-order, in-order, post-order).
经典示例包括计算阶乘（n! = n × (n-1)!，基准 0! = 1）、斐波那契数列和汉诺塔。在树和图中，递归为遍历（前序、中序、后序）提供了优雅的解决方案。
Recursion can be less efficient than iteration due to function call overhead and the risk of stack overflow. Some problems, however, are inherently recursive and difficult to express iteratively. Tail recursion optimisation, supported by some compilers, can reduce overhead.
由于函数调用开销和堆栈溢出风险，递归可能比迭代效率低。然而，有些问题本质上是递归的，难以用迭代表达。某些编译器支持的尾递归优化可以降低成本。
Exam questions often ask students to trace a recursive function, identify the base case, or convert a recursive algorithm to an iterative one using a stack.
考题常要求学生追踪递归函数、识别基准情形，或使用栈将递归算法转换为迭代形式。
11. Algorithm Efficiency and Big O Notation | 算法效率与大 O 表示法
Algorithm efficiency is measured in terms of time complexity (how runtime grows with input size) and space complexity (how memory usage grows). Big O notation describes the upper bound of growth rate, abstracting away constants and lower-order terms.
算法效率通过时间复杂度（运行时间随输入规模的增长情况）和空间复杂度（内存使用随输入规模的增长情况）来衡量。大 O 表示法描述增长率的上界，忽略常数和低阶项。
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, quicksort (average) |
| O(n²) | Quadratic | Bubble sort, selection sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci (naive) |
To determine Big O, count the dominant operations. For a single loop iterating n times, complexity is O(n). Nested loops over n give O(n²). When the problem size is halved each time, complexity is typically logarithmic, O(log n).
确定大 O 的方法是统计主导操作的次数。单个循环迭代 n 次，复杂度为 O(n)。嵌套循环对 n 次迭代给出 O(n²)。当问题规模每次减半时，复杂度通常为对数级，O(log n)。
Space complexity considers auxiliary memory, not the input storage itself. An in-place algorithm like quicksort uses O(log n) space for recursion stack, while merge sort uses O(n) extra space.
空间复杂度考虑的是辅助内存，而非输入存储本身。快速排序等原地算法使用 O(log n) 的递归栈空间，而归并排序使用 O(n) 的额外空间。
12. Common Exam Pitfalls and Tips | 常见考试陷阱与技巧
Students often lose marks by confusing algorithm types (e.g., stating binary search works on unsorted data), forgetting base cases in recursion, or miscalculating Big O (overlooking that the innermost loop’s cost multiplies, not adds).
学生常因混淆算法类型（例如声称二分搜索适用于未排序数据）、忘记递归中的基准情形，或错误计算大 O（忽略最内层循环的开销是相乘而非相加）而丢分。
- Always check preconditions: binary search requires sorted data; merges and comparison-based sorts rely on a defined ordering.
- 始终检查前提条件：二分搜索要求数据已排序；合并和基于比较的排序依赖于定义的次序。
- Use trace tables methodically during dry-runs; label columns for each variable and update row by row.
- 在手工执行时有条理地使用追踪表；为每个变量设置列，并逐行更新。
- When writing pseudocode, maintain consistent indentation and explicitly initialise accumulators.
- 编写伪代码时，保持一致的缩进并显式初始化累加器。
- In recursion questions, identify the base case first—it is the key to preventing infinite calls.
- 在递归问题中，首先识别基准情形——它是防止无限调用的关键。
- For time complexity, if the problem halves the remaining data each step, think log n; if it touches every element in nested loops, think n².
- 分析时间复杂度时，若每一步将剩余数据减半，考虑 log n；若嵌套循环触及每个元素，考虑 n²。
Finally, practice converting between representations: given a flowchart, write the pseudocode; given pseudocode, draw a trace table and predict output. This cross-format skill is heavily tested.
最后，练习在不同表示形式之间转换：给出流程图，写出伪代码；给出伪代码，画出追踪表并预测输出。这种跨格式的技能经常被重点考查。
Published by TutorHao | IB CCEA Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导