📚 Formula and Theorem Quick Reference Handbook | 公式定理速查手册
This concise handbook gathers the essential formulae, laws, and complexity facts required for the CAIE Pre-U Computer Science syllabus. Each section presents the key points in both English and Chinese, making it ideal for quick revision and last-minute reference. Keep it at hand while solving past papers to reinforce your understanding of algorithms, data structures, Boolean logic, processor performance, networking, and data representation.
本手册汇集了CAIE Pre-U计算机科学课程所需的基本公式、定律和复杂度要点。每个小节均以中英双语呈现关键内容，非常适合快速复习和考前查阅。在做历年真题时随身携带，可帮助你巩固对算法、数据结构、布尔逻辑、处理器性能、网络及数据表示的理解。
1. Big-O Complexity Classes | 大O复杂度类别
Big-O notation describes the upper bound of an algorithm's time or space complexity as the input size n grows. The most common classes are listed in order of increasing growth rate.
大O表示法描述了随着输入规模 n 的增长，算法时间复杂度或空间复杂度的上界。以下按增长率递增的顺序列出常见的复杂度类别。
- O(1) – Constant time. Execution time does not depend on input size.
O(1) – 常数时间。执行时间与输入规模无关。 - O(log n) – Logarithmic time. Often seen in binary search.
O(log n) – 对数时间。常见于二分查找。 - O(n) – Linear time. A single loop over n elements.
O(n) – 线性时间。对 n 个元素的单层循环。 - O(n log n) – Log-linear time. Typical for efficient sorting algorithms like merge sort.
O(n log n) – 线性对数时间。常见于归并排序等高效排序算法。 - O(n²) – Quadratic time. Nested loops over n elements.
O(n²) – 平方时间。对 n 个元素的嵌套循环。 - O(2ⁿ) – Exponential time. Often appears in brute-force recursive solutions.
O(2ⁿ) – 指数时间。常见于暴力递归解法。 - O(n!) – Factorial time. Extremely slow, seen in permutation problems.
O(n!) – 阶乘时间。极慢，见于排列问题。
When analysing an algorithm, drop constant factors and lower-order terms; only the dominant term determines the Big-O complexity.
分析算法时，应忽略常数因子和低阶项；只有最高阶项决定了大O复杂度。
2. Sorting Algorithms Complexity | 排序算法复杂度
The table below summarises the time and space complexity of the main sorting algorithms required for CAIE Pre-U. Best, average, and worst-case scenarios are indicated where applicable.
下表总结了CAIE Pre-U要求的主要排序算法的时间复杂度和空间复杂度。适用时标注了最好、平均和最坏情况。
| 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) |
| Selection 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) |
Stable sorting algorithms preserve the relative order of equal elements. Merge sort, bubble sort, and insertion sort are stable; quick sort and selection sort are not.
稳定排序算法会保持相等元素的相对次序。归并排序、冒泡排序和插入排序是稳定的；快速排序和选择排序不稳定。
3. Data Structure Operations Complexity | 数据结构操作复杂度
Understanding the time complexity of basic operations on common data structures is crucial for algorithm design and exam questions. The table below uses average-case complexities unless stated otherwise.
理解常见数据结构上基本操作的时间复杂度对于算法设计和考试答题至关重要。下表若无特别说明，均使用平均情况下的复杂度。
| Data Structure 数据结构 | Access 访问 | Search 查找 | Insertion 插入 | Deletion 删除 |
|---|---|---|---|---|
| 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 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash Table 哈希表 | N/A | O(1) | O(1) | O(1) |
| Graph (adjacency list) 图（邻接表） | O(1) | O(V+E) | O(1) | O(E) |
For binary search trees, worst-case complexity becomes O(n) if the tree is unbalanced; self-balancing trees (e.g. AVL) guarantee O(log n).
对于二叉搜索树，如果树不平衡，最坏复杂度将变为 O(n)；自平衡树（例如AVL树）可以保证 O(log n)。
4. Boolean Algebra Laws | 布尔代数定律
Boolean algebra is the foundation of digital logic design. The following laws are used to simplify logic expressions. Assume A, B, C are Boolean variables.
布尔代数是数字逻辑设计的基础。以下定律用于简化逻辑表达式。假设 A、B、C 为布尔变量。
- Identity Law 同一律： A + 0 = A, A · 1 = A
A OR 0 = A, A AND 1 = A - Null Law 零一律： A + 1 = 1, A · 0 = 0
A OR 1 = 1, A AND 0 = 0 - Idempotent Law 幂等律： A + A = A, A · A = A
A OR A = A, A AND A = A - Complement Law 互补律： A + ¬A = 1, A · ¬A = 0
A OR NOT A = 1, A AND NOT A = 0 - Involution Law 双重否定律： ¬(¬A) = A
NOT (NOT A) = A - Commutative Law 交换律： A + B = B + A, A · B = B · A
- Associative Law 结合律： (A + B) + C = A + (B + C), (A · B) · C = A · (B · C)
- Distributive Law 分配律： A · (B + C) = (A · B) + (A · C), A + (B · C) = (A + B) · (A + C)
- Absorption Law 吸收律： A + (A · B) = A, A · (A + B) = A
- De Morgan's Theorems 德摩根定理： ¬(A · B) = ¬A + ¬B, ¬(A + B) = ¬A · ¬B
NOT (A AND B) = (NOT A) OR (NOT B); NOT (A OR B) = (NOT A) AND (NOT B)
Apply these laws to minimise the number of gates in a logic circuit, reducing cost and improving performance.
应用这些定律可以减少逻辑电路中门的数量，从而降低成本并提高性能。
5. Logic Gate Truth Tables | 逻辑门真值表
Standard logic gates and their Boolean expressions are fundamental. The table below shows the symbol, expression, and truth table for two-input gates.
标准逻辑门及其布尔表达式是基础。下表显示了双输入门的符号、表达式和真值表。
| Gate 门 | Expression 表达式 | A=0,B=0 | A=0,B=1 | A=1,B=0 | A=1,B=1 |
|---|---|---|---|---|---|
| AND 与 | A · B | 0 | 0 | 0 | 1 |
| OR 或 | A + B | 0 | 1 | 1 | 1 |
| NAND 与非 | ¬(A · B) | 1 | 1 | 1 | 0 |
| NOR 或非 | ¬(A + B) | 1 | 0 | 0 | 0 |
| XOR 异或 | A ⊕ B | 0 | 1 | 1 | 0 |
| XNOR 同或 | ¬(A ⊕ B) | 1 | 0 | 0 | 1 |
The NOT gate (inverter) has a single input: output = ¬A. Every digital circuit can be constructed using only NAND gates or only NOR gates.
非门（反相器）只有一个输入：输出 = ¬A。任何数字电路都可以仅用与非门或仅用或非门构建。
6. Number Representation Formulas | 数制表示公式
Conversions between binary, denary, and hexadecimal are essential. The value of a binary number bₙ₋₁...b₁b₀ is calculated as:
二进制、十进制和十六进制之间的转换是必需的。二进制数 bₙ₋₁...b₁b₀ 的值计算公式为：
Σ bᵢ × 2ⁱ (from i=0 to n-1)
Similarly, a hexadecimal digit represents 4 bits. To convert from hex to binary, replace each hex digit with its 4‑bit binary equivalent.
类似地，一个十六进制数字代表 4 位二进制。将十六进制转为二进制时，用其 4 位二进制等价物替换每个十六进制数字。
For signed numbers using two's complement, an n-bit integer has range:
对于使用二进制补码的有符号数，n 位整数的范围为：
-2ⁿ⁻¹ to 2ⁿ⁻¹ - 1
7. Floating-Point Representation | 浮点数表示
Floating-point numbers are stored in the form ± mantissa × baseexponent. In binary, the normalised mantissa typically begins with 1 (hidden bit). The IEEE 754 single-precision format uses:
浮点数以 ± 尾数 × 基数指数 的形式存储。在二进制中，规格化的尾数通常以 1 开头（隐藏位）。IEEE 754 单精度格式如下：
- 1 bit sign 符号位
1 位符号位 - 8 bits biased exponent 移码指数 (bias 127)
8 位移码指数（偏置值 127） - 23 bits mantissa (fractional part)
23 位尾数（小数部分）
The value of a normalised single-precision number is:
一个规格化单精度数的值为：
(-1)ˢ × (1.mantissa) × 2exponent - 127
Conversion errors occur because many decimal fractions cannot be represented exactly in binary.
由于许多十进制小数无法精确表示为二进制，会产生转换误差。
8. Memory Addressing Formulas | 内存寻址公式
Memory capacity depends on the number of address lines and data bus width. Key relationships:
内存容量取决于地址线数和数据总线宽度。关键关系如下：
- Number of addressable locations = 2n, where n = number of address lines.
可寻址单元数 = 2n，其中 n 为地址线数。 - Total memory capacity = number of locations × word size (bits).
总内存容量 = 单元数 × 字长（位）。 - Cache address breakdown: Tag | Index | Offset. The index selects the cache line; offset selects the byte within the line.
高速缓存地址划分：标记 | 索引 | 偏移。索引选择缓存行；偏移选择行内字节。
For a direct-mapped cache with line size L bytes and C cache lines, the address bits are split as:
对于行大小为 L 字节、有 C 个缓存行的直接映射缓存，地址位划分如下：
Offset = log₂(L) bits; Index = log₂(C) bits; Tag = remaining bits
9. Processor Performance Equations | 处理器性能方程
Processor execution time is determined by clock rate, cycles per instruction (CPI), and instruction count. The fundamental equation:
处理器执行时间由时钟频率、每条指令周期数 (CPI) 和指令数决定。基本方程：
Execution Time = Instruction Count × CPI × Clock Cycle Time
1 / clock frequency. Therefore, performance improves with higher frequency and lower CPI.
时钟周期 = 1 / 时钟频率。因此，频率越高、CPI 越低，性能越好。
Average CPI for a program with multiple instruction types is:
包含多种指令类型的程序的平均 CPI 为：
CPI_avg = Σ (CPI_i × IC_i) / Total Instruction Count
Amdahl's Law gives the theoretical speedup from improving a part of a system:
阿姆达尔定律给出了改进系统某一部分的理论加速比：
Speedup = 1 / ((1 - f) + f/s)
where f is the fraction of execution time affected by the improvement, and s is the speedup of that part.
其中 f 是受改进影响的执行时间比例，s 是该部分的加速比。
10. Transmission Time and Bandwidth | 传输时间与带宽
In networking, transmission time depends on data size and bandwidth. The formula is:
在网络中，传输时间取决于数据大小和带宽。公式为：
Transmission Time = Data Size (bits) / Bandwidth (bps)
n for a signal to travel across a medium: Propagation Time = Distance / Propagation Speed.
传播延迟是信号在介质中传播所需的时间：传播时间 = 距离 / 传播速度。
Total latency = Transmission Time + Propagation Time + Queuing Delay + Processing Delay.
总延迟 = 传输时间 + 传播时间 + 排队延迟 + 处理延迟。
its per second; useful conversions: 1 kbps = 1000 bps, 1 Mbps = 10⁶ bps, 1 Gbps = 10⁹ bps.
带宽通常以比特每秒计；常用换算：1 kbps = 1000 bps，1 Mbps = 10⁶ bps，1 Gbps = 10⁹ bps。
11. Error Detection and Correction | 错误检测与纠正
Parity bits add a single bit to make the number of 1s either even or odd. It detects single-bit errors but cannot correct them.
奇偶校验位通过添加一个比特使 1 的个数为偶数或奇数。它能检测单比特错误，但无法纠正。
Checksums involve summing data words and sending the sum; the receiver recalculates and compares.
校验和通过对数据字求和并发送该和；接收方重新计算并比较。
Cyclic Redundancy Check (CRC) uses polynomial division; the remainder is appended to the data.
循环冗余校验 (CRC) 使用多项式除法；余数附加到数据后。
Hamming codes can correct single-bit errors. For m data bits, the number of parity bits p must satisfy:
汉明码可以纠正单比特错误。对于 m 个数据位，校验位数量 p 必须满足：
2ᵖ ≥ m + p + 1
Each parity bit covers positions where the bit's binary representation has that power of two.
每个校验位覆盖那些位置编号的二进制表示中对应位为 1 的位置。
12. Encryption Key Size and Security | 加密密钥大小与安全
In symmetric encryption, a brute-force attack tries all possible keys. The number of possible keys for an n-bit key is 2ⁿ. Therefore, the time to break is proportional to 2ⁿ.
在对称加密中，暴力破解会尝试所有可能的密钥。n 位密钥的可能密钥数量为 2ⁿ。因此，破解时间与 2ⁿ 成正比。
Asymmetric encryption (e.g. RSA) relies on the difficulty of factorising large numbers. The security of RSA with key size k bits is roughly equivalent to the difficulty of factoring a k-bit semiprime.
非对称加密（如 RSA）依赖于大数分解的困难性。密钥长度为 k 位的 RSA 安全性大致等同于分解一个 k 位半素数的难度。
A common recommendation: a symmetric key of 128 bits provides roughly the same security as a 3072‑bit RSA key.
常见建议是：128 位对称密钥提供的安全性大致相当于 3072 位 RSA 密钥。
Quantum computing poses a threat to current asymmetric algorithms; Shor's algorithm can factor integers in polynomial time.
量子计算对当前的非对称算法构成威胁；Shor 算法可在多项式时间内分解整数。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图