Edexcel Year 13 Computer Science: Key Formulas & Theorems Quick Reference | Edexcel 计算机 Year 13 公式定理速查手册

📚 Edexcel Year 13 Computer Science: Key Formulas & Theorems Quick Reference | Edexcel 计算机 Year 13 公式定理速查手册

This revision card consolidates the essential formulas, theorems, and computational laws required for the Edexcel A Level Computer Science (Year 13) exam. Use it as a rapid recap to reinforce your understanding of algorithmic complexity, Boolean algebra, graph algorithms, networking, encryption, and database normalisation.

这份速查卡汇总了 Edexcel A Level 计算机科学（Year 13）考试所需的必备公式、定理与计算法则。将其用于快速回顾，以巩固你对算法复杂度、布尔代数、图算法、网络通信、加密和数据库范式的理解。

1. Time Complexity: Big O Notation | 时间复杂度：大O表示法

Big O notation describes the upper bound of an algorithm’s growth rate. It expresses how runtime or memory usage scales with input size n, ignoring constant factors.

大O表示法描述算法增长速率的上界。它表达运行时间或内存使用如何随输入规模 n 变化，并忽略常数因子。

• O(1) – Constant time: the operation takes the same amount of time regardless of n.

  O(1) – 常数时间：无论 n 多大，操作耗时相同。

• O(log n) – Logarithmic time: the time grows proportionally to the logarithm of n. Example: binary search.

  O(log n) – 对数时间：时间随 n 的对数比例增长。例如：二分查找。

• O(n) – Linear time: the time grows directly with n. Example: linear search.

  O(n) – 线性时间：时间直接随 n 增长。例如：线性搜索。

• O(n log n) – Log-linear time: typical of efficient sorting algorithms like merge sort.

  O(n log n) – 对数线性时间：常见于高效排序算法，如归并排序。

• O(n²) – Quadratic time: the time is proportional to the square of n. Example: bubble sort, insertion sort.

  O(n²) – 平方时间：时间与 n 的平方成正比。例如：冒泡排序、插入排序。

• O(2ⁿ) – Exponential time: time doubles with each additional element. Example: recursive Fibonacci without memoization.

  O(2ⁿ) – 指数时间：每增加一个元素，时间翻倍。例如：无记忆化的递归斐波那契。

Typical ranking: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

---

2. Sorting Algorithms Complexity | 排序算法复杂度

Sorting algorithms are fundamental. Their time and space complexities vary across best, average, and worst cases. Below is a summary table for the key sorts.

排序算法是基础。它们的时间与空间复杂度在最好、平均和最坏情况下各不相同。下表总结了关键排序算法。

Algorithm	Best	Average	Worst	Space
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)

Merge sort guarantees O(n log n) but requires additional O(n) memory. Quick sort is in‑place but degrades to O(n²) if the pivot is poorly chosen.

归并排序保证 O(n log n) 但需要额外的 O(n) 内存。快速排序是原地排序，但如果枢轴选择不当会退化至 O(n²)。

---

3. Search Algorithms Complexity | 搜索算法复杂度

Search algorithms locate a target element. The choice depends on whether the data is sorted.

搜索算法用于定位目标元素。选择依赖于数据是否有序。

• Linear Search: O(n) time, O(1) space. Works on unsorted data.

  线性搜索：O(n) 时间，O(1) 空间。适用于无序数据。

• Binary Search: O(log n) time, O(1) space for iterative version. Requires sorted data.

  二分查找：O(log n) 时间，迭代版本 O(1) 空间。要求数据有序。

• Binary Search Tree (balanced): O(log n) average, O(n) worst if unbalanced.

  二叉搜索树（平衡）：平均 O(log n)，最坏不平衡 O(n)。

• Hash Table lookup: O(1) average, O(n) worst due to collisions.

  哈希表查找：平均 O(1)，因冲突最坏 O(n)。

---

4. Data Structure Operations Complexity | 数据结构操作复杂度

This quick reference lists common operations for core data structures using average time complexity.

本速查表列出核心数据结构常用操作的平均时间复杂度。

Data Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Linked List	O(n)	O(n)	O(1)	O(1)
Stack / Queue	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)

For stacks and queues, insert/delete is O(1) because you only add/remove at the ends. Hash table O(1) assumes a good hash function with low collision.

栈和队列的插入/删除为 O(1)，因为你仅在端点操作。哈希表的 O(1) 假设有良好的散列函数和低冲突率。

---

5. Boolean Algebra Laws | 布尔代数定律

