📚 Year 13 WJEC Computer Science: Formula & Theorem Quick Reference Handbook | WJEC 计算机科学公式定理速查手册
This quick-reference handbook covers the essential formulas, theorems, and properties you need to master for the Year 13 WJEC Computer Science specification. From Big O notation to CPU performance equations, Boolean algebra to graph theory, every critical expression is presented in both English and Chinese, helping you revise efficiently and accurately. Use this guide to reinforce your understanding and to keep key facts at your fingertips during exam preparation.
本速查手册涵盖 Year 13 WJEC 计算机科学课程中必须掌握的核心公式、定理和性质。从大 O 记法到 CPU 性能方程，从布尔代数到图论，每个关键表达式均以中英双语呈现，助你高效、准确地复习。备考期间，借助本指南可以巩固理解，并随时查阅重要知识点。
1. Big O Notation & Time Complexity Classes | 大 O 记法与时间复杂度分类
Big O notation describes the upper bound of an algorithm’s running time or space requirement, ignoring constant factors and lower-order terms. It classifies algorithms by how their resource usage grows relative to input size n. Common complexity classes include constant time O(1), where execution does not depend on n; logarithmic time O(log n), typical of binary search; linear time O(n), typical of a single loop; linearithmic time O(n log n), typical of merge sort and quicksort (average case); quadratic time O(n²), typical of nested loops and selection sort; cubic time O(n³); and exponential time O(2ⁿ), which becomes impractical for large n.
大 O 记法描述了算法运行时间或空间需求的上界，忽略常数因子和低阶项。它根据资源使用量随输入规模 n 增长的方式对算法进行分类。常见复杂度类别包括：常数时间 O(1)，执行时间不依赖于 n；对数时间 O(log n)，二分搜索的典型特征；线性时间 O(n)，单层循环的典型特征；线性对数时间 O(n log n)，归并排序和快速排序（平均情况）的典型特征；平方时间 O(n²)，嵌套循环和选择排序的典型特征；立方时间 O(n³)；指数时间 O(2ⁿ)，当 n 较大时变得不切实际。
The formal definition states: f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. For example, if an algorithm requires exactly 3n² + 5n + 10 operations, we say it is O(n²) because for large n, the n² term dominates.
正式定义是：f(n) = O(g(n))，如果存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有 0 ≤ f(n) ≤ c·g(n)。例如，若某个算法恰好需要 3n² + 5n + 10 次操作，我们说它是 O(n²)，因为在 n 较大时，n² 项占主导地位。
2. Sorting Algorithm Complexities | 排序算法复杂度
Sorting algorithms are fundamental, and their time complexities determine practical efficiency. The table below summarises the best, average, and worst-case time complexities and space complexities for the most common sorts. Stable sorts preserve the relative order of equal elements, while in-place sorts require only a constant amount of extra memory.
排序算法是基础内容，其时间复杂度决定了实际效率。下表总结了最常见排序算法的最佳、平均和最坏情况时间复杂度以及空间复杂度。稳定排序保留相等元素的相对顺序，原地排序则仅需常数级额外内存。
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) avg | No* |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
* Quicksort can be implemented with stability but the standard in-place version is not stable.
* 快速排序可以稳定实现，但标准原地版本不稳定。
3. Recurrence Relations & Master Theorem | 递推关系与主定理
Divide-and-conquer algorithms often lead to recurrence relations of the form T(n) = a·T(n/b) + f(n), where a is the number of subproblems, n/b is the size of each subproblem, and f(n) is the cost of dividing and combining. The Master Theorem provides asymptotic bounds for such recurrences. Compare f(n) with n^(log_b a) (written n pow log_b a):
分治算法通常导出形如 T(n) = a·T(n/b) + f(n) 的递推关系，其中 a 为子问题个数，n/b 为每个子问题的规模，f(n) 为分解与合并的代价。主定理给出了这类递推关系的渐近界。将 f(n) 与 n^(log_b a) 进行比较：
- Case 1: If f(n) = O(n^(log_b a – ε)) for some ε > 0, then T(n) = Θ(n^(log_b a)).
- 情况 1：若存在 ε > 0 使得 f(n) = O(n^(log_b a – ε))，则 T(n) = Θ(n^(log_b a))。
- Case 2: If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) · log n).
- 情况 2：若 f(n) = Θ(n^(log_b a))，则 T(n) = Θ(n^(log_b a) · log n)。
- Case 3: If f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and if a·f(n/b) ≤ c·f(n) for some c < 1 and sufficiently large n, then T(n) = Θ(f(n)).
- 情况 3：若存在 ε > 0 使得 f(n) = Ω(n^(log_b a + ε))，且对于某个 c < 1 和足够大的 n，满足 a·f(n/b) ≤ c·f(n)，则 T(n) = Θ(f(n))。
For example, in merge sort, a = 2, b = 2, so log_b a = 1. f(n) = Θ(n) = n¹, fitting Case 2, therefore T(n) = Θ(n log n).
例如，在归并排序中，a = 2，b = 2，故 log_b a = 1。f(n) = Θ(n) = n¹，符合情况 2，因此 T(n) = Θ(n log n)。
4. Boolean Algebra Laws & Simplification | 布尔代数定律与化简
Boolean algebra is used to simplify logic circuits. The fundamental laws form the basis for manipulation. Here are the key identities for variables A, B, C and constants 0 and 1.
布尔代数用于化简逻辑电路。基本定律构成了运算的基础。以下为变量 A、B、C 及常量 0 和 1 的关键恒等式。
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).
Identity: A · 1 = A; A + 0 = A.
Complement: A · ¬A = 0; A + ¬A = 1.
Idempotent: A · A = A; A + A = A.
Null (Annihilation): A · 0 = 0; A + 1 = 1.
Absorption: A + A·B = A; A·(A + B) = A.
De Morgan’s Theorems: ¬(A · B) = ¬A + ¬B; ¬(A + B) = ¬A · ¬B.
Double Negation: ¬(¬A) = A.
交换律：A · B = B · A；A + B = B + A。
结合律：(A · B) · C = A · (B · C)；(A + B) + C = A + (B + C)。
分配律：A · (B + C) = A · B + A · C；A + (B · C) = (A + B) · (A + C)。
同一律：A · 1 = A；A + 0 = A。
互补律：A · ¬A = 0；A + ¬A = 1。
幂等律：A · A = A；A + A = A。
零一律：A · 0 = 0；A + 1 = 1。
吸收律：A + A·B = A；A·(A + B) = A。
德摩根定理：¬(A · B) = ¬A + ¬B；¬(A + B) = ¬A · ¬B。
双重否定：¬(¬A) = A。
These laws can be proved via truth tables and are essential for minimising logic expressions to reduce gate counts.
这些定律可通过真值表证明，对最小化逻辑表达式从而减少门数量至关重要。
5. Karnaugh Maps (K-maps) Minimisation | 卡诺图最小化
Karnaugh maps offer a visual method to simplify Boolean functions with up to four variables (or five with care). Adjacent cells differ by one bit (Gray code ordering). Group the 1s in rectangles of size 1, 2, 4, or 8 that are powers of two. A group eliminates the variable(s) that change across the group. The simplified sum-of-products expression is formed by OR-ing the AND terms of each group, where a variable appears complemented if it is consistently 0 in the group, uncomplemented if consistently 1, and omitted if it varies.
卡诺图提供了一种可视化方法，用于最多四个变量（小心处理也可用五个）的布尔函数简化。相邻单元格通过一位不同（格雷码顺序）排列。将 1 分组成大小为 1、2、4 或 8 的矩形（2 的幂次）。一个组消除在组内变化的变量。简化的积之和表达式通过对每个组的与项进行或运算得到：若变量在组中始终为 0，则以反变量出现；若始终为 1，则以原变量出现；若发生变化，则省略。
For example, the function F(A,B,C) = Σ(0,1,3,7) yields the minimal expression F = ¬A·¬B + A·C.
例如，函数 F(A,B,C) = Σ(0,1,3,7) 的最小化表达式为 F = ¬A·¬B + A·C。
The number of prime implicants and essential prime implicants can also be identified from the K-map. Don’t-care conditions (X) can be treated as 0 or 1 to form larger groups, further simplifying logic.
质蕴含项和必要质蕴含项也可从卡诺图中识别。无关条件（X）可视为 0 或 1，以形成更大的组，进一步简化逻辑。
6. Digital Logic Propagation Delay & Fan-out | 数字逻辑传播延迟与扇出
Every logic gate introduces a propagation delay (t_pd), the time it takes for a change at the input to be reflected at the output. In a combinational circuit, the overall delay is the sum of delays along the critical path. For synchronous circuits, the clock period must be greater than the worst-case combinational delay plus flip-flop setup and hold times.
每个逻辑门都会引入传播延迟（t_pd），即输入变化反映到输出所需的时间。在组合电路中，总延迟是关键路径上延迟的总和。对于同步电路，时钟周期必须大于最坏情况下的组合延迟加上触发器的建立时间和保持时间。
Clock period (T) ≥ t_pd(max) + t_setup + t_hold
The fan-out of a gate is the number of standard loads (inputs of subsequent gates) it can drive while maintaining valid logic levels. Exceeding fan-out limits increases t_pd and may cause malfunction. For TTL logic, a typical fan-out is 10; CMOS gates have high fan-out but increased delay with capacitive load.
门的扇出是指它能驱动同时维持有效逻辑电平的标准负载（后续门的输入）的数量。超出扇出限制会增加 t_pd，并可能导致故障。对于 TTL 逻辑，典型扇出为 10；CMOS 门扇出很高，但延迟会随容性负载增加。
7. CPU Performance Equations | CPU 性能方程
CPU performance is measured through execution time, CPI (cycles per instruction), and clock rate. The fundamental CPU time formula links these parameters:
CPU Execution Time = (Instruction Count × CPI) / Clock Rate
Where Instruction Count is the number of instructions executed, CPI is the average number of clock cycles per instruction, and Clock Rate (frequency) is measured in Hz. The reciprocal, Clock Cycle Time = 1 / Clock Rate, gives the duration of one cycle.
CPU 性能通过执行时间、CPI（每条指令周期数）和时钟频率来衡量。基本的 CPU 时间公式将这几个参数联系起来：
CPU 执行时间 = (指令条数 × CPI) / 时钟频率
其中指令条数是执行的指令数量，CPI 是每条指令的平均时钟周期数，时钟频率以 Hz 为单位。其倒数，时钟周期时间 = 1 / 时钟频率，给出一个周期的持续时间。
MIPS (Million Instructions Per Second) is another metric:
MIPS = Clock Rate / (CPI × 10⁶)
However, MIPS is not always a reliable performance indicator across different instruction set architectures because CPI varies with program characteristics.
MIPS（百万指令每秒）是另一种度量：
MIPS = 时钟频率 / (CPI × 10⁶)
然而，由于 CPI 随程序特性变化，MIPS 并非总是跨不同指令集体系结构的可靠性能指标。
For pipelined processors, the ideal CPI is 1, but hazards (structural, data, control) increase it. The effective CPI = Ideal CPI + Stall cycles per instruction.
对于流水线处理器，理想 CPI 为 1，但结构、数据和控制冲突会使 CPI 增大。有效 CPI = 理想 CPI + 每条指令停顿周期数。
8. Memory Hierarchy & Average Access Time | 存储器层次与平均访问时间
Modern systems use a memory hierarchy with cache, main memory, and disk. The average memory access time (AMAT) is a key performance formula involving cache hit rate (H) and miss penalty (M):
AMAT = H × t_cache + (1 – H) × (t_cache + t_main) = t_cache + (1 – H) × t_main
Often the miss penalty is simply t_main, but in multi-level caches the formula extends. For a two-level cache:
AMAT = t_L1 + (1 – H_L1) × [ t_L2 + (1 – H_L2) × t_main ]
现代系统采用具有缓存、主存和磁盘的存储器层次。平均内存访问时间（AMAT）是涉及缓存命中率（H）和缺失代价（M）的关键性能公式：
AMAT = H × t_cache + (1 – H) × (t_cache + t_main) = t_cache + (1 – H) × t_main
通常缺失代价就是 t_main，但在多级缓存中公式会扩展。对于两级缓存：
AMAT = t_L1 + (1 – H_L1) × [ t_L2 + (1 – H_L2) × t_main ]
Cache performance can also be improved by reducing the miss rate, miss penalty, or access time. The 3 Cs of cache misses (compulsory, capacity, conflict) help analyse miss causes.
缓存性能还可以通过降低缺失率、缺失代价或访问时间来改善。缓存的 3C 缺失模型（强制缺失、容量缺失、冲突缺失）有助于分析缺失原因。
9. Data Transmission & Network Throughput | 数据传输与网络吞吐量
In communication networks, the data transmission time for a file of size S bits over a link of bandwidth B bits per second is t_trans = S / B. The propagation delay t_prop = distance / propagation speed. The total latency includes transmission delay, propagation delay, and queuing delay in routers.
在通信网络中，大小为 S 比特的文件在带宽为 B 比特/秒的链路上的传输时间为 t_trans = S / B。传播延迟 t_prop = 距离 / 传播速度。总延迟包括传输延迟、传播延迟以及路由器中的排队延迟。
Throughput is the effective rate of data transfer. For a TCP connection, the throughput is limited by the congestion window size (CWND) and round-trip time (RTT):
Throughput ≤ CWND / RTT
吞吐量是有效的数据传输速率。对于 TCP 连接，吞吐量受拥塞窗口大小（CWND）和往返时间（RTT）限制：
吞吐量 ≤ CWND / RTT
Bit error rate (BER) and frame error rate are also important in evaluating link quality. The simple parity check and CRC (Cyclic Redundancy Check) detect errors; Hamming distance defines the error detection/correction capability of a code.
误码率（BER）和误帧率在评估链路质量时也很重要。简单奇偶校验和循环冗余校验（CRC）检测错误；汉明距离定义了一种编码的检错/纠错能力。
10. Tree and Graph Properties | 树与图的性质
Trees are connected acyclic graphs. In a rooted binary tree, important relationships exist between nodes and levels. A full binary tree of height h has at most 2ʰ⁺¹ – 1 nodes. The maximum number of leaves at level h is 2ʰ. For a binary search tree, the number of comparisons needed to search is proportional to the tree’s height. In the worst case (degenerate tree), height = n, giving O(n) search; when balanced, height = O(log n).
树是无环连通图。在根二叉树的节点与层次之间存在重要关系。高度为 h 的满二叉树最多有 2ʰ⁺¹ – 1 个节点。第 h 层的最多叶节点数为 2ʰ。对于二叉搜索树，查找所需的比较次数与树的高度成正比。最坏情况下（退化树），高度 = n，查找复杂度为 O(n)；平衡时，高度 = O(log n)。
Graph properties include the degree of a vertex, the handshaking lemma (sum of degrees = 2 × number of edges), and connectivity. In an undirected graph, a tree with |V| vertices has exactly |V| – 1 edges. Dijkstra’s algorithm finds the shortest path from a single source in O(|E| + |V| log |V|) time using a priority queue. The adjacency matrix for a graph of n nodes requires n² storage.
图的性质包括顶点的度、握手引理（度之和 = 2 × 边数）以及连通性。在无向图中，具有 |V| 个顶点的树恰好有 |V| – 1 条边。Dijkstra 算法使用优先队列在 O(|E| + |V| log |V|) 时间内找到单源最短路径。n 个节点的图的邻接矩阵需要 n² 存储空间。
11. Hash Functions & Collision Resolution | 哈希函数与冲突解决
Hashing maps keys to array indices using a hash function h(key). A good hash function distributes keys uniformly to minimise collisions. The load factor α = n / m, where n is the number of stored elements and m is the table size. With chaining, average search time is O(1 + α). When using open addressing with linear probing, the average number of probes for an unsuccessful search is approximately (1/2)(1 + 1/(1-α)²).
哈希使用哈希函数 h(key) 将键映射到数组索引。一个好的哈希函数将键均匀分布，以最小化冲突。负载因子 α = n / m，其中 n 是存储的元素数，m 是表的大小。采用链地址法时，平均查找时间为 O(1 + α)。采用开放定址法的线性探测时，不成功查找的平均探测次数约为 (1/2)(1 + 1/(1-α)²)。
Common collision resolution techniques include separate chaining and open addressing (linear probing, quadratic probing, double hashing). Double hashing uses a second hash function h2(key) to determine the step size, reducing clustering.
常见的冲突解决技术包括链地址法和开放定址法（线性探测、二次探测、双哈希）。双哈希使用第二个哈希函数 h2(key) 来确定步长，减少聚集现象。
12. Data Compression Ratios | 数据压缩比
Compression reduces the size of data for storage or transmission. The compression ratio is defined as the size of the original data divided by the size of the compressed data:
Compression ratio = Original size / Compressed size
The space saving is often expressed as a percentage: (1 – 1/ratio) × 100%. Lossless compression (e.g., Huffman coding, LZW) preserves all original data; lossy compression (e.g., JPEG, MP3) achieves higher ratios by discarding less perceptible information.
压缩可减少数据量以便存储或传输。压缩比定义为原始数据大小与压缩后数据大小之比：
压缩比 = 原始大小 / 压缩后大小
空间节省通常以百分比表示：(1 – 1/比) × 100%。无损压缩（如哈夫曼编码、LZW）保留所有原始数据；有损压缩（如 JPEG、MP3）通过丢弃不太可感知的信息获得更高的压缩比。
Entropy H = -Σ P(x) log₂ P(x) gives the theoretical minimum average bits per symbol for lossless coding. Huffman coding produces a prefix-free code close to this entropy bound.
熵 H = -Σ P(x) log₂ P(x) 给出了无损编码每个符号的理论最小平均比特数。哈夫曼编码可产生接近此熵界的无前缀编码。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导