算法 (Algorithms) — A-Level Computer Science 学习指南

适合谁：A-Level Computer Science 参加 A-Level Computer Science 的考生。

覆盖内容：伪代码与流程图、冒泡/插入排序算法、线性/二分搜索算法、时间复杂度基础、手动算法追踪全部考纲要求子主题。

前置知识：基础编程概念；Python / Java / VB 任一种。

关于练习题：下文「练习题」一节的所有题目均为我们按 A-Level Computer Science 风格编写的原创题目 (original problems)，仅用于教学。它们不是 Cambridge International 真题的复制，措辞、数值或语境可能不同。请把它们当作练手用；评分细则请对照 Cambridge 官方 mark scheme。

1. 什么是算法（Algorithms）？

算法（Algorithm）是计算机科学的核心概念，指为解决特定问题设计的有序、明确、可执行、有限的操作步骤，同一个问题可以有多种算法实现，你需要根据效率、实现难度等维度选择最优方案。 本章节是A-Level Computer Science的核心基础考点，在Paper 1理论题、Paper 2编程题中均会考察，占比约10%-15%，常见题型包括伪代码编写、算法追踪、复杂度判断等。

2. 伪代码与流程图（Pseudocode and Flowcharts）

算法有两种考纲认可的标准描述方式，不需要你用特定编程语言的严格语法，只要逻辑清晰符合规范即可：

伪代码（Pseudocode）

介于自然语言和编程语言的半结构化描述，考纲统一要求使用标准关键字：INPUT（输入）、OUTPUT（输出）、IF-THEN-ELSE（分支）、WHILE/FOR（循环），所有结构必须加对应的闭合关键字（ENDIF/ENDFOR/ENDWHILE）。 示例：输入两个数输出较大值的伪代码：

INPUT num1, num2
IF num1 > num2 THEN
 OUTPUT num1
ELSE
 OUTPUT num2
ENDIF

流程图（Flowchart）

用图形符号表示算法逻辑，常用符号包括：椭圆（起止框）、平行四边形（输入输出框）、矩形（处理框）、菱形（判断框）、箭头（流程线）。上述比较大小的算法流程为：开始→输入两个数→判断num1>num2？→是则输出num1，否则输出num2→结束。

3. 排序算法（Sorting Algorithms）：冒泡、插入排序

排序算法是将无序数据序列按指定规则（升序/降序）调整为有序序列的算法，考纲要求掌握两种基础实现：

冒泡排序（Bubble Sort）

核心逻辑：重复遍历待排序序列，相邻元素两两比较，若顺序错误则交换，每轮遍历会把当前最大/最小的元素"冒泡"到序列末尾，直到某轮没有交换发生，说明排序完成。 示例：对序列[3,1,4,2]升序排序的第一轮：

• 3和1比较，顺序错误交换→[1,3,4,2]
• 3和4比较，顺序正确不交换
• 4和2比较，顺序错误交换→[1,3,2,4] 第一轮结束，最大元素4已移动到末尾。

插入排序（Insertion Sort）

核心逻辑：将序列分为「已排序」和「未排序」两部分，每次从未排序部分取第一个元素，插入到已排序部分的正确位置，直到所有元素都被处理。 示例：对序列[3,1,4,2]升序排序：

1. 初始已排序部分：[3]，未排序部分：[1,4,2]
2. 取1插入到3前→已排序[1,3]，未排序[4,2]
3. 取4插入到末尾→已排序[1,3,4]，未排序[2]
4. 取2插入到1和3之间→最终有序序列[1,2,3,4]

4. 搜索算法（Searching Algorithms）：线性、二分搜索

搜索算法是在数据序列中查找特定目标元素的算法，考纲要求掌握两种：

线性搜索（Linear Search）

也叫顺序搜索，核心逻辑：从序列第一个元素开始逐个和目标比较，直到找到目标元素或遍历完整个序列。优点是无需序列有序，缺点是效率低。 示例：在序列[2,5,1,8,3]中查找8，依次比较2≠8、5≠8、1≠8、8=8，返回索引3。

二分搜索（Binary Search）

也叫折半搜索，核心逻辑：要求序列必须已排序，每次取中间元素和目标比较，若相等则找到；若目标更小则在左半部分继续搜索，更大则在右半部分继续搜索，每次排除一半元素，效率远高于线性搜索。 示例：在升序序列[1,2,3,5,8]中查找8：

1. 左边界left=0，右边界right=4，中间索引mid=(0+4)//2=2，对应元素3，8>3，搜索右半部分
2. 左边界更新为3，右边界4，mid=(3+4)//2=3，对应元素5，8>5，搜索右半部分
3. 左边界更新为4，右边界4，mid=4，对应元素8，找到，返回索引4。

