📚 Algorithm Essentials for IB & OCR Computer Science | IB & OCR 计算机算法考点精讲
Algorithms form the backbone of computational thinking. In both IB and OCR Computer Science specifications, the ability to design, trace, and evaluate algorithms is tested repeatedly. This guide condenses the must-know concepts into a revision-friendly format, covering everything from the basic building blocks of sequence, selection, and iteration, to standard searching and sorting routines, efficiency measurement with Big O notation, recursion, and trace tables. Whether you are preparing for Paper 2 in OCR or the algorithmic problem-solving components in IB, mastering these topics will give you a solid foundation. We will walk through each core idea with clear English explanations followed by their Chinese translations, ensuring bilingual learners can grasp the precision required for exams.
算法是计算思维的基石。在 IB 和 OCR 计算机科学大纲中，设计、跟踪和评估算法的能力会被反复考查。本指南将必考概念浓缩为适合复习的格式，涵盖从顺序、选择和迭代等基本构造，到标准搜索与排序例程、用大 O 符号衡量效率、递归以及跟踪表等所有内容。无论你是在准备 OCR 的 Paper 2，还是 IB 中的算法问题解决模块，掌握这些主题都会给你打下扎实的基础。我们将逐一讲解每个核心思想，以清晰的英文解释后紧跟其中文翻译，确保双语学习者能抓住考试所需的精准表述。
1. What is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous steps designed to solve a specific problem or perform a computation. In computer science, algorithms must terminate, produce a correct output for every valid input, and be stated in a form that can be implemented in a programming language. Everyday examples include recipes, assembly instructions, and the steps you follow to log into a system. For IB and OCR exams, an algorithm is often written in pseudocode or represented as a flowchart, and you need to be able to read, interpret, trace, and modify it.
算法是一个有限的、定义明确且无歧义的步骤序列，旨在解决某个特定问题或执行一项计算。在计算机科学中，算法必须能够终止、对每个有效输入都能产生正确的输出，并且以可以在编程语言中实现的形式表述。日常例子包括菜谱、组装说明书以及登录系统的步骤。对于 IB 和 OCR 考试，算法通常用伪代码编写或表示为流程图，你需要能够阅读、解释、跟踪和修改算法。
2. Algorithm Representation: Pseudocode and Flowcharts | 算法表示：伪代码与流程图
Pseudocode is a human-readable notation that uses structured English-like statements to describe an algorithm without worrying about syntax details of a specific language. In OCR exams, pseudocode follows a precise reference language with keywords like INPUT, OUTPUT, IF...THEN...ELSE...ENDIF, WHILE...DO...ENDWHILE, and FOR...TO...NEXT. Flowcharts use standard symbols: ovals for start/stop, parallelograms for input/output, rectangles for processes, diamonds for decisions, and arrows to show flow. Both representations must be unambiguous so that any competent programmer could convert them to working code. IB also allows pseudocode and occasionally flowcharts; you are expected to understand both.
伪代码是一种人类可读的表示法，使用结构化的、类似英语的语句来描述算法，而无需关心特定语言的语法细节。在 OCR 考试中，伪代码遵循精确的参考语言，包含诸如 INPUT、OUTPUT、IF...THEN...ELSE...ENDIF、WHILE...DO...ENDWHILE 和 FOR...TO...NEXT 等关键词。流程图使用标准符号：椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理步骤，菱形表示判断，箭头表示流向。两种表示都必须无歧义，以便任何有能力的程序员都能将其转换为可运行代码。IB 也允许使用伪代码，偶尔出现流程图；考生需要理解两者。
3. Basic Building Blocks: Sequence, Selection, Iteration | 基本结构：顺序、选择、迭代
Every algorithm can be constructed from three fundamental control structures. Sequence means executing instructions one after another in the order they appear. Selection allows branching based on a condition, typically using IF, ELSE IF, ELSE, or SWITCH/CASE statements. Iteration (looping) repeats a block of code either a fixed number of times (definite iteration with FOR) or while a condition remains true (indefinite iteration with WHILE or REPEAT...UNTIL). Mastery of these three constructs is essential because more complex algorithms—such as searching and sorting—are built by combining them. In exams, you will often be asked to identify which structure is being used or to correct a faulty loop condition.
每个算法都可以由三种基本控制结构构建。顺序意味着按照出现的先后顺序逐条执行指令。选择允许根据条件进行分支，通常使用 IF、ELSE IF、ELSE 或 SWITCH/CASE 语句。迭代（循环）重复执行一段代码，可以是固定次数（使用 FOR 的确定迭代），也可以在条件为真时重复执行（使用 WHILE 或 REPEAT...UNTIL 的不定迭代）。掌握这三种结构至关重要，因为更复杂的算法——如搜索和排序——都是通过组合它们来构建的。在考试中，你经常会被要求识别正在使用哪种结构，或者纠正一个有错误的循环条件。
4. Searching Algorithms: Linear and Binary Search | 搜索算法：线性查找与二分查找
Linear search checks each element in a list sequentially until the target is found or the list ends. It works on unsorted data and has a worst-case time complexity of O(n). Binary search repeatedly divides a sorted list in half, comparing the middle element with the target to discard half of the remaining items each step. Its time complexity is O(log n), making it far more efficient on large datasets. However, it requires the data to be sorted beforehand. OCR and IB exams often present pseudocode for both algorithms and ask you to trace the number of comparisons, identify the conditions under which each is appropriate, or complete missing steps in the algorithm.
线性查找按顺序检查列表中的每个元素，直到找到目标或列表结束。它适用于未排序的数据，最坏情况的时间复杂度为 O(n)。二分查找反复将已排序的列表分成两半，每一步将中间元素与目标进行比较，以舍弃剩余项的一半。其时间复杂度为 O(log n)，在大型数据集上效率高得多。但它要求数据预先排序。OCR 和 IB 考试经常给出这两种算法的伪代码，要求你跟踪比较次数，识别每种算法适用的条件，或补全算法中缺失的步骤。
5. Sorting Algorithms: Bubble, Insertion, Merge Sort | 排序算法：冒泡、插入、归并排序
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process repeats until no swaps are needed. It has O(n²) time complexity and is mainly used for educational purposes. Insertion sort builds the sorted list one item at a time by taking each new element and inserting it into its correct position among the already sorted items. It is efficient for small or nearly sorted datasets ( O(n²) worst-case, but O(n) best-case). Merge sort is a divide-and-conquer algorithm that recursively splits the list into halves until each sublist contains a single element, then merges those sublists back together in sorted order. It guarantees O(n log n) performance but requires additional memory. Exam questions often ask you to perform a pass of bubble sort, show the stages of merge sort, or compare the suitability of these algorithms under different constraints.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。这一过程重复进行，直到不需要任何交换。其时间复杂度为 O(n²)，主要用于教学目的。插入排序一次构建一个已排序项，通过取出每个新元素并将其插入到已排序项中的正确位置。它适用于小型或接近已排序的数据集（最坏情况 O(n²)，但最好情况 O(n)）。归并排序是一种分治算法，递归地将列表对半分割，直到每个子列表只包含一个元素，然后将这些子列表按序合并回一起。它保证 O(n log n) 的性能，但需要额外内存。考题常要求你执行一趟冒泡排序，展示归并排序的各个阶段，或在不同约束条件下比较这些算法的适用性。
6. Algorithm Efficiency and Big O Notation | 算法效率与大 O 表示法
Big O notation describes the upper bound of an algorithm’s growth rate as the input size (n) increases, focusing on the dominant term and ignoring constants. Common complexities include O(1) (constant time, e.g., accessing an array element by index), O(log n) (logarithmic, e.g., binary search), O(n) (linear, e.g., linear search), O(n log n) (e.g., merge sort), O(n²) (quadratic, e.g., bubble sort), and O(2ⁿ) (exponential, e.g., some recursive solutions to the Fibonacci sequence without memoization). In IB and OCR, you must be able to identify the time complexity of given algorithms, justify your reasoning, and understand the practical implications: an O(n²) algorithm may be fine for small n but becomes impractical for large inputs.
大 O 表示法描述了随着输入规模（n）增长，算法增长速率的上界，它关注起主导作用的项并忽略常数。常见复杂度包括 O(1)（常数时间，例如通过索引访问数组元素）、O(log n)（对数时间，如二分查找）、O(n)（线性时间，如线性查找）、O(n log n)（如归并排序）、O(n²)（平方时间，如冒泡排序）以及 O(2ⁿ)（指数时间，如某些不使用记忆化的斐波那契递归解法）。在 IB 和 OCR 中，你必须能够识别给定算法的时间复杂度，论证你的推理，并理解其实际影响：一个 O(n²) 的算法对于小规模 n 可能尚可，但对于大规模输入会变得不切实际。
7. Standard Algorithms: Maximum, Minimum, Counting | 标准算法：求最大值、最小值、计数
Standard algorithms are reusable patterns that appear frequently in exams. Finding the maximum initialises a variable with the first element (or a very small number) and iterates through the list, updating the variable whenever a larger value is encountered. The minimum is analogous. Counting occurrences uses a counter variable, incremented each time an element matches a target condition. Summing and averaging are also common. These algorithms form the basis of many larger problems, such as data analysis or processing records. In both pseudocode tracing and programming questions, you will be expected to write or complete these standard loops correctly, paying attention to initialisation and boundary conditions to avoid off-by-one errors.
标准算法是可复用的模式，在考试中经常出现。求最大值时，用一个变量初始化为第一个元素（或一个非常小的数），然后遍历列表，每当遇到更大的值时更新该变量。求最小值类似。计数出现次数使用一个计数器变量，每当元素匹配目标条件时将其递增。求和与求平均值也很常见。这些算法构成了许多更大问题的基础，例如数据分析或记录处理。在伪代码跟踪和编程题中，你需要正确编写或补全这些标准循环，注意初始化和边界条件，以避免差一错误。
8. Recursion | 递归
Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive solution must have a base case that stops the recursion, and a recursive case that reduces the problem size. Classic examples include calculating factorials, Fibonacci numbers, and traversing tree data structures. Recursion can lead to elegant code, but without careful design it may cause stack overflow or exponential time complexity. When tracing recursive algorithms in IB and OCR, you must show the call stack, track parameter values at each call, and identify the order in which calls return. Tail recursion and the conversion between recursion and iteration are also examined at higher levels.
递归是一种函数调用自身来解决同一问题的较小实例的技术。每个递归解决方案都必须有一个终止递归的基准情形，以及一个缩小问题规模的递归情形。经典例子包括计算阶乘、斐波那契数以及遍历树数据结构。递归可以带来优雅的代码，但若设计不小心，可能会导致栈溢出或指数级时间复杂度。在 IB 和 OCR 中跟踪递归算法时，你必须展示调用栈，跟踪每次调用时的参数值，并识别调用返回的顺序。尾递归以及递归与迭代之间的转换在较高层级也会考查。
9. Trace Tables and Dry Runs | 跟踪表与手工执行
A trace table is a systematic tool used to follow the execution of an algorithm step by step, recording the values of variables and the output at each stage. It is heavily examined in OCR Paper 2 and IB algorithmic questions. To complete a trace table, you set up columns for each variable (and often for conditions and output), then work through the algorithm line by line, updating the table as values change. Trace tables help detect logical errors, test understanding of loops and conditionals, and verify algorithm correctness. Common pitfalls include failing to update a variable at the right moment or misinterpreting the order of operations inside a loop.
跟踪表是一种系统性的工具，用于逐步跟踪算法的执行，记录每个阶段变量的值和输出。它在 OCR Paper 2 和 IB 的算法题中被大量考查。要完成一个跟踪表，你需要为每个变量（通常还包括条件和输出）设置列，然后逐行执行算法，在数值变化时更新表格。跟踪表有助于发现逻辑错误，测试对循环和条件语句的理解，并验证算法的正确性。常见的陷阱包括未在正确时刻更新变量，或误解循环内部操作的执行顺序。
10. Comparing Algorithms: Time and Space Complexity | 算法比较：时间与空间复杂度
When comparing two algorithms that solve the same problem, you must consider both time complexity (how execution time grows with input size) and space complexity (how memory usage grows). A linear search uses O(1) extra space but O(n) time; binary search uses O(1) space but O(log n) time (assuming the data is already sorted). Merge sort uses O(n log n) time but requires O(n) additional space, while bubble sort uses O(1) extra space but O(n²) time. Exam questions may provide multiple algorithms and ask you to recommend one based on constraints like limited memory, large datasets, or the need for stability (preserving the original order of equal elements). You must be able to justify your choice with reference to complexity analysis.
在比较解决同一问题的两种算法时，你必须同时考虑时间复杂度（执行时间如何随输入规模增长）和空间复杂度（内存使用如何增长）。线性查找使用 O(1) 额外空间但需 O(n) 时间；二分查找使用 O(1) 空间但需 O(log n) 时间（假设数据已排序）。归并排序使用 O(n log n) 时间但需要 O(n) 额外空间，而冒泡排序使用 O(1) 额外空间但需 O(n²) 时间。考题可能给出多个算法，并要求你根据有限内存、大型数据集或需要稳定性（保持相等元素的原始顺序）等约束条件推荐其中一个。你必须能够参考复杂度分析来论证你的选择。
11. Common Pitfalls and Exam Tips | 常见雷区与考试技巧
One frequent mistake is confusing the loop control conditions—WHILE loops check at the start, whereas REPEAT...UNTIL checks at the end, guaranteeing at least one execution. Another is mishandling array indexing: remember that many pseudocode languages use 0‑based indexing, but some exam questions may state 1‑based indexing explicitly. Off‑by‑one errors in loops often result from incorrectly setting the initial or terminal values of a FOR loop. When writing algorithms, always initialise variables explicitly before using them. In binary search, a common error is computing the midpoint incorrectly or forgetting to exclude the middle element in the next range. For trace tables, do not skip rows—complete every change, and double‑check the order of operations within a line of pseudocode. Finally, when describing algorithm efficiency, avoid vague phrases like “faster”; instead use Big O notation and refer to growth rates.
一个常见错误是混淆循环控制条件——WHILE 循环在开头检查条件，而 REPEAT...UNTIL 在结尾检查，确保至少执行一次。另一个错误是处理数组索引不当：记住许多伪代码语言使用基于 0 的索引，但有些考题可能会明确说明基于 1 的索引。循环中的差一错误常常是因为错误设置了 FOR 循环的初始值或终止值。在编写算法时，务必在使用变量之前显式地初始化它们。在二分查找中，一个常见错误是错误地计算中点，或忘记在下一次范围中排除中间元素。对于跟踪表，不要跳过行——记录每一次变化，并仔细检查一行伪代码中操作的顺序。最后，在描述算法效率时，避免使用“更快”这类模糊词汇；取而代之，使用大 O 表示法并提及增长率。
12. Summary and Key Takeaways | 总结与核心要点
Algorithms are central to problem‑solving in computer science. The key takeaways for IB and OCR candidates are: recognise and apply the three building blocks; understand and trace linear and binary search as well as bubble, insertion, and merge sorts; calculate Big O for both time and space; systematically use trace tables to verify logic; and recognise when recursion is appropriate and how to avoid infinite recursion with a solid base case. Regular practice with past papers, especially writing out trace tables step by step and coding algorithms from pseudocode, builds the fluency needed for top marks. Remember that examiners are looking for precision, so always state assumptions (e.g., 0‑based indexing) and be explicit in your reasoning.
算法是计算机科学中解决问题的核心。对 IB 和 OCR 考生而言，核心要点是：识别并应用三种基本结构；理解并跟踪线性查找、二分查找以及冒泡、插入和归并排序；计算时间和空间的大 O；系统地使用跟踪表来验证逻辑；并识别何时适合使用递归，以及如何通过扎实的基准情形避免无限递归。通过定期练习历年真题，尤其是逐步写出跟踪表并从伪代码编写代码，可以培养取得高分所需的熟练度。请记住，考官看重的是精确性，因此要始终陈述假设条件（例如基于 0 的索引）并在推理中做到清晰明确。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply