Algorithms | 算法 - aleveler.com

📚 Algorithms | 算法

An algorithm is a precise, step-by-step set of instructions that solves a problem or performs a computation. In A-Level Computer Science, algorithms are studied not just as code, but as reusable patterns for searching, sorting, pathfinding and decision-making. Understanding how to design, express and evaluate algorithms is central to the Edexcel specification.

算法是一组精确、逐步执行的指令，用于解决问题或完成计算。在 A-Level 计算机科学中，算法不仅是代码，更是用于搜索、排序、路径查找和决策的可复用模式。理解如何设计、表示和评估算法是 Edexcel 考试大纲的核心内容。

1. What Is an Algorithm? | 什么是算法？

An algorithm is a finite sequence of unambiguous instructions. It must have a clear start, defined inputs, a deterministic set of steps, and a terminating condition that produces outputs. Everyday examples include baking recipes, assembly instructions and the process of logging into a school network.

算法是有限的一系列无歧义的指令。它必须有明确的起点、定义好的输入、一组确定的步骤，以及产生输出并终止的条件。日常例子包括烘焙食谱、组装说明和登录学校网络的过程。

In computing, algorithms are independent of any programming language. The same algorithm can be implemented in Python, Java or pseudocode. What matters is that each step is precise enough for a machine to execute without interpretation or guesswork.

在计算中，算法独立于任何编程语言。同一算法可以用 Python、Java 或伪代码实现。重要的是每一步都足够精确，使机器无需解释或猜测即可执行。

2. Representing Algorithms: Pseudocode and Flowcharts | 算法的表示：伪代码与流程图

Pseudocode uses structured English-like statements to represent algorithms. It avoids programming-language-specific syntax but keeps sequence, selection and iteration clear. Common notation includes INPUT, OUTPUT, IF … THEN … ELSE, WHILE … DO and FOR … NEXT.

伪代码使用类似英语的结构化语句来表示算法。它避免特定编程语言的语法，但保持顺序、选择和迭代清晰。常见标记包括 INPUT、OUTPUT、IF … THEN … ELSE、WHILE … DO 和 FOR … NEXT。

Flowcharts represent the same logic visually. Rounded rectangles show start and end points, rectangles show processes, diamonds show decisions, and parallelograms show input or output. Flowcharts are useful for visualising branching and loops before coding.

流程图以可视化方式表示相同的逻辑。圆角矩形表示起点和终点，矩形表示处理过程，菱形表示判断，平行四边形表示输入或输出。流程图有助于在编写代码前直观展示分支和循环。

Both tools help decompose a problem into manageable sub-steps. Edexcel questions often ask candidates to trace a pseudocode algorithm or convert a flowchart into structured English, so precision matters more than style.

这两种工具都有助于将问题分解为可管理的子步骤。Edexcel 考试题经常要求考生跟踪伪代码算法，或将流程图转换为结构化英语，因此精确性比风格更重要。

3. Algorithmic Complexity and Big O Notation | 算法复杂度与大 O 表示法

Big O notation describes how the time or space requirements of an algorithm grow as the input size n increases. It focuses on the dominant term and ignores constants, because those constants have less impact for very large inputs.

大 O 表示法描述算法的运行时间或空间需求如何随输入规模 n 增大而增长。它关注主导项并忽略常数，因为当输入非常大时，这些常数的影响较小。

Common complexity classes include O(1) for constant time, O(log n) for logarithmic, O(n) for linear, O(n log n) for linearithmic, and O(n²) for quadratic time. An algorithm with O(n²) will become slow much more quickly than one with O(n log n) as n grows.

常见的复杂度类别包括：O(1) 表示常数时间，O(log n) 表示对数时间，O(n) 表示线性时间，O(n log n) 表示线性对数时间，O(n²) 表示二次时间。随着 n 增大，O(n²) 算法会比 O(n log n) 算法更快变得缓慢。

Edexcel expects students to compare algorithms by their worst-case Big O complexity, not by absolute milliseconds. For example, binary search is preferred over linear search for large sorted datasets because O(log n) grows far more slowly than O(n).

Edexcel 要求学生通过最坏情况的大 O 复杂度来比较算法，而不是通过绝对毫秒数。例如，对于大型有序数据集，二分搜索优于线性搜索，因为 O(log n) 的增长速度远慢于 O(n)。

4. Linear Search | 线性搜索

Linear search checks every element in a list one by one until the target value is found or the list ends. It works on unsorted data and requires no preprocessing, making it simple to implement and understand.

线性搜索逐一检查列表中的每个元素，直到找到目标值或列表结束。它适用于未排序的数据，不需要预处理，因此实现和理解都很简单。