5. 时间复杂度基础（Time Complexity Intuition）

时间复杂度是衡量算法运行效率的核心指标，考纲要求用大O表示法（Big O Notation）判断基础算法的最坏情况运行时间，即输入规模为n时的最大运算次数：

• $O(1)$：常数时间，运算次数和n无关，比如直接访问数组指定位置的元素
• $O(n)$：线性时间，运算次数和n成正比，比如线性搜索最坏情况（目标在最后或不存在）
• $O(n^2)$：平方时间，运算次数和n的平方成正比，比如冒泡、插入排序最坏情况（序列完全逆序）
• $O(\log n)$：对数时间，运算次数随n增大增长极慢，比如二分搜索最坏情况 考纲不需要你严格推导复杂度，只要能准确判断上述基础算法的复杂度即可。

6. 手动算法追踪（Tracing Algorithms by Hand）

手动算法追踪是考官每年必考的题型，占分约5-8分，要求你跟着给定的算法步骤，一步步记录所有变量、数组的变化，通常用变量表（Trace Table）完成。 示例：追踪对[5,2,7,1]升序冒泡排序的第一轮过程，变量表如下：

7. 常见陷阱（Common Pitfalls）

1. 错误做法：在无序序列上使用二分搜索。原因：只记得二分搜索效率高，忽略了必要前提。正确做法：二分搜索的前置条件是序列已排序，无序序列只能使用线性搜索。
2. 错误做法：冒泡排序每轮都遍历整个序列，包括已经排好的末尾元素。原因：忘记每轮已经把当前最大元素移动到末尾，不需要重复比较。正确做法：第k轮冒泡排序只需要遍历前n-k个元素，若某轮没有交换可以直接提前终止。
3. 错误做法：写伪代码时省略ENDIF/ENDFOR等闭合关键字。原因：平时写Python等不需要显式闭合的编程语言形成了习惯。正确做法：A-Level考纲的伪代码规范要求所有分支、循环结构必须加对应的闭合关键字，否则会被扣语法分。
4. 错误做法：计算时间复杂度时按最好情况计算。原因：混淆了最坏情况和平均情况的要求。正确做法：考纲所有时间复杂度的题目默认要求最坏情况的大O表示，不要按最好情况作答。

8. 练习题（A-Level Computer Science 风格）

题目1

对升序序列[3,7,12,19,25,31,40]用二分搜索查找元素19，写出完整步骤。 解答： 步骤1：初始化左边界left=0，右边界right=6 步骤2：计算中间索引mid=(0+6)//2=3，对应元素为19，和目标值相等，查找成功，返回索引3。

题目2

给出无序序列[4,1,5,2,3]，写出插入排序升序排列的完整过程，列出每一步的已排序和未排序部分。 解答：

1. 初始：已排序[4]，未排序[1,5,2,3]
2. 取1插入到4前：已排序[1,4]，未排序[5,2,3]
3. 取5插入到末尾：已排序[1,4,5]，未排序[2,3]
4. 取2插入到1和4之间：已排序[1,2,4,5]，未排序[3]
5. 取3插入到2和4之间：已排序[1,2,3,4,5]，排序完成。

题目3

判断以下三个算法的最坏情况时间复杂度：a) 插入排序 b) 线性搜索 c) 二分搜索 解答： a) 插入排序最坏情况为序列完全逆序，每个元素都要移动到已排序部分的最前面，时间复杂度为$O(n^2)$ b) 线性搜索最坏情况为目标元素不存在或在序列末尾，需要遍历所有元素，时间复杂度为$O(n)$ c) 二分搜索最坏情况为目标元素不存在，每次排除一半元素，最多需要${\log }_{2}n$次比较，时间复杂度为$O(\log n)$

9. 速查表（Quick Reference Cheatsheet）

10. 接下来怎么学

本章节的算法知识是后续数据结构（数组、链表、栈、队列等）、递归算法、进阶排序搜索算法的基础，在Paper 2的编程题和Paper 4的理论题中都会结合其他考点综合考察，你需要熟练掌握每种算法的手动追踪和伪代码编写，才能应对综合题型。 如果你在练习过程中遇到任何考点疑问、题目不会做，都可以随时到小欧提问，我们会为你提供针对性的讲解和练习指导。

本指南内容对齐 CIE 剑桥国际 AS & A Level 计算机科学 9618 考纲。OwlsAi 与 Cambridge Assessment International Education 无附属关系。