📚 Year 12 Edexcel Computer Science: Formula & Theorem Quick Reference Handbook | Year 12 Edexcel 计算机：公式定理速查手册
This quick reference handbook brings together the key formulas, theorems, and laws that every Year 12 Edexcel Computer Science student needs at their fingertips. From Boolean algebra and Karnaugh maps to time complexity and floating‑point arithmetic, the following sections condense essential theory into a clear, bilingual resource designed for rapid revision and deeper understanding.
这本速查手册汇集了每位 Year 12 Edexcel 计算机科学学生都需要掌握的关键公式、定理和定律。从布尔代数与卡诺图，到时间复杂度与浮点运算，以下各节将核心理论浓缩为一份清晰的双语资源，旨在帮助快速复习和深入理解。
1. Big‑O Time Complexity | 大 O 时间复杂度
Big‑O notation describes the upper bound of an algorithm’s running time or space requirement as the input size n grows. It focuses on the dominant term and ignores constants, giving a high‑level view of efficiency.
大 O 表示法描述了随着输入规模 n 增长，算法运行时间或空间需求的上界。它关注主导项并忽略常数，从高层次衡量效率。
O(1) – Constant time: execution time does not depend on input size. Example: accessing an array element by index.
O(1) – 常数时间：执行时间不依赖输入规模。例如：通过索引访问数组元素。
O(log n) – Logarithmic time: often seen in binary search or balanced tree operations where the problem size halves each step.
O(log n) – 对数时间：常见于二分查找或平衡树操作，每一步问题规模减半。
O(n) – Linear time: a single loop over n elements. Example: linear search.
O(n) – 线性时间：单层循环遍历 n 个元素。例如：线性搜索。
O(n log n) – Linearithmic time: typical of efficient sorting algorithms like merge sort and quicksort (average case).
O(n log n) – 线性对数时间：典型的高效排序算法如归并排序和快速排序（平均情况）。
O(n²) – Quadratic time: nested loops over n items, e.g. bubble sort, insertion sort (worst case).
O(n²) – 平方时间：两层嵌套循环遍历 n 个元素，例如冒泡排序、插入排序（最坏情况）。
O(2ⁿ) – Exponential time: often arises in brute‑force combinatorial problems; extremely slow for large n.
O(2ⁿ) – 指数时间：常见于暴力组合问题；对大规模 n 极慢。
2. Boolean Algebra Laws | 布尔代数定律
Boolean algebra operates on variables that take only two values, true (1) and false (0). These laws are fundamental for simplifying logic circuits and expressions.
布尔代数处理只有真（1）和假（0）两种取值的变量。这些定律是简化逻辑电路与表达式的基础。
Key laws (where A, B, C ∈ {0,1}):
关键定律（A, B, C 取值为 0 或 1）：
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
3. De Morgan’s Theorems | 德摩根定理
De Morgan’s theorems provide a way to transform AND operations into OR operations (and vice versa) with the help of negation. They are essential for circuit simplification using NAND or NOR gates.
德摩根定理借助取反，将 AND 运算转换为 OR 运算（反之亦然）。它们对于使用与非门或或非门简化电路至关重要。
¬(A · B) = ¬A + ¬B
¬(A + B) = ¬A · ¬B
In words: the negation of a conjunction is the disjunction of the negations; the negation of a disjunction is the conjunction of the negations. These laws allow conversion of any logic circuit into one built solely from NAND or NOR gates.
用语言表达：与运算的取反等于各变量取反后的或运算；或运算的取反等于各变量取反后的与运算。这些定律允许将任何逻辑电路转换为仅由与非门或或非门构成的等价电路。
4. Simplification Using Karnaugh Maps | 卡诺图化简
A Karnaugh map (K‑map) is a visual tool for simplifying Boolean expressions of up to four variables. Adjacent cells differ by exactly one variable, allowing grouping of minterms to eliminate redundant literals.
卡诺图是一种用于化简最多四个变量的布尔表达式的可视化工具。相邻单元格仅在一个变量上不同，从而通过分组最小项来消除冗余文字。
Steps for a 2‑variable K‑map:
两变量卡诺图步骤：
Draw a 2×2 grid with rows labelled by A and columns by B (or vice versa).
绘制 2×2 网格，行标签为 A，列标签为 B（或相反）。
Fill in 1s for minterms where the output is 1.
在输出为 1 的最小项对应的单元格中填入 1。
Group adjacent 1s in rectangles of size 1, 2, or 4 (powers of 2).
将相邻的 1 按大小为 1、2 或 4（2 的幂）的矩形分组。
For each group, write the product term of variables that remain constant; drop variables that change.
对每一组，写出保持不变的变量的乘积项；发生变化的变量被消去。
For 3‑variable and 4‑variable maps, the principle extends using Gray code ordering along the axes. Karnaugh maps lead directly to minimal sum‑of‑products expressions.
对于三变量和四变量卡诺图，原理相同，只是坐标轴采用格雷码顺序。卡诺图可直接得出最简与或表达式。
5. Number Base Conversions | 数制转换公式
Computer science frequently uses binary, denary, and hexadecimal. The following methods and formulas ensure accurate conversions.
计算机科学频繁使用二进制、十进制和十六进制。以下方法和公式确保准确转换。
Binary to Denary: multiply each bit by its place value (power of 2) and sum.
二进制转十进制：将每一位乘以其位权（2 的幂）并求和。
Value = Σ (bᵢ × 2ⁱ) , bᵢ ∈ {0,1}
Denary to Binary: repeatedly divide the number by 2, recording the remainders. Read remainders from bottom to top.
十进制转二进制：反复除以 2，记录余数。从下往上读余数。
Hexadecimal to Denary: multiply each hex digit by 16 raised to its position.
十六进制转十进制：将每位十六进制数字乘以 16 的相应次幂。
Hex digits: 0‑9, A=10, B=11, C=12, D=13, E=14, F=15.
十六进制数字：0‑9，A=10，B=11，C=12，D=13，E=14，F=15。
Binary to Hex: group binary digits in fours from the right, then convert each group.
二进制转十六进制：从右开始每四位二进制分组，然后转换每组。
6. Floating‑Point Representation & Normalisation | 浮点数表示与规范化
Real numbers are stored in a mantissa‑exponent form, similar to scientific notation. In binary floating‑point, a number is expressed as:
实数以类似科学计数法的尾数-指数形式存储。在二进制浮点数中，一个数表示为：
Value = M × 2ᴱ
Where M is the mantissa (signed fraction in sign‑magnitude or two’s complement) and E is the exponent (biased or two’s complement integer).
其中 M 是尾数（有符号小数，采用原码或补码），E 是指数（移码或补码整数）。
Normalisation ensures maximum precision by removing leading zeros from the mantissa. For a positive normalised mantissa, the binary point is placed so that the first bit after the sign bit is a 1. For negative numbers in two’s complement, the first two bits are 10. Normalised form: 0.1xxx... or 1.0xxx...
规范化通过去除尾数中的前导零来确保最大精度。对于正规范化尾数，小数点的位置使得符号位之后的第一位为 1。对于补码表示的负数，前两位为 10。规范化形式：0.1xxx... 或 1.0xxx...
The range and precision depend on the bit allocation; Edexcel often uses a 12‑bit floating‑point with 8‑bit mantissa and 4‑bit exponent.
范围和精度取决于位数分配；Edexcel 常使用 12 位浮点数，8 位尾数和 4 位指数。
7. Two’s Complement and Overflow | 补码与溢出
Two’s complement is the standard representation for signed integers. Positive numbers have a leading 0; negative numbers are obtained by inverting all bits of the positive magnitude and adding 1.
补码是有符号整数的标准表示法。正数的最高位为 0；负数通过对正数按位取反后加 1 得到。
−N = ¬N + 1 (for an n‑bit word)
Range for n bits: from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.
n 位补码的范围：从 −2ⁿ⁻¹ 到 2ⁿ⁻¹ − 1。
ve and negative cannot overflow. The rule: overflow = Carry into MSB XOR Carry out of MSB.
当两个同符号数相加得到异符号结果时发生溢出；正负数相加不会溢出。溢出判断规则：溢出 = 最高位进位 XOR 最高位出进位。
8. Hashing and Collision Resolution | 哈希与冲突解决
A hash function maps a key to an index in a fixed‑size table. A good hash function distributes keys uniformly. Collisions occur when two keys map to the same index.
哈希函数将键映射到固定大小表中的索引。良好的哈希函数能均匀分布键值。当两个键映射到同一索引时发生冲突。
Common hash function for strings: sum of ASCII values modulo table size.
字符串常用哈希函数：ASCII 值之和模表的大小。
h(key) = (Σ character_code) mod N
Two primary collision resolution strategies:
两种主要的冲突解决策略：
Open addressing (linear probing): if the slot is occupied, try the next slot (index+1) mod N, then the next, until an empty slot is found.
开放寻址（线性探测）：如果槽已被占用，尝试下一个槽 (index+1) mod N，依次寻找直到空槽。
Separate chaining: each table slot holds a linked list of entries that hash to that index.
分离链接法：每个表槽存放一个链表，所有哈希到该索引的条目都链入其中。
9. Sorting Algorithm Complexities | 排序算法复杂度
A solid grasp of common sorting algorithms and their efficiencies is essential for the Edexcel specification. The table below summarises average and worst‑case time complexities and space usage.
扎实掌握常见排序算法及其效率对 Edexcel 考纲至关重要。下表总结了平均和最坏情况时间复杂度以及空间使用情况。
| Algorithm | Average Time | Worst Time | Space |
|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n) |
| Quicksort | O(n log n) | O(n²) | O(log n)* |
* Quicksort’s space complexity depends on recursion depth; in‑place partitioning reduces auxiliary space.
* 快速排序的空间复杂度取决于递归深度；原地分区可减少辅助空间。
10. Logic Gate Truth Tables | 逻辑门真值表
A quick reference for the fundamental logic gates and their Boolean expressions is invaluable for designing and simplifying circuits.
快速查阅基本逻辑门及其布尔表达式对于设计和简化电路非常宝贵。
| Gate | Symbol | Boolean Expression | Truth Table (A,B → Output) |
|---|---|---|---|
| AND | · | A · B | 00→0, 01→0, 10→0, 11→1 |
| OR | + | A + B | 00→0, 01→1, 10→1, 11→1 |
| NOT | ¬ | ¬A | 0→1, 1→0 |
| NAND | ↑ | ¬(A · B) | 00→1, 01→1, 10→1, 11→0 |
| NOR | ↓ | ¬(A + B) | 00→1, 01→0, 10→0, 11→0 |
| XOR | ⊕ | A ⊕ B = ¬A·B + A·¬B | 00→0, 01→1, 10→1, 11→0 |
| XNOR | ⊙ | ¬(A ⊕ B) | 00→1, 01→0, 10→0, 11→1 |
These seven gates form the foundation of combinational logic. NAND and NOR are particularly significant because they are functionally complete, meaning any Boolean function can be implemented using only NAND or only NOR gates.
这七个门构成了组合逻辑的基础。NAND 和 NOR 功能特别强大，因为它们具有功能完备性，即任何布尔函数都可以仅用 NAND 或仅用 NOR 门实现。
11. Common Searching Algorithms | 常用搜索算法
Search algorithms are a core topic. Linear search examines each element in sequence, while binary search efficiently halves the search space on a sorted list.
搜索算法是核心主题。线性搜索依次检查每个元素，而二分搜索在有序列表中高效地每次将搜索范围减半。
Linear Search: O(n) time, O(1) space. Does not require sorted data.
线性搜索：时间复杂度 O(n)，空间复杂度 O(1)。不要求数据有序。
) space (iterative) or O(log n) space (recursive call stack). Requires a sorted array. Mid‑point formula: mid = low + (high − low)/2.
二分搜索：时间复杂度 O(log n)，空间迭代版 O(1)，递归版 O(log n)。要求数组已排序。中点公式：mid = low + (high − low)/2。
12. Error Detection: Checksum and Parity | 错误检测：校验和与奇偶校验
Data transmitted over networks can be corrupted; error detection methods help identify such issues. A parity bit is an extra bit added to a binary string to make the total number of 1s even (even parity) or odd (odd parity). It can detect single‑bit errors.
网络传输中的数据可能损坏；错误检测方法有助于识别这类问题。奇偶校验位是附加到二进制串上的额外位，使得 1 的总数为偶数（偶校验）或奇数（奇校验）。它能检测单比特错误。
A checksum involves summing data blocks (e.g. bytes) and transmitting the sum or its complement. The receiver recomputes the sum and compares.
校验和将数据块（如字节）求和，并传输该和或其补码。接收方重新计算和并进行比较。
Checksum = Sum of data blocks mod 256 (for 8‑bit checksum)
校验和 = 数据块之和模 256（8 位校验和）
More advanced techniques like CRC are built on polynomial division but are beyond the Year 12 core; however, the principles of parity and checksums remain essential revision points.
更高级的技术如 CRC 建立在多项式除法基础上，但它超出了 Year 12 核心范围；不过奇偶校验和校验和的原理仍是重要的复习要点。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图