The worst-case time complexity is O(n), because in the worst case the target is the last element or absent. The best case is O(1) when the target is found at the first position. On average, roughly half of the elements are checked, but Big O still records this as O(n).

最坏情况时间复杂度是 O(n)，因为最坏情况下目标是最后一个元素或不存在。最好情况是 O(1)，当目标在第一个位置时。平均而言，大约检查一半元素，但大 O 仍将其记录为 O(n)。

Linear search is appropriate for small lists or when data is constantly changing. It is also the only reliable option when the list cannot be sorted or when the data structure does not support direct indexing.

线性搜索适用于小列表或数据不断变化的情况。当列表无法排序，或数据结构不支持直接索引时，它也是唯一可靠的选择。

5. Binary Search | 二分搜索

Binary search operates on a sorted list by repeatedly dividing the search interval in half. It compares the target value with the middle element and discards the half that cannot contain the target.

二分搜索在有序列表中运行，通过反复将搜索区间减半来实现。它将目标值与中间元素比较，并舍弃不可能包含目标值的一半。

The algorithm remains very fast because each comparison halves the remaining search space. Its worst-case time complexity is O(log n), which means a list of one million items needs at most about twenty comparisons.

该算法非常快，因为每次比较都将剩余搜索空间减半。其最坏情况时间复杂度是 O(log n)，这意味着一个包含一百万个项目的列表最多只需约二十次比较。

However, binary search requires sorted data. If the list is unsorted, it must first be sorted, which adds overhead. Binary search cannot be applied directly to linked lists if random access by index is not available.

然而，二分搜索要求数据有序。如果列表未排序，必须首先进行排序，这会增加开销。如果链表不支持按索引随机访问，也不能直接应用二分搜索。

6. Bubble Sort | 冒泡排序

Bubble sort repeatedly steps through a list, compares adjacent pairs, and swaps them if they are in the wrong order. Larger values ‘bubble’ towards the end of the list on each pass, which gives the algorithm its name.

冒泡排序反复遍历列表，比较相邻元素对，如果顺序错误则交换它们。较大的值在每次遍历中向列表末尾“冒泡”，该算法因此得名。

The basic version has worst-case and average-case time complexity of O(n²). A useful optimisation uses a flag to detect whether any swaps occurred during a pass; if no swaps occurred, the list is already sorted and the algorithm can stop early.

基本版本的冒泡排序最坏和平均时间复杂度为 O(n²)。一种有用的优化是使用标志位检测一趟中是否发生了交换；如果没有发生交换，说明列表已经有序，算法可以提前停止。

Bubble sort is stable, meaning equal elements keep their original relative order. It requires only a small amount of extra memory, but it is too slow for large datasets and is mainly used for teaching sorting concepts.

冒泡排序是稳定的，这意味着相等的元素保持原有的相对顺序。它只需要少量额外内存，但对于大型数据集来说太慢，主要用于教学排序概念。

7. Merge Sort and Quicksort | 归并排序与快速排序

Merge sort uses a divide-and-conquer strategy. It recursively splits the list into halves until each sublist has one element, then repeatedly merges the sorted sublists back together. Merging guarantees that the final list is sorted.

归并排序使用分治策略。它递归地将列表分成两半，直到每个子列表只有一个元素，然后反复将已排序的子列表合并在一起。合并过程保证了最终列表有序。

Merge sort has a worst-case complexity of O(n log n), making it much faster than bubble sort for large lists. It is stable and works well with linked lists, but it requires additional memory proportional to n for the merging process.

归并排序的最坏时间复杂度为 O(n log n)，对于大型列表比冒泡排序快得多。它是稳定的，并且适用于链表，但合并过程需要与 n 成正比的额外内存。

Quicksort also uses divide and conquer, but it works by selecting a pivot and partitioning the list into values less than and greater than the pivot. Its average complexity is O(n log n), but the worst case can degrade to O(n²) if poor pivot choices are made consistently.

快速排序也使用分治策略，但它通过选择基准值并将列表划分为小于基准值和大于基准值的两部分来工作。它的平均复杂度为 O(n log n)，但如果持续选择糟糕的基准值，最坏情况可能退化为 O(n²)。

Unlike merge sort, quicksort can be implemented in-place, using little extra memory. However, its stability depends on the partitioning method. Edexcel candidates should be able to compare both algorithms in terms of efficiency, memory use and stability.

与归并排序不同，快速排序可以原地实现，只使用很少的额外内存。然而，其稳定性取决于划分方法。Edexcel 考生应能从效率、内存使用和稳定性方面比较这两种算法。