Boolean algebra is used to simplify logic circuits. The main laws are listed below. (A, B, C represent Boolean variables)

布尔代数用于化简逻辑电路。主要定律如下。（A, B, C 代表布尔变量）

• Identity: A + 0 = A, A · 1 = A

  恒等律：A + 0 = A，A · 1 = A

• Null (Annulment): A + 1 = 1, A · 0 = 0

  零律：A + 1 = 1，A · 0 = 0

• Idempotent: A + A = A, A · A = A

  幂等律：A + A = A，A · A = A

• Complement: A + ¬A = 1, A · ¬A = 0

  互补律：A + ¬A = 1，A · ¬A = 0

• Double Negation: ¬(¬A) = A

  双重否定律：¬(¬A) = A

• Commutative: A + B = B + A, A · B = B · A

  交换律：A + B = B + A，A · B = B · A

• Associative: (A + B) + C = A + (B + C), (A · B) · C = A · (B · C)

  结合律：(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)

  分配律：A · (B + C) = A·B + A·C，A + (B·C) = (A+B)·(A+C)

• Absorption: A + A·B = A, A·(A+B) = A

  吸收律：A + A·B = A，A·(A+B) = A

• De Morgan’s: ¬(A · B) = ¬A + ¬B, ¬(A + B) = ¬A · ¬B

  德摩根定律：¬(A · B) = ¬A + ¬B，¬(A + B) = ¬A · ¬B

Use De Morgan’s and distributive laws to convert between sum-of-products and product-of-sums forms.

利用德摩根定律和分配律可在“积之和”与“和之积”形式间转换。

---

6. Karnaugh Maps & Simplification | 卡诺图与化简

A Karnaugh map (K-map) is a visual tool for simplifying Boolean expressions of up to 4 variables. Cells are arranged so that adjacent cells differ by only one variable, enabling grouping of 1s in powers of two (1,2,4,8).

卡诺图（K-map）是一种化简多达 4 个变量布尔表达式的可视化工具。格子排列使得相邻格子仅相差一个变量，从而可将 1 按 2 的幂次方（1,2,4,8）分组。

Steps: 1) Fill in the K-map from truth table. 2) Circle groups of adjacent 1s (wrapping allowed). 3) Each group corresponds to a product term where variables that change are eliminated. 4) OR the simplified terms.

步骤：1) 根据真值表填充卡诺图。2) 圈出相邻的 1 组（允许环绕边界）。3) 每组对应一个乘积项，其中发生变化的变量被消除。4) 将化简项求或。

For 3 variables: 8 cells; for 4 variables: 16 cells.

---

7. Graph Algorithms: Dijkstra & A* | 图算法：Dijkstra 与 A*

Dijkstra’s algorithm finds the shortest path from a start node to all others in a graph with non‑negative weights.

Dijkstra 算法在非负权重的图中找出从起点到所有其他节点的最短路径。

It uses a priority queue and repeatedly selects the unvisited node with the smallest tentative distance, updating neighbours. Time complexity with a binary heap: O((V + E) log V).

它采用优先队列，反复选择具有最小暂定距离的未访问节点，并更新邻居。使用二叉堆的时间复杂度：O((V + E) log V)。

A* is an informed search algorithm that uses a heuristic h(n) (estimated cost to goal) in addition to the actual cost g(n). Its evaluation function is f(n) = g(n) + h(n).

A* 是一种知情搜索算法，除了实际代价 g(n) 外，还使用启发函数 h(n)（估计到目标的代价）。其评估函数为 f(n) = g(n) + h(n)。

For A* to be optimal, the heuristic must be admissible (never overestimates the true cost).

为使 A* 最优，启发函数必须可采纳（不高估实际代价）。

---

8. Computational Theory: Halting Problem | 计算理论：停机问题

The Halting Problem asks whether a given program will finish running or run forever on a particular input. Turing proved that a general algorithm to solve the halting problem for all possible program‑input pairs cannot exist — it is undecidable.

停机问题询问：给定程序对于特定输入是否会终止或永远运行。图灵证明，不存在一个通用算法能为所有可能的程序-输入对判定停机——它是不可判定的。

The proof uses a diagonalisation argument: assume a halting oracle H(P, I) exists, then construct a paradoxical program that contradicts H.

证明采用对角化论证：假设存在一个停机预言机 H(P, I)，然后构造一个会导致矛盾的悖论程序。

Recognising decidable vs undecidable problems is a key part of the theory of computation.

