📚 Year 13 Cambridge Computer Science Formula & Theorem Quick-Reference Handbook | 剑桥计算机13年级公式定理速查手册
This article provides a concise, bilingual reference of the most essential formulas, theorems, and performance figures required for the Cambridge International A Level Computer Science (Year 13) syllabus. Use it to reinforce your understanding of algorithmic complexity, Boolean logic, data structures, network addressing, encryption foundations, and processor architecture. Each section pairs an English explanation with a Chinese counterpart, followed by clear bullet points, tables, and centered key equations.
本文提供剑桥国际A Level计算机科学（13年级）课程大纲中最核心的公式、定理与性能数据的中英双语速查手册。通过它，你可以巩固对算法复杂度、布尔逻辑、数据结构、网络寻址、加密基础以及处理器架构的理解。每个小节均由英文和中文配套说明组成，并通过要点、表格和居中公式加以呈现。
1. Algorithmic Complexity & Big-O Notation | 算法复杂度与大O记号
The efficiency of an algorithm is described by its time and space complexity using Big-O notation, which expresses the upper bound on growth as input size n increases. The most common classes, from fastest to slowest growth, are listed below.
算法效率通过时间与空间复杂度来描述，采用大O记号表示当输入规模 n 增大时增长的上限。以下列出从最快增长到最慢增长的常见类别。
- O(1) – Constant time: independent of n.
- O(1) – 常数时间：与 n 无关。
- O(log n) – Logarithmic: typical of divide-and-conquer algorithms (e.g., binary search).
- O(log n) – 对数时间：常见于分治算法（如二分查找）。
- O(n) – Linear: one pass through data (e.g., linear search).
- O(n) – 线性时间：遍历一次数据（如线性搜索）。
- O(n log n) – Log-linear: efficient sorts (merge sort, heap sort, average case quick sort).
- O(n log n) – 线性对数时间：高效排序（归并排序、堆排序、快速排序平均情况）。
- O(n²) – Quadratic: nested loops (bubble sort, insertion sort).
- O(n²) – 平方时间：嵌套循环（冒泡排序、插入排序）。
- O(2ⁿ) – Exponential: many brute‑force recursive solutions.
- O(2ⁿ) – 指数时间：许多暴力递归解法。
- O(n!) – Factorial: exhaustive permutations (e.g., travelling salesman brute force).
- O(n!) – 阶乘时间：穷举排列（如旅行商问题暴力搜索）。
Space complexity follows the same notation, measuring the extra memory used as a function of n.
空间复杂度采用相同记号，衡量额外内存使用随 n 的变化。
2. Sorting Algorithms – Key Performance Metrics | 排序算法关键性能指标
The table below summarises the average and worst-case time complexities, space complexity, and stability of the sorting algorithms you need to know for the Cambridge syllabus.
下表汇总了剑桥课程大纲要求掌握的排序算法的平均和最坏情况时间复杂度、空间复杂度及稳定性。
| Algorithm | Average | Worst | Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No |
Merge sort is the only guaranteed O(n log n) worst-case comparison sort that is stable. Quick sort’s average case is very efficient, but its worst case occurs with a bad pivot (e.g., already sorted data).
归并排序是唯一保证最坏情况下 O(n log n) 且稳定的比较排序。快速排序平均效率很高，但若基准选取不佳（如已排序数据），则会退化至最坏情况。
3. Searching Algorithms | 搜索算法
Linear Search examines each element sequentially. Time complexity: O(n). It works on any list, sorted or unsorted. Binary Search repeatedly divides a sorted array in half. Time complexity: O(log n). The array must be sorted for binary search to function.
线性搜索顺序检查每个元素，时间复杂度 O(n)，适用于有序或无序列表。二分查找反复将有序数组分成两半，时间复杂度 O(log n)，前提是数组必须已排序。
The maximum number of comparisons in binary search on an array of size n is ⌈log₂(n+1)⌉ or approximately log₂ n.
对大小为 n 的数组进行二分查找，最大比较次数为 ⌈log₂(n+1)⌉，约等于 log₂ n。
Binary Search: mid = ⌊(low + high) / 2⌋
For a hash table lookup, under ideal conditions (no collisions) the average time complexity is O(1), but worst-case with poor hashing can degrade to O(n).
哈希表查找在理想无冲突情况下平均时间复杂度为 O(1)，但在哈希函数不佳时最坏可退化为 O(n)。
4. Boolean Algebra Laws | 布尔代数定律
These identities are essential for simplifying logic circuits and Boolean expressions. In the Cambridge syllabus, the set of laws is frequently examined.
这些恒等式对于化简逻辑电路和布尔表达式至关重要，在剑桥考试中经常出现。
| Law | OR form | AND form |
|---|---|---|
| Identity | A + 0 = A | A · 1 = A |
| Null (Annulment) | A + 1 = 1 | A · 0 = 0 |
| Idempotent | A + A = A | A · A = A |
| Complement | A + ¬A = 1 | A · ¬A = 0 |
| Double Negation | ¬(¬A) = A | |
| Commutative | A + B = B + A | A · B = B · A |
| Associative | A + (B + C) = (A + B) + C | A · (B · C) = (A · B) · C |
| Distributive | A · (B + C) = A·B + A·C | A + (B·C) = (A+B)·(A+C) |
| Absorption | A + (A·B) = A | A · (A + B) = A |
Here we use ‘+’ for OR, ‘·’ for AND, and ‘¬’ for NOT. The laws are dual: every OR law has a matching AND law obtained by swapping ‘+’ with ‘·’ and 0 with 1.
此处 ‘+’ 表示 OR，’·’ 表示 AND，’¬’ 表示 NOT。这些定律具有对偶性：将 ‘+’ 换成 ‘·’、0 换成 1，即可由 OR 定律得到对应的 AND 定律。
5. De Morgan’s Laws & Karnaugh Map Simplification | 德摩根定律与卡诺图化简
De Morgan’s laws allow conversion between the negation of a conjunction and a disjunction:
德摩根定律可实现合取取反与析取之间的转换：
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
Karnaugh maps (K-maps) provide a visual method for simplifying Boolean expressions of up to four variables. Adjacent cells differ by one variable; groups of 1, 2, 4, 8 etc. are formed to eliminate variables. The simplified SOP (Sum of Products) expression is read from the minimal coverage of the 1s.
卡诺图（K-map）提供了一种可视化方法，用于化简最多四个变量的布尔表达式。相邻单元格仅有一个变量不同；可将 1、2、4、8 等个 1 组合起来消除变量。化简后的 SOP（与或式）从对 1 的最小覆盖中读出。
For example, a 2-variable K-map can represent the expression F = A·¬B + A·B, which simplifies to A.
例如，一个二变量卡诺图可表示表达式 F = A·¬B + A·B，化简后得到 A。
6. Data Structures & Operations Complexity | 数据结构与操作复杂度
Understanding the time complexity of core operations on fundamental data structures helps in choosing the right one for a given task.
理解基本数据结构上核心操作的时间复杂度，有助于为特定任务选择合适的数据结构。
| Data Structure | Access | Search | Insert (avg) | Delete (avg) |
|---|---|---|---|---|
| Array (unsorted) | O(1) | O(n) | O(1) (end) | O(1) (end) |
| Sorted Array | O(1) | O(log n) | O(n) | O(n) |
| Stack / Queue | O(1) | O(n) | O(1) | O(1) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Binary Search Tree (balanced) |
O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table | N/A | O(1) | O(1) | O(1) |
Note that stacks support LIFO (Last In First Out) and queues support FIFO (First In First Out) – these behaviours define the data structure, not complexity. For graphs, representations include adjacency matrix (space O(V²)) and adjacency list (space O(V+E)).
注意，栈支持 LIFO（后进先出），队列支持 FIFO（先进先出）——这些行为定义了数据结构，而非复杂度。图的表示包括邻接矩阵（空间 O(V²)）和邻接表（空间 O(V+E)）。
7. Tree and Graph Traversals | 树与图遍历
For binary trees, three depth-first traversals are defined:
对于二叉树，定义了三种深度优先遍历：
- Pre-order: visit root, then left subtree, then right subtree.
- 前序遍历：访问根，再左子树，再右子树。
- In-order: left subtree, root, right subtree. (Produces sorted output in a binary search tree.)
- 中序遍历：左子树、根、右子树。（在二叉搜索树中产生有序输出。）
- Post-order: left subtree, right subtree, root. (Used to delete trees.)
- 后序遍历：左子树、右子树、根。（用于删除树。）
Breadth-first traversal uses a queue to visit nodes level by level. For graphs, depth-first search (DFS) uses a stack (or recursion), and breadth-first search (BFS) uses a queue. Both have time complexity O(V+E) when using adjacency lists.
广度优先遍历使用队列逐层访问节点。对于图，深度优先搜索（DFS）使用栈（或递归），广度优先搜索（BFS）使用队列。使用邻接表时，两者的时间复杂度均为 O(V+E)。
8. Network Subnetting & IP Addressing | 网络子网划分与IP寻址
An IPv4 address is 32 bits, usually written as four dotted decimal octets. The subnet mask determines the network and host portions. The number of usable host addresses in a subnet with n host bits is:
IPv4 地址为 32 位，通常用四个点分十进制八位组表示。子网掩码确定网络部分和主机部分。拥有 n 个主机位的子网中可用主机地址数为：
Usable hosts = 2ⁿ – 2
Subtracting 2 accounts for the network address (all host bits 0) and broadcast address (all host bits 1). For example, a /24 mask (255.255.255.0) has 8 host bits: 2⁸ – 2 = 254 usable addresses.
减去 2 是为了排除网络地址（主机位全 0）和广播地址（主机位全 1）。例如，/24 掩码（255.255.255.0）有 8 个主机位：2⁸ – 2 = 254 个可用地址。
CIDR notation prefix /x indicates the number of network bits. The subnet mask in dotted decimal is obtained by setting the first x bits to 1. Subnetting a larger network into smaller subnets follows the same power-of-two rules.
CIDR 表示法的前缀 /x 指示网络位的数量。点分十进制子网掩码通过将前 x 位设为 1 得到。将一个较大的网络划分为更小的子网遵循同样的 2 的幂次规则。
9. RSA Encryption & Number Theory Foundations | RSA加密与数论基础
RSA is an asymmetric encryption algorithm whose security relies on the difficulty of factoring large numbers. The key generation and encryption/decryption formulas are fundamental.
RSA 是一种非对称加密算法，其安全性依赖于大数分解的困难性。密钥生成和加密/解密公式是基础内容。
Key generation:
- Choose two large primes p and q.
- 选择两个大素数 p 和 q。
- Compute n = p × q; φ(n) = (p – 1)(q – 1).
- 计算 n = p × q；φ(n) = (p – 1)(q – 1)。
- Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
- 选择 e 满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。
- Determine d as the modular multiplicative inverse of e mod φ(n): e × d ≡ 1 (mod φ(n)).
- 求 d 使得 e × d ≡ 1 (mod φ(n))，即 e 模 φ(n) 的乘法逆元。
- Public key: (n, e); Private key: (n, d).
- 公钥：(n, e)；私钥：(n, d)。
Encryption: C = Mᵉ mod n
Decryption: M = Cᵈ mod n
Small example values are often used in exam questions to illustrate the mechanics of modular exponentiation.
考题中常使用较小的示例数值来说明模幂运算的机理。
10. Assembly Language & Addressing Modes | 汇编语言与寻址模式
In low-level programming, the CPU executes machine-code instructions. Assembly language mnemonics represent operations like LDR, STR, ADD, SUB (ARM-like or Little Man Computer style). The addressing mode dictates how the operand is interpreted.
在底层编程中，CPU 执行机器码指令。汇编语言助记符表示 LDR、STR、ADD、SUB 等操作（类似 ARM 或 LMC 小机箱计算机风格）。寻址模式决定了操作数的解读方式。
- Immediate: operand is a literal constant. e.g., ADD R1, #5.
- 立即寻址：操作数是字面常量，如 ADD R1, #5。
- Direct (Absolute): the operand is a memory address. e.g., LDR R2, 100.
- 直接寻址（绝对寻址）：操作数是内存地址，如 LDR R2, 100。
- Indirect: the operand specifies a register or memory location that holds the effective address.
- 间接寻址：操作数指定一个寄存器或内存位置，其中存放有效地址。
- Indexed: effective address = base register + offset. e.g., LDR R3, [R4, #8].
- 变址寻址：有效地址 = 基址寄存器 + 偏移量，如 LDR R3, [R4, #8]。
Understanding the number of memory accesses needed for each mode is critical for performance analysis.
理解每种寻址模式所需的内存访问次数，对于性能分析至关重要。
11. Database Normalisation & SQL | 数据库规范化与SQL
Normalisation reduces data redundancy and anomalies. The three normal forms needed for Cambridge A Level are:
规范化可减少数据冗余和异常。剑桥A Level需要掌握的三范式如下：
- 1NF: No repeating groups; every attribute contains atomic (indivisible) values. Create separate rows for multi-valued entries.
- 1NF：无重复组；每个属性包含原子值（不可再分）。为多值条目创建单独的行。
- 2NF: 1NF plus all non-key attributes are fully functionally dependent on the whole primary key (no partial dependencies).
- 2NF：1NF 且所有非主属性完全函数依赖于整个主键（无部分依赖）。
- 3NF: 2NF plus no transitive dependencies (non-key attributes depend only on the primary key, not on another non-key attribute).
- 3NF：2NF 且无传递依赖（非主属性只依赖于主键，不依赖于其他非主属性）。
Common SQL commands: SELECT … FROM … WHERE … ORDER BY … GROUP BY … (with HAVING), and joins (INNER JOIN, LEFT/RIGHT JOIN). Aggregation functions: COUNT, SUM, AVG, MAX, MIN.
常见 SQL 命令：SELECT … FROM … WHERE … ORDER BY … GROUP BY …（含 HAVING），以及连接（INNER JOIN、LEFT/RIGHT JOIN）。聚合函数：COUNT、SUM、AVG、MAX、MIN。
Normalisation is applied step-by-step, and denormalisation is sometimes used deliberately to improve query performance in data warehousing.
规范化逐步应用，而在数据仓库中有时会故意使用反规范化以提高查询性能。
12. Processor Architecture – Pipelining & Performance | 处理器架构——流水线与性能
Pipelining improves instruction throughput by overlapping the execution stages (fetch, decode, execute, memory access, write-back). The ideal speedup from a k-stage pipeline over a non-pipelined CPU, assuming equal stage time and no stalls, is:
流水线通过重叠指令的执行阶段（取指、译码、执行、访存、写回）来提高指令吞吐量。理想情况下，k 级流水线相对于非流水线 CPU 的加速比为：
Speedup ≈ k (when number of instructions is large)
In reality, pipeline hazards (data, control, structural) reduce this ideal speedup. Data forwarding and branch prediction are techniques used to minimise stalls.
现实中，流水线冒险（数据冒险、控制冒险、结构冒险）会降低这一理想加速比。数据前递和分支预测是用于减少停顿的技术。
The execution time of a program can be expressed as:
程序执行时间可表示为：
CPU time = (Instruction count × CPI) / Clock rate
Where CPI is the average clock cycles per instruction. Pipelining aims for a CPI close to 1 in the best case.
其中 CPI 为平均每条指令的时钟周期数。流水线旨在最优情况下使 CPI 接近 1。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导