8. Recursion and the Call Stack | 递归与调用栈

Recursion is a technique where a function calls itself to solve smaller instances of the same problem. Every recursive algorithm must have a base case that stops the recursion, otherwise it will continue indefinitely and cause a stack overflow.

递归是一种函数调用自身来解决同一问题的较小实例的技术。每个递归算法必须有一个停止递归的基准情形，否则它将无限继续下去并导致栈溢出。

Each recursive call is placed on the call stack, which stores return addresses, parameters and local variables. When the base case is reached, the calls unwind and return values are combined. This stack use is the main memory cost of recursive algorithms.

每次递归调用都会被放入调用栈中，调用栈存储返回地址、参数和局部变量。当到达基准情形时，调用开始逐层返回并合并结果。这种栈的使用是递归算法的主要内存开销。

Recursion produces elegant solutions for problems with self-similar structure, such as traversing trees, calculating factorials and performing merge sort. However, deeply recursive solutions can be less efficient than iterative versions if the stack grows too large.

递归为具有自相似结构的问题提供了优雅的解决方案，例如遍历树、计算阶乘和执行归并排序。然而，如果栈增长过大，深度递归的解决方案可能比迭代版本效率更低。

9. Graph Traversal and Pathfinding Algorithms | 图遍历与路径查找算法

A graph consists of vertices connected by edges. Many real-world systems can be modelled as graphs, including road networks, social networks and computer networks. Graph algorithms explore these structures to find routes or relationships.

图由顶点和连接顶点的边组成。许多现实世界系统都可以建模为图，包括道路网络、社交网络和计算机网络。图算法探索这些结构以寻找路径或关系。

Depth-first search follows one branch as far as possible before backtracking, while breadth-first search explores all neighbours level by level. Breadth-first search finds the shortest path in an unweighted graph; depth-first search is useful for exploring all reachable nodes.

深度优先搜索沿一个分支尽可能深入，然后回溯；广度优先搜索逐层探索所有邻居。广度优先搜索可以在无权图中找到最短路径；深度优先搜索适合探索所有可达节点。

Dijkstra’s algorithm finds the shortest path in a weighted graph with non-negative edge weights. It repeatedly selects the unvisited vertex with the smallest known distance and relaxes its neighbours. A* improves on Dijkstra by using a heuristic estimate of the remaining distance to the goal, guiding the search more directly.

Dijkstra 算法在具有非负边权的加权图中查找最短路径。它反复选择已知距离最小的未访问顶点，并松弛其邻居。A* 通过使用到目标的剩余距离的启发式估计来改进 Dijkstra，使搜索更有方向性。

Edexcel candidates should understand where these algorithms are used. For example, satellite navigation systems use A* or Dijkstra, while web crawlers may use breadth-first search to index pages.

Edexcel 考生应了解这些算法的应用场景。例如，卫星导航系统使用 A* 或 Dijkstra，而网络爬虫可能使用广度优先搜索来索引页面。

10. Intractability and Heuristics | 难解性与启发式方法

Some problems have no known polynomial-time algorithm, which means the time required can grow explosively with input size. The travelling salesman problem is a classic example: finding the shortest tour that visits every city exactly once is computationally very difficult as the number of cities increases.

有些问题没有已知的多项式时间算法，这意味着所需时间可能随输入规模急剧增长。旅行商问题是一个经典例子：随着城市数量增加，找到恰好访问每个城市一次的最短巡回路线在计算上非常困难。

Problems are often classified as P if they can be solved in polynomial time, and NP if a solution can be verified in polynomial time. The question of whether P equals NP is unresolved, but it drives much of theoretical computer science.

问题通常分为：如果可以在多项式时间内解决，则属于 P 类；如果解可以在多项式时间内验证，则属于 NP 类。P 是否等于 NP 的问题尚未解决，但它推动了理论计算机科学的许多研究。

For intractable problems, heuristics provide approximate solutions that are good enough in practice. A heuristic is a rule of thumb, such as always visiting the nearest unvisited city, which does not guarantee the optimal solution but reaches a reasonable one quickly.

对于难解问题，启发式方法提供在实际中足够好的近似解。启发式是一种经验法则，例如总是访问最近的未访问城市，它不保证最优解，但能快速得到合理的结果。

Heuristics trade optimality for speed. They are widely used in routing, scheduling, artificial intelligence and game playing, where finding an exact answer would take far too long.

启发式以牺牲最优性来换取速度。它们广泛用于路线规划、调度、人工智能和游戏中，在这些领域找到精确答案耗时太长。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Algorithms | 算法