识别可判定与不可判定问题是计算理论的关键部分。

---

9. Database Normalisation | 数据库范式

Normalisation reduces data redundancy and prevents update anomalies. The three normal forms required for Edexcel A Level are:

范式化减少数据冗余并防止更新异常。Edexcel A Level 要求掌握的三个范式为：

• 1NF: A table is in First Normal Form if it has no repeating groups and each cell contains atomic values. Every attribute must be single-valued.

  1NF：若表没有重复组且每格包含原子值，则属于第一范式。每个属性必须是单值的。

• 2NF: A table is in Second Normal Form if it is in 1NF and every non‑key attribute is fully functionally dependent on the whole primary key (no partial dependencies).

  2NF：若满足 1NF 且每个非键属性完全函数依赖于整个主键（不存在部分依赖），则属于第二范式。

• 3NF: A table is in Third Normal Form if it is in 2NF and no non‑key attribute is transitively dependent on the primary key (i.e., no non‑key attribute depends on another non‑key).

  3NF：若满足 2NF 且没有非键属性传递依赖于主键（即非键属性不依赖于其他非键属性），则属于第三范式。

Functional dependency X → Y means that a value of X uniquely determines a value of Y.

函数依赖 X → Y 表示 X 的值唯一确定 Y 的值。

---

10. Network Performance Formulas | 网络性能公式

Network performance is measured using transmission time, propagation delay, and throughput.

网络性能通过传输时间、传播延迟和吞吐量衡量。

Transmission time = Data size (bits) / Bandwidth (bps)

Transmission time is the time to push all bits onto the wire.

传输时间是将所有比特推入线路所需的时间。

Propagation delay = Distance / Propagation speed

Propagation delay is the time for one bit to travel from sender to receiver.

传播延迟是一个比特从发送方到达接收方的时间。

Total latency = Transmission time + Propagation delay + Queuing + Processing

总延迟 = 传输时间 + 传播延迟 + 排队时延 + 处理时延。

Packet delivery time = Packet size / Bandwidth

---

11. Floating Point Binary Representation | 浮点数二进制表示

A floating‑point number is stored as mantissa × 2^exponent. The mantissa is typically normalised so the most significant bit is 1 (for positive) or 0 (for negative) immediately after the sign bit, maximising precision.

浮点数以 尾数 × 2^指数 的形式存储。尾数通常经过规格化，使正数符号位后紧随的最高位为 1，负数紧随 0，以最大化精度。

Convert decimal to binary: write the integer and fractional parts separately, combine, then adjust exponent until the binary point is right after the first 1 (normalisation).

十进制转换为二进制：分别写出整数和小数部分，组合后调整指数直到小数点紧跟第一个 1（规格化）。

For example, 5.75₁₀ = 101.11₂ = 1.0111 × 2². In a 8‑bit mantissa with 4‑bit exponent, the stored mantissa would be 10111000 and exponent 0010 (but actual representation depends on the format, including sign bits and bias).

例如，5.75₁₀ = 101.11₂ = 1.0111 × 2²。在 8 位尾数 4 位指数格式中，尾数存储为 10111000，指数 0010（实际表示依赖于格式，包括符号位和偏置）。

---

12. RSA Encryption | RSA 加密

RSA is an asymmetric encryption algorithm relying on the difficulty of factoring large composites.

RSA 是一种非对称加密算法，依赖于分解大合数的困难性。

• Choose two large primes p and q. Compute n = p × q and φ(n) = (p‑1)(q‑1).

  选择两个大素数 p 和 q。计算 n = p × q 及 φ(n) = (p‑1)(q‑1)。

• Select public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. Common choice: 65537.

  选择公钥指数 e，满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。常见选择：65537。

• Compute private exponent d as the modular multiplicative inverse of e modulo φ(n), i.e., e × d ≡ 1 (mod φ(n)).

  计算私钥指数 d 为 e 关于模 φ(n) 的乘法逆元，即 e × d ≡ 1 (mod φ(n))。

• Encryption: ciphertext C = M^e mod n. Decryption: M = C^d mod n.

  加密：密文 C = M^e mod n。解密：M = C^d mod n。

The security relies on the fact that deriving d from (n, e) requires φ(n), which in turn requires factoring n.

安全性依赖于从 (n, e) 推导 d 需要 φ(n)，而计算 φ(n) 又需要分解 n。

Example: p=61, q=53 → n=3233, φ=3120. Let e=17 → d=2753 (since 17×2753 mod 3120 = 1).

---

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

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