📚 A-Level OCR Computer Science: Algorithms Exam Essentials | A-Level OCR 计算机：算法 考点精讲
Algorithms form the intellectual core of computer science. In OCR A-Level Computer Science, you are expected not only to understand what an algorithm is, but also to design, trace, compare and evaluate them. This article distils the essential knowledge you need for the exam, covering representation, searching and sorting, complexity analysis, graph traversals, design paradigms, and practical problem-solving strategies. Each section pairs a concise English explanation with a parallel Chinese translation, helping you master the terminology in both languages.
算法是计算机科学的智力核心。在 OCR A-Level 计算机课程中，你不仅需要理解算法的定义，还要能够设计、追踪、比较和评估算法。本文提炼了考试必备的核心知识，涵盖算法表示、搜索与排序、复杂度分析、图遍历、设计范式以及实际解题策略。每个小节都以配对的中英文段落呈现，帮助你掌握双语术语。
1. What Is an Algorithm? | 什么是算法？
An algorithm is a finite sequence of well-defined, unambiguous instructions designed to solve a specific problem or perform a computation. It must have a clear input and output, be effective (each step can be carried out in finite time) and terminate after a finite number of steps. In the OCR specification, you must be able to describe algorithms in words, pseudocode and flowcharts, and understand that the same problem can be solved by different algorithms with varying efficiency.
算法是有限条定义明确、无歧义的指令序列，用于解决特定问题或完成计算。它必须有清晰的输入和输出，具备可行性（每一步可在有限时间内完成），并在有限步骤后终止。在 OCR 大纲中，你需要会用自然语言、伪代码和流程图描述算法，并理解同一问题可由不同算法解决，效率各有差异。
2. Algorithm Representation: Pseudocode and Flowcharts | 算法表示法：伪代码与流程图
Pseudocode is a structured, language-independent way of expressing algorithms. OCR provides a specific pseudocode syntax that you must be comfortable reading and writing. Keywords such as INPUT, OUTPUT, IF…THEN…ELSE…ENDIF, WHILE…DO…ENDWHILE, FOR…TO…NEXT and REPEAT…UNTIL form the building blocks. Flowcharts use standard symbols: ellipses for start/end, parallelograms for input/output, rectangles for processes, diamonds for decisions, and arrows to indicate flow of control.
伪代码是一种结构化的、独立于编程语言的算法表达方式。OCR 提供了特定的伪代码语法，你必须熟练阅读和书写。INPUT、OUTPUT、IF…THEN…ELSE…ENDIF、WHILE…DO…ENDWHILE、FOR…TO…NEXT 和 REPEAT…UNTIL 等关键字是构建模块。流程图使用标准符号：椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理步骤，菱形表示判断，箭头表示控制流。
A trace table is a valuable tool for dry-running an algorithm. It systematically records the values of variables at each step, helping to verify correctness and identify logic errors. For exam questions, you may be asked to complete a trace table for a given pseudocode and state the final output.
追踪表是手动执行算法的有力工具。它系统地记录每一步变量的值，有助于验证正确性并发现逻辑错误。考试中可能要求为给定的伪代码补全追踪表，并给出最终输出。
3. Searching Algorithms: Linear and Binary Search | 搜索算法：线性搜索与二分搜索
A linear search checks each element in a list sequentially until the target is found or the end is reached. It works on unsorted data and has a worst-case time complexity of O(n). Pseudocode example:
线性搜索按顺序检查列表中的每个元素，直到找到目标或到达末尾。它适用于未排序的数据，最坏时间复杂度为 O(n)。伪代码示例：
FOR i ← 0 TO LEN(list)-1
IF list[i] = target THEN OUTPUT i
NEXT i
OUTPUT "not found"
A binary search requires a sorted list. It repeatedly divides the search interval in half. Compare the target with the middle element; if not equal, discard the half where the target cannot lie. The time complexity is O(log n), making it much faster for large datasets.
二分搜索要求列表已排序。它反复将搜索区间减半：将目标与中间元素比较；若不相等，则舍弃目标不可能存在的一半。时间复杂度为 O(log n)，对于大数据集快得多。
low ← 0, high ← LEN(list)-1
WHILE low ≤ high
mid ← (low + high) DIV 2
IF list[mid] = target THEN OUTPUT mid
ELSE IF list[mid] < target THEN low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
OUTPUT "not found"
4. Sorting Algorithms: Bubble, Insertion and Merge Sort | 排序算法：冒泡排序、插入排序与归并排序
Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. After each pass the largest unsorted element bubbles to its correct position. Its average and worst-case complexity is O(n²). It is simple but inefficient for large n.
冒泡排序重复遍历列表，比较相邻元素，若顺序错误则交换。每趟遍历后，最大的未排序元素会“冒泡”到正确位置。平均和最坏时间复杂度为 O(n²)。算法简单，但对大 n 效率低下。
Insertion sort builds the sorted list one element at a time. It takes an element from the unsorted part and inserts it into the correct position within the sorted part. Like bubble sort, it is O(n²), but performs well on small or nearly sorted datasets.
插入排序一次一个元素地构建有序列表。它从未排序部分取出一个元素，并将其插入到已排序部分的正确位置。与冒泡排序一样是 O(n²)，但在小规模或近似有序的数据上表现良好。
Merge sort is a divide-and-conquer algorithm that recursively splits the list into two halves until each sublist has length 1, then repeatedly merges sublists to produce new sorted sublists. Its time complexity is O(n log n) in all cases, making it very efficient for large data but requiring extra memory for merging.
归并排序是一种分治算法：递归地将列表分成两半，直到每个子列表长度为 1，然后反复合并子列表以生成新的有序子列表。所有情况下时间复杂度均为 O(n log n)，对大规模数据非常高效，但合并时需要额外内存。
5. Complexity Analysis and Big O Notation | 复杂度分析与大 O 表示法
Time complexity measures how the execution time of an algorithm grows with the input size n. Big O notation describes the upper bound, ignoring constant factors and lower-order terms. Common complexities in OCR exams:
时间复杂度衡量算法执行时间如何随输入规模 n 增长。大 O 表示法描述上界，忽略常数因子和低阶项。OCR 考试中常见的复杂度有：
| Big O | Name 名称 | Example 示例 |
|---|---|---|
| O(1) | Constant 常数 | Accessing array element 访问数组元素 |
| O(log n) | Logarithmic 对数 | Binary search 二分搜索 |
| O(n) | Linear 线性 | Linear search 线性搜索 |
| O(n log n) | Linearithmic 线性对数 | Merge sort 归并排序 |
| O(n²) | Quadratic 平方 | Bubble sort 冒泡排序 |
| O(2ⁿ) | Exponential 指数 | Recursive Fibonacci 递归斐波那契 |
Space complexity is similarly analysed but refers to the amount of memory an algorithm needs. Algorithms that require additional data structures proportional to input size (e.g. merge sort) have O(n) space complexity, while in-place algorithms like bubble sort require O(1) extra space.
空间复杂度的分析类似，但指算法所需的内存空间。需要与输入规模成比例的额外数据结构的算法（如归并排序）空间复杂度为 O(n)，而就地算法（如冒泡排序）仅需 O(1) 额外空间。
6. Standard Algorithms: Maximum, Minimum, Mean and Counting | 标准算法：最大值、最小值、平均值与计数
OCR expects you to be able to write and understand standard aggregation algorithms. Finding the maximum (or minimum) involves initialising a variable with the first element and then iterating through the rest, updating whenever a larger (or smaller) element is found.
OCR 要求你会编写和理解标准聚合算法。求最大值（或最小值）需要用一个变量初始化为第一个元素，然后遍历其余元素，每当发现更大（或更小）的元素时更新该变量。
max ← list[0]
FOR i ← 1 TO LEN(list)-1
IF list[i] ⊳ max THEN max ← list[i]
NEXT i
OUTPUT max
To calculate the mean, sum all elements and divide by the count. To count occurrences meeting a condition, initialise a counter to 0 and increment it each time the condition is true. These linear-scan algorithms are all O(n).
计算平均值时，先求和再除以元素个数。计算满足条件的出现次数时，将计数器初始化为 0，每次条件为真时加 1。这些线性扫描算法的时间复杂度都是 O(n)。
7. Graph and Tree Traversal: Depth-First and Breadth-First | 图与树的遍历：深度优先与广度优先
Graph traversal is fundamental in many applications such as pathfinding and web crawling. Depth-first traversal (DFS) uses a stack (either explicitly or via recursion) to go as deep as possible along one branch before backtracking. Breadth-first traversal (BFS) uses a queue to visit all neighbours of a node before moving to the next level.
图遍历是路径查找和网页爬虫等许多应用的基础。深度优先遍历（DFS）使用栈（显式或通过递归）沿着一条分支尽可能深入，直到无法继续再回溯。广度优先遍历（BFS）使用队列，在进入下一层之前先访问节点的所有邻居。
For trees, the traversal order is named pre-order, in-order and post-order for depth‑first approaches on binary trees. BFS on a tree is also called level‑order traversal. OCR exam questions often ask you to list nodes in the correct order, or to trace a traversal on a given graph adjacency list or matrix.
对于树，二叉树的深度优先遍历分为前序、中序和后序。树的 BFS 也称为层序遍历。OCR 考试常要求你列出正确的节点访问顺序，或在给定的图邻接表或邻接矩阵上追踪遍历过程。
8. Algorithm Design Strategies: Divide & Conquer, Greedy and Dynamic Programming | 算法设计策略：分治、贪心与动态规划
Divide and conquer splits a problem into smaller subproblems, solves them recursively, and combines their solutions. Merge sort and binary search are classic examples. This strategy often leads to O(n log n) complexity. A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum; examples include Dijkstra's shortest path algorithm and the coin change problem (with canonical coin systems).
分治法将问题划分为更小的子问题，递归求解后合并结果。归并排序和二分搜索是经典例子。该策略常带来 O(n log n) 复杂度。贪心算法每一步都做出局部最优选择，希望找到全局最优；例子包括 Dijkstra 最短路径算法和找零钱问题（在规范硬币系统中）。
Dynamic programming is an extension where overlapping subproblems are solved once and stored, avoiding repeated work. It is not always explicitly tested at A-Level OCR but understanding the principle (memoisation) is beneficial for problem‑solving questions.
动态规划是分治的延伸，将重叠子问题只求解一次并存储，避免重复计算。OCR A-Level 虽不总是直接考查，但理解其原理（记忆化）对解决复杂问题大有裨益。
9. Recursion vs. Iteration | 递归与迭代
itself. A recursive solution must have a base case to terminate. For example, factorial n! = n × (n-1)! with base case 0! ually runs faster, though the code may be less intuitive for problems like tree traversal.
递归是指子程序调用自身。递归解必须有一个终止的基准情形。例如阶乘 n! = n × (n-1)!，基准情形 0! = 1。递归解法往往优雅，但可能因调用栈开销而低效，并有栈溢出风险。迭代使用循环，通常运行更快，但对树遍历等问题代码可能不够直观。
OCR may ask you to trace a recursive function or to convert a simple recursive algorithm into an iterative one. Always ensure you identify the base case and the recursive call.
OCR 可能要求你追踪递归函数或将简单递归算法转换为迭代形式。务必识别出基准情形和递归调用。
10. Practical Problem Solving with Algorithms | 算法实际解题策略
Exam questions often present a scenario and ask you to design or modify an algorithm. Follow a structured approach: read the problem carefully, identify inputs and outputs, break the task into steps, decide on suitable data structures (arrays, lists, stacks, queues), draft pseudocode, and then test with normal, boundary and invalid data. Always consider efficiency and edge cases.
考试常给出场景，让你设计或修改算法。遵循结构化方法：仔细读题，确定输入与输出，分解任务步骤，选择合适的数据结构（数组、列表、栈、队列），起草伪代码，然后用正常、边界和无效数据测试。始终考虑效率和边界情况。
11. Testing, Correctness and Trace Tables | 测试、正确性与追踪表
Algorithm testing is not just about finding errors; you must demonstrate that the algorithm handles all valid inputs correctly and fails gracefully with invalid inputs. Use trace tables to walk through each step logically. OCR mark schemes reward clear trace tables that show variable values at each stage, as well as identification of logic errors.
算法测试不仅是找错；你必须证明算法能正确处理所有有效输入，并对无效输入妥善处理。使用追踪表逻辑地执行每一步。OCR 评分标准奖励清晰的追踪表，能显示各阶段变量值，并识别逻辑错误。
12. Exam Tips and Common Pitfalls | 考试技巧与常见误区
When answering algorithm questions: 1) always state assumptions about input format; 2) label loops and conditions clearly in pseudocode; 3) double-check boundary indices (e.g., off‑by‑one errors); 4) when comparing algorithms, refer to both time and space complexity; 5) for graph traversal, state which data structure is used (stack or queue). Avoid memorising entire code; instead, understand the underlying logic so you can adapt to unfamiliar problems.
回答算法题时：1) 始终陈述输入的假设；2) 伪代码中清晰标注循环和条件；3) 复查边界索引（如差一错误）；4) 比较算法时，兼顾时间与空间复杂度；5) 图遍历要说明所用的数据结构（栈或队列）。避免死记硬背整段代码，而要理解内在逻辑，以便应变不熟悉的问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图