📚 Algorithms | 算法
Algorithms form the core of computer science, and a solid grasp of algorithmic thinking is essential for any A-Level student. In this article, we break down key algorithmic concepts as outlined by the Edexcel specification, from simple search and sort routines to graph traversal and algorithm efficiency.
算法构成了计算机科学的核心，掌握算法思维对每一位 A-Level 学生都至关重要。本文根据 Edexcel 考试大纲，逐一梳理关键算法概念，从基础的搜索与排序算法，到图遍历和算法效率分析。
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. The key properties include finiteness (it must terminate), definiteness (each step is clear), input, output, and effectiveness.
算法是一个有限的、定义明确且无歧义的指令序列，旨在解决特定问题或执行计算。其关键特性包括有穷性（必须终止）、确定性（每一步定义清晰）、输入、输出和有效性。
Algorithms are independent of programming languages. They can be expressed in natural language, pseudocode, or flowcharts. A good algorithm is correct, efficient, and easy to understand.
算法独立于编程语言。它们可以用自然语言、伪代码或流程图来表达。一个好的算法应当正确、高效且易于理解。
2. Representing Algorithms | 算法的表示方法
Pseudocode uses structured English-like statements to describe an algorithm without strict syntax. It allows designers to focus on logic rather than language-specific details. Typical constructs include IF...THEN...ELSE, FOR...NEXT, WHILE...ENDWHILE, and INPUT/OUTPUT.
伪代码使用类似英语的结构化语句来描述算法，无需严格遵守语法。它让设计者能够专注于逻辑，而非语言特有的细节。常见结构包括 IF...THEN...ELSE、FOR...NEXT、WHILE...ENDWHILE 以及 INPUT/OUTPUT。
Flowcharts provide a graphical representation using standard symbols: ovals for start/stop, parallelograms for input/output, rectangles for processes, and diamonds for decisions. Arrows show the flow of control.
流程图使用标准符号进行图形化表示：椭圆形表示开始/结束，平行四边形表示输入/输出，矩形表示处理过程，菱形表示判断。箭头指示控制流的方向。
3. Linear Search | 线性搜索
The linear search algorithm scans each element of a list sequentially until the target value is found or the end of the list is reached. It works on both sorted and unsorted data.
线性搜索算法按顺序逐一扫描列表中的每个元素，直到找到目标值或到达列表末尾。它适用于已排序和未排序的数据。
In the worst case, the target is at the end or absent, requiring n comparisons for a list of size n. Thus the time complexity is O(n). Linear search is simple but inefficient for large datasets.
在最坏情况下，目标值位于末尾或不存在，对于大小为 n 的列表需要 n 次比较。因此时间复杂度为 O(n)。线性搜索实现简单，但对于大型数据集效率较低。
4. 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. If they are not equal, it discards the half in which the target cannot lie and continues on the remaining half.
二分搜索应用于已排序列表，通过反复将搜索区间一分为二进行查找。它将目标值与中间元素进行比较。如果不相等，则排除目标值不可能存在的半区，继续在另一半区搜索。
Each comparison halves the list size, giving a worst‑case time complexity of O(log n). Binary search is much faster than linear search for large n, but requires the data to be sorted first.
每次比较将列表大小减半，最坏情况下的时间复杂度为 O(log n)。对于较大的 n，二分搜索比线性搜索快得多，但要求数据预先完成排序。
5. Bubble Sort | 冒泡排序
Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.
冒泡排序反复遍历列表，比较相邻元素，如果顺序错误则交换它们。遍历过程不断重复，直到不再需要交换，此时列表已完成排序。
After each pass, the largest unsorted element 'bubbles' to its correct position at the end. Bubble sort has a worst‑case and average time complexity of O(n²), making it inefficient on large lists.
每趟遍历后，最大的未排序元素会“冒泡”到其正确的末尾位置。冒泡排序的最坏和平均时间复杂度为 O(n²)，因此在大型列表上效率较低。
6. Insertion Sort | 插入排序
Insertion sort builds the final sorted array one item at a time. It takes each element from the unsorted part and inserts it into its correct position within the sorted part by shifting larger elements to the right.
插入排序每次构建最终已排序数组的一个元素。它取出未排序部分的一个元素，通过将较大元素向右移动，将其插入到已排序部分的正确位置。
For nearly sorted data, insertion sort performs well with O(n) best‑case time. However, the average and worst‑case complexity is O(n²). It is a stable sort and works efficiently on small datasets.
对于近似已排序的数据，插入排序表现良好，最佳情况时间复杂度为 O(n)。但其平均和最坏情况复杂度为 O(n²)。插入排序是一种稳定排序，在小型数据集上效率较高。
7. Merge Sort | 归并排序
Merge sort is a divide‑and‑conquer algorithm. It splits the list into two halves, recursively sorts each half, and then merges the two sorted halves into a single sorted list.
归并排序是一种分治算法。它将列表分成两半，递归地对每一半进行排序，然后将两个已排序的半区合并为一个已排序的列表。
The merging process compares the smallest remaining elements of each half and copies the smaller one to the output. Merge sort has a time complexity of O(n log n) in all cases, which makes it much faster than O(n²) algorithms for large n. However, it requires additional memory for the merging step (O(n) space).
合并过程比较两个半区中各自最小的剩余元素，并将较小的元素复制到输出。归并排序在所有情况下的时间复杂度均为 O(n log n)，这使得它在处理大规模数据时远快于 O(n²) 算法。不过，合并步骤需要额外的内存空间（O(n) 空间复杂度）。
8. Quick Sort | 快速排序
Quick sort also uses the divide‑and‑conquer strategy. It selects a 'pivot' element and partitions the list into two sub‑lists: elements less than the pivot and elements greater than the pivot. It then recursively sorts the sub‑lists.
快速排序同样采用分治策略。它选择一个“基准”元素，将列表划分为两个子列表：小于基准的元素和大于基准的元素。然后递归地对子列表进行排序。
The choice of pivot greatly affects performance. In the average case, quick sort runs in O(n log n) time, but the worst case (e.g., already sorted data with a poor pivot choice) degrades to O(n²). It is an in‑place sorting algorithm, requiring only O(log n) extra space for the recursion stack.
基准的选择对性能影响很大。在平均情况下，快速排序的运行时间为 O(n log n)，但最坏情况（如已排序数据且基准选择不当）会退化到 O(n²)。它是一种原地排序算法，仅需 O(log n) 的额外空间用于递归栈。
9. Algorithm Efficiency and Big O Notation | 算法效率与大 O 表示法
Big O notation describes the upper bound of an algorithm's time or space requirement as the input size grows. It characterises the worst‑case complexity and allows us to compare algorithms independently of hardware or implementation.
大 O 表示法描述了随着输入规模增长，算法时间或空间需求的上限。它表示最坏情况下的复杂度，使我们能够在不考虑硬件或实现细节的情况下比较算法。
Common complexities include: O(1) – constant time; O(log n) – logarithmic time (e.g., binary search); O(n) – linear time (e.g., linear search); O(n log n) – linearithmic time (e.g., merge sort); O(n²) – quadratic time (e.g., bubble sort). Understanding these categories helps in choosing the right algorithm for a given problem.
常见的复杂度包括：O(1) – 常数时间；O(log n) – 对数时间（如二分搜索）；O(n) – 线性时间（如线性搜索）；O(n log n) – 线性对数时间（如归并排序）；O(n²) – 平方时间（如冒泡排序）。理解这些分类有助于针对特定问题选择合适的算法。
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Space complexity is also critical, especially on memory‑constrained devices. An in‑place algorithm like quick sort uses minimal extra memory, whereas merge sort needs additional space proportional to the input size.
空间复杂度同样关键，尤其是在内存受限的设备上。像快速排序这样的原地算法仅使用极少的额外内存，而归并排序则需要与输入规模成比例的额外空间。
10. Recursion | 递归
Recursion is a technique in which a function calls itself to solve a smaller instance of the same problem. Every recursive solution must have a base case to stop the recursion and a recursive case that moves towards the base case.
递归是一种函数调用自身以解决同一问题的更小实例的技术。每个递归解法都必须有一个基准情况来终止递归，以及一个向基准情况逼近的递归情况。
Recursion is used in many algorithms, such as merge sort, quick sort, depth‑first search, and tree traversals. It often leads to elegant code, but may incur more memory overhead due to the call stack. An iterative equivalent can sometimes avoid stack overflow issues.
递归用于许多算法，如归并排序、快速排序、深度优先搜索和树的遍历。它通常能使代码简洁优雅，但可能由于调用栈而产生更多的内存开销。迭代等价实现有时可以避免栈溢出问题。
11. Graph Traversal: BFS and DFS | 图的遍历：广度优先搜索与深度优先搜索
Graph traversal algorithms systematically visit every vertex in a graph. The two fundamental methods are Breadth‑First Search (BFS) and Depth‑First Search (DFS).
图遍历算法系统地访问图中的每个顶点。两种基本方法是广度优先搜索（BFS）和深度优先搜索（DFS）。
BFS explores the graph level by level. Starting from a source node, it visits all neighbours first, then neighbours of neighbours, and so on. It uses a queue data structure. BFS can find the shortest path in an unweighted graph.
BFS 按层次探索图。从源节点开始，它首先访问所有直接邻居，然后是邻居的邻居，依此类推。它使用队列数据结构。BFS 可以在无权图中找到最短路径。
DFS explores as far along a branch as possible before backtracking. It uses a stack (or recursion) and can be implemented iteratively or recursively. DFS is useful for detecting cycles, topological sorting, and path‑finding in mazes.
DFS 先沿着一个分支尽可能深入，然后再回溯。它使用栈（或递归），可以通过迭代或递归实现。DFS 在检测环、拓扑排序以及迷宫寻路等问题中非常有用。
Both algorithms have a time complexity of O(V + E) for an adjacency list representation, where V is the number of vertices and E the number of edges.
对于邻接表表示，两种算法的时间复杂度均为 O(V + E)，其中 V 为顶点数，E 为边数。
12. Shortest Path Algorithms: Dijkstra and A* | 最短路径算法：Dijkstra 与 A*
Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non‑negative edge weights. It maintains a priority queue of unvisited nodes, always expanding the node with the smallest tentative distance.
Dijkstra 算法用于在具有非负边权的加权图中，找出从单一源节点到所有其他节点的最短路径。它维护一个未访问节点的优先队列，总是扩展临时距离最小的节点。
Its time complexity is O((V + E) log V) with a binary heap. Dijkstra fails if any edge weight is negative.
使用二叉堆时，其时间复杂度为 O((V + E) log V)。若存在负权边，Dijkstra 算法将失效。
n) + h(n), where g(n) is the actual cost from the start to node n and h(n) is the heuristic estimate. If the heuristic is admissible (never overestimates), A* is guaranteed to find the optimal path, often exploring fewer nodes than Dijkstra.
A* 算法通过引入启发式函数来估计到目标的剩余距离，从而扩展了 Dijkstra 算法。总估计代价 f(n) = g(n) + h(n)，其中 g(n) 是从起点到节点 n 的实际代价，h(n) 是启发式估计。若启发式函数是可接受的（从不低估实际代价），A* 算法保证找到最优路径，并且通常比 Dijkstra 探索更少的节点。
Both algorithms are widely used in routing, game AI, and network navigation.
这两种算法广泛应用于路径规划、游戏人工智能和网络导航。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图