📚 Using and Understanding Algorithms | 使用与理解算法
Algorithms are the heart of computer science. They are step-by-step procedures designed to solve problems or perform tasks. From searching a database to rendering graphics, every piece of software relies on well-designed algorithms. In the Edexcel A-Level Computer Science curriculum, students must not only use common algorithms but also understand their internal logic, efficiency, and limitations. This article provides a comprehensive guide to mastering algorithms for your exam, blending theory with practical insight.
算法是计算机科学的核心。它们是用于解决问题或执行任务的逐步过程。从搜索数据库到渲染图形，每一款软件都依赖精心设计的算法。在 Edexcel A-Level 计算机科学课程中，学生不仅要会使用常见算法，还要理解其内部逻辑、效率与局限性。本文为你提供一份综合指南，帮助你在考试中掌握算法，将理论与实践融会贯通。
1. What Is an Algorithm? Definition and Properties | 什么是算法？定义与特性
An algorithm is a finite sequence of well-defined, unambiguous instructions to solve a problem. It takes some input, processes it through logical steps, and produces an output. Every algorithm must possess five key properties: finiteness (it terminates after a finite number of steps), definiteness (each step is precisely stated), input (zero or more values), output (one or more results), and effectiveness (the operations are basic enough to be carried out in finite time).
算法是用于解决问题的有限序列，由定义明确、无歧义的指令组成。它接受某些输入，通过逻辑步骤进行处理，并产生输出。每个算法必须具备五项关键特性：有限性（在有限步骤后终止）、确定性（每一步都有准确定义）、输入（零个或多个值）、输出（一个或多个结果）和有效性（操作足够基本，可以在有限时间内完成）。
In A-Level problems, you often need to describe an algorithm using pseudocode or a flowchart, proving you understand the sequence of steps. For instance, an algorithm to calculate the factorial of n is finite and definite: it multiplies numbers from 1 to n until n is reached.
在 A-Level 题目中，你经常需要用伪代码或流程图描述算法，证明你理解步骤的顺序。例如，计算 n 的阶乘的算法是有限且确定的：它将从 1 到 n 的数字相乘，直到到达 n。
2. Algorithm Representation: Flowcharts and Pseudocode | 算法表示：流程图与伪代码
Flowcharts use standard symbols – ovals for start/stop, parallelograms for input/output, rectangles for processes, and diamonds for decisions – to visually represent the flow of control. They help beginners trace logic without worrying about syntax. However, complex algorithms become cluttered; that's where pseudocode comes in.
流程图使用标准符号——椭圆表示开始/结束，平行四边形表示输入/输出，矩形表示处理过程，菱形表示判断——来可视化地表示控制流。它们帮助初学者追踪逻辑而无需担心语法。然而复杂算法会显得杂乱，这时伪代码就派上了用场。
Pseudocode is a midpoint between natural language and programming code. Edexcel allows flexible pseudocode as long as it is clear. For example, IF ... THEN ... ELSE ... ENDIF and FOR ... NEXT are common structures. Pseudocode lets you focus on algorithm logic without getting bogged down by specific syntax of a programming language.
伪代码介于自然语言和编程代码之间。Edexcel 允许使用灵活的伪代码，只要清晰即可。例如 IF ... THEN ... ELSE ... ENDIF 和 FOR ... NEXT 是常见结构。伪代码让你专注于算法逻辑，而不必拘泥于特定编程语言的语法。
In exams, you might be asked to draw a flowchart for a given problem or write pseudocode for a searching algorithm. Being fluent in both representations ensures you can answer any question format.
考试中你可能需要为给定问题绘制流程图，或为某种搜索算法编写伪代码。熟练掌握两种表示法能确保你应对任何题型。
3. Algorithm Efficiency: Time and Space Complexity | 算法效率：时间复杂度与空间复杂度
Efficiency is a measure of the resources an algorithm consumes. The two main resources are time (how many steps it takes) and space (how much memory it uses). As input size grows, some algorithms slow down dramatically while others stay fast. This is captured by complexity analysis.
效率是衡量算法消耗资源的尺度。两大主要资源是时间（执行步骤数）和空间（使用的内存量）。随着输入规模增大，有些算法急剧变慢，而另一些保持快速。这通过复杂度分析来刻画。
Time complexity is usually expressed as a function of the input size n. For example, a linear search examines each element until it finds the target; in the worst case it checks n times. Its time complexity is O(n). Space complexity considers extra memory besides the input; an in-place sorting algorithm uses O(1) extra space.
时间复杂度通常表示为输入规模 n 的函数。例如线性搜索逐个检查元素直到找到目标；最坏情况下需要检查 n 次，其时间复杂度为 O(n)。空间复杂度考虑除输入之外的额外内存；原地排序算法使用 O(1) 额外空间。
4. Big O Notation: Common Complexity Classes | 大 O 表示法：常见复杂度等级
Big O notation describes the upper bound of an algorithm's growth rate, focusing on the dominant term and ignoring constants. The most frequent complexity classes – from fastest to slowest – are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential, and O(n!) factorial.
大 O 表示法描述算法增长速率的上界，关注主导项而忽略常数。最常见的复杂度等级（从快到慢）是 O(1) 常数、O(log n) 对数、O(n) 线性、O(n log n) 线性对数、O(n²) 平方、O(2ⁿ) 指数和 O(n!) 阶乘。
You can estimate complexity by counting nested loops. A single loop over n items gives O(n). Two nested loops each running n times result in O(n²). Repeated halving (as in binary search) leads to O(log n) because the problem size reduces exponentially. Recursive algorithms often require recurrence relations to determine complexity.
你可以通过数循环嵌套来估计复杂度。单层循环遍历 n 个项得到 O(n)。两个嵌套循环各执行 n 次导致 O(n²)。反复折半（如二分搜索）产生 O(log n)，因为问题规模呈指数级缩减。递归算法通常需要递推关系来确定复杂度。
Example: Search algorithms – Linear search O(n) vs Binary search O(log n)
示例：搜索算法 – 线性搜索 O(n) 对 二分搜索 O(log n)
5. Linear Search and Binary Search | 线性搜索与二分搜索
Linear search traverses each element from the start until the target is found or the list ends. It works on unsorted data but is slow, with worst-case O(n). Binary search repeatedly divides a sorted list in half, comparing the middle value to the target and discarding the irrelevant half. It runs in O(log n) time, making it vastly faster on large datasets.
线性搜索从头开始遍历每个元素，直到找到目标或列表末尾。它适用于未排序数据但速度慢，最坏情况为 O(n)。二分搜索反复将已排序列表折半，比较中间值与目标并丢弃无关的一半。其运行时间为 O(log n)，在大数据集上快得多。
ces. For binary search, set low to 0 and high to length-1. While low ≤ high, compute mid = ⌊(low+high)/2⌋ is smaller, high = mid-1; else low = mid+1. If the loop exits without finding, return -1.
实现时需要小心处理索引。对于二分搜索，设 low 为 0，high 为长度-1。当 low ≤ high 时，计算 mid = ⌊(low+high)/2⌋。若 list[mid] 等于目标，返回 mid。若目标更小，则 high = mid-1；否则 low = mid+1。若循环结束未找到，返回 -1。
Exam tip: Know the preconditions – binary search requires a sorted array; linear search does not. Be able to trace steps and compare number of comparisons.
考试提示：知晓前置条件——二分搜索要求已排序数组；线性搜索则不需要。能追踪步骤并比较多寡。
6. Sorting Algorithms: Bubble Sort and Merge Sort | 排序算法：冒泡排序与归并排序
Bubble sort repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong order. The largest unsorted element 'bubbles up' to its correct position in each pass. Its worst-case time complexity is O(n²) and it is inefficient for large data, but it is simple to implement and works in-place.
冒泡排序反复遍历列表，比较相邻元素并在顺序错误时交换它们。每趟最大的未排序元素会“冒泡”到正确位置。其最坏时间复杂度为 O(n²)，对于大数据效率低下，但它实现简单且原地工作。
Merge sort follows the divide-and-conquer strategy. It recursively splits the list into halves until each sublist contains one element, then merges them back in sorted order. Merge sort has a time complexity of O(n log n) in all cases and is stable, but it requires additional O(n) space for merging. It is excellent for large datasets and linked lists.
归并排序遵循分治策略。它递归地将列表折半直到每个子列表包含一个元素，然后按照排序顺序将它们合并回去。归并排序在所有情况下的时间复杂度为 O(n log n) 且稳定，但它需要额外的 O(n) 空间进行合并。它非常适合大数据集和链表。
Comparison: Bubble sort swap count ≈ n²/2, Merge sort operations ≈ n log₂ n
比较：冒泡排序交换次数 ≈ n²/2，归并排序操作次数 ≈ n log₂ n
7. Recursive Algorithms: Concepts and Examples | 递归算法：概念与示例
ping condition) and a recursive step that reduces the problem toward the base case. The classic example is calculating factorial: n! = n × (n-1)! with base case 0! = 1.
当函数调用自身来解决同一问题的较小实例时，就发生了递归。每个递归算法必须有一个基准情形（停止条件）和一个递归步骤，将问题缩小向基准情形推进。经典例子是计算阶乘：n! = n × (n-1)!，基准情形 0! = 1。
Recursion can produce elegant solutions for problems like tree traversals, Fibonacci generation, and the Tower of Hanoi. However, deep recursion may cause stack overflow if not well designed, and naive recursive Fibonacci has exponential complexity O(2ⁿ). Using memoization or converting to iteration can optimise performance.
递归可为树遍历、斐波那契生成和汉诺塔等问题提供优雅解。然而，若设计不当，深度递归可能导致栈溢出，且朴素递归斐波那契的复杂度为指数级 O(2ⁿ)。使用记忆化或转换为迭代可以优化性能。
8. Algorithm Design Strategies: Divide and Conquer | 算法设计策略：分治法
Divide and conquer breaks a problem into smaller, self-similar subproblems, solves each recursively, and then combines the results. Merge sort and binary search are classic examples. This strategy often leads to efficient O(n log n) algorithms and is widely used in areas like matrix multiplication (Strassen) and closest pair of points.
分治法将问题分解为更小、自相似的子问题，递归解决每个子问题，然后组合结果。归并排序和二分搜索是经典例子。这一策略常常导出高效的 O(n log n) 算法，并广泛用于矩阵乘法（Strassen）和最近点对等领域。
olutions. Recurrence relations help analyse their complexity, for example T(n) = 2T(n/2) + O(n) yields O(n log n).
设计分治算法时，你必须确定如何划分输入、如何直接解决基准情形以及如何合并解。递推关系有助于分析其复杂度，例如 T(n) = 2T(n/2) + O(n) 得出 O(n log n)。
9. Algorithm Correctness and Testing | 算法正确性与测试
An algorithm is correct if, for every valid input, it produces the expected output and terminates. Correctness can be checked through testing with typical, edge, and invalid cases, but formal verification uses loop invariants and mathematical induction. For example, in binary search, a loop invariant is that if the target is in the list, it lies between low and high.
若对于每个有效输入，算法都能产生预期输出并终止，则它是正确的。正确性可通过典型、边界和无效用例的测试来检查，但形式化验证使用循环不变式和数学归纳法。例如，在二分搜索中，循环不变式是如果目标在列表中，它必位于 low 和 high 之间。
Trace tables are a practical tool: they record variable values at each step to manually verify algorithm logic. In the exam, you might be asked to complete a trace table for a given algorithm and explain the purpose of a loop invariant.
追溯表是一种实用工具：它记录每一步的变量值，以手工验证算法逻辑。考试中你可能需要为给定算法填写追溯表，并解释循环不变式的作用。
10. Limits of Computation: Computability and the Halting Problem | 计算局限性：可计算性与停机问题
Not all problems can be solved by algorithms. The halting problem asks whether a program, given its description and an input, will eventually halt or run forever. Alan Turing proved that no general algorithm can solve this for all possible programs—it is undecidable. This reveals fundamental limits of computation.
并非所有问题都能用算法解决。停机问题询问：给定一个程序的描述和输入，它最终会停止还是永远运行？艾伦·图灵证明了没有任何通用算法可以为所有可能的程序解决此问题——它是不可判定的。这揭示了计算的基本局限。
Understanding undecidability helps computer scientists recognise when they are trying to solve an unsolvable problem. Other undecidable problems include the equivalence of two context-free grammars. In A-Level, you should appreciate that some problems are beyond algorithmic solution and describe the halting problem in simple terms.
理解不可判定性帮助计算机科学家认识到自己是否在试图解决一个不可解的问题。其他不可判定的问题包括两个上下文无关文法的等价性。在 A-Level 中，你应当领会有些问题超出算法解决的范围，并能用简单的语言描述停机问题。
11. Practical Applications: Algorithms in Problem Solving | 实际应用：算法在问题解决中的作用
Algorithms are embedded in everyday technology: search engines use PageRank and indexing algorithms, GPS navigation employs shortest path algorithms like Dijkstra’s, and compression tools rely on Huffman coding. Recognising these applications deepens your understanding and helps tackle scenario-based exam questions.
算法嵌入在日常技术中：搜索引擎使用 PageRank 和索引算法，GPS 导航采用最短路径算法如迪杰斯特拉，压缩工具依赖哈夫曼编码。认识这些应用能加深理解，并有助于应对情景化考试题。
When solving a new problem, decompose it into known algorithmic patterns: can it be mapped to a graph, a search space, or an optimisation? Choosing the right abstract representation is half the battle. A-Level tasks often ask you to design or adapt an algorithm for a given context.
解决新问题时，将其分解为已知的算法模式：能否映射为图、搜索空间或优化问题？选择正确的抽象表示是成功的一半。A-Level 任务常要求你为给定情境设计或改造算法。
12. Summary and Exam Tactics | 总结与应试策略
To excel in the Using and Understanding Algorithms topic, practise writing pseudocode and drawing flowcharts for searching and sorting. Memorise the complexities: linear search O(n), binary search O(log n), bubble sort O(n²), merge sort O(n log n). Understand recursion and the idea of divide and conquer. Be able to explain the halting problem and why some problems cannot be solved algorithmically.
要在“使用和理解算法”主题中取得优异成绩，需练习为搜索和排序编写伪代码并绘制流程图。牢记复杂度：线性搜索 O(n)，二分搜索 O(log n)，冒泡排序 O(n²)，归并排序 O(n log n)。理解递归和分治思想。能解释停机问题及为何有些问题无法用算法解决。
During the exam, manage your time: read the algorithm carefully, trace it with a small dataset, and watch for edge cases like empty lists or duplicate values. Use the correct notation and show your working. With solid fundamentals, you can tackle any algorithm question with confidence.
考试时，合理分配时间：仔细阅读算法，用一个小的数据集追踪它，并留意边界情况如空列表或重复值。使用正确的符号并展示你的工作。凭借扎实的基本功，你可以自信地应对任何算法题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图