📚 Year 13 WJEC Computer Science: Formula & Theorem Quick Reference Handbook | WJEC 计算机科学 A2 公式定理速查手册
This quick-reference handbook compiles the essential formulas, theorems, and key relationships for the Year 13 WJEC Computer Science specification. It serves as a handy revision aid, covering algorithm complexity, data structures, Boolean algebra, theory of computation, processor performance, databases, and networking. Keep it close when tackling past papers and check your understanding of each concept with the paired explanations.
本速查手册汇总了 WJEC 计算机科学 A2（Year 13）大纲中的核心公式、定理和关键关系。它涵盖了算法复杂度、数据结构、布尔代数、计算理论、处理器性能、数据库和网络等领域，是备考复习的实用工具。每个概念都配有中英对照解释，帮助你巩固理解并高效解题。
1. Big O Notation Complexity Formulas | 大 O 表示法复杂度公式
Big O notation describes an upper bound on the growth rate of an algorithm's time or space requirements. It allows us to classify algorithms by how their resource consumption scales with input size n.
大 O 表示法用于描述算法时间或空间需求增长的上界，帮助我们根据输入规模 n 的增长对算法进行分类。
| Notation | Name | Example |
| O(1) | Constant | Array access by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n2) | Quadratic | Bubble sort, insertion sort |
| O(2n) | Exponential | Recursive Fibonacci |
| O(n!) | Factorial | Travelling salesman brute force |
Informally, O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!) for large n. Big Theta (Θ) gives a tight bound, and Big Omega (Ω) gives a lower bound.
非正式地，对于很大的 n 有 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。大 Θ 表示紧确界，大 Ω 表示下界。
2. Recurrence Relations & Master Theorem | 递推关系与主定理
of the form T(n) = aT(n/b) + f(n). The Master Theorem provides a direct way to solve them.
许多分治算法的运行时间可表示为形如 T(n) = aT(n/b) + f(n) 的递推式，主定理提供了一种直接求解的方法。
T(n) = aT(n/b) + f(n)
Case 1: If f(n) = O(nlogba - ε) for some ε > 0, then T(n) = Θ(nlogba).
情况 1：若 f(n) = O(nlog_b a - ε)（ε>0），则 T(n) = Θ(nlog_b a)。
Case 2: If f(n) = Θ(nlogba), then T(n) = Θ(nlogba log n).
情况 2：若 f(n) = Θ(nlog_b a)，则 T(n) = Θ(nlog_b a log n)。
Case 3: If f(n) = Ω(nlogba + ε) and af(n/b) ≤ cf(n) for some c < 1, then T(n) = Θ(f(n)).
情况 3：若 f(n) = Ω(nlog_b a + ε) 且满足正则条件，则 T(n) = Θ(f(n))。
Example: Binary search recurrence T(n) = T(n/2) + O(1) falls into Case 2 (a=1, b=2, logba=0), giving Θ(log n). Merge sort T(n) = 2T(n/2) + O(n) also Case 2, giving Θ(n log n).
示例：二分查找递推式 T(n) = T(n/2) + O(1) 属于情况 2（a=1, b=2），解为 Θ(log n)。归并排序 T(n) = 2T(n/2) + O(n) 同为情况 2，解为 Θ(n log n)。
3. Data Structure Essential Formulas | 数据结构核心公式
Key formulas for binary trees and graphs appear frequently in written assessments. For a full binary tree of height h (root at height 1), the maximum number of nodes is:
二叉树和图的关键公式在笔试中经常出现。对于高度为 h 的满二叉树（根高度为 1），最大节点数为：
n = 2h - 1
Conversely, the minimal height of a complete binary tree with n nodes is h = ⌈log2(n+1)⌉. In an array-based heap, for an element at index i: parent = ⌊(i-1)/2⌋, left child = 2i+1, right child = 2i+2.
反之，含 n 个节点的完全二叉树的最小高度为 h = ⌈log₂(n+1)⌉。在基于数组的堆中，索引 i 元素的父节点为 ⌊(i-1)/2⌋，左子节点为 2i+1，右子节点为 2i+2。
e graph, the sum of degrees of all vertices equals twice the number of edges: Σ deg(v) = 2|E|. A tree with V vertices satisfies |E| = |V| - 1.
对于简单图，所有顶点的度数之和等于边数的两倍：Σ deg(v) = 2|E|。对于树，有 |E| = |V| - 1。
4. Sorting & Searching Algorithm Metrics | 排序与搜索算法指标
Common comparison-based sorting algorithms have well-known time complexities in best, average, and worst cases. The table below summarises them.
常见的基于比较的排序算法在最好、平均和最坏情况下有已知的时间复杂度，下表对这些算法进行了总结。
| Algorithm | Best | Average | Worst | Space |
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) |
| Insertion Sort | O(n) | O(n2) | O(n2) | 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(n2) | O(log n) |
The maximum number of comparisons in binary search is ⌊log2 n⌋ + 1. For linear search, worst-case comparisons = n.
二分查找的最大比较次数为 ⌊log₂ n⌋ + 1。线性查找的最坏情况比较次数为 n。
5. Boolean Algebra Laws & Simplification | 布尔代数定律与化简
The laws of Boolean algebra are essential for simplifying logic circuits and expressions. A and B are Boolean variables.
布尔代数定律对化简逻辑电路和表达式至关重要。A 与 B 为布尔变量。
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)
Distributive: A∧(B∨C) = (A∧B)∨(A∧C)
分配律：A∧(B∨C) = (A∧B)∨(A∧C)
Identity: A∨0 = A ; A∧1 = A
同一律：A∨0 = A ；A∧1 = A
Complement: A∨¬A = 1 ; A∧¬A = 0
互补律：A∨¬A = 1 ；A∧¬A = 0
De Morgan's: ¬(A∧B) = ¬A∨¬B ; ¬(A∨B) = ¬A∧¬B
德摩根定律：¬(A∧B) = ¬A∨¬B ；¬(A∨B) = ¬A∧¬B
Absorption: A∨(A∧B) = A ; A∧(A∨B) = A
吸收律：A∨(A∧B) = A ；A∧(A∨B) = A
underpin Karnaugh map simplification and logic minimisation. An XOR gate is expressed as A ⊕ B = (A∧¬B) ∨ (¬A∧B).
这些定律是卡诺图化简和逻辑最小化的基础。异或门可表示为 A ⊕ B = (A∧¬B) ∨ (¬A∧B)。
6. Logic Gates & Truth Tables | 逻辑门与真值表
NAND and NOR gates are functionally complete; any Boolean function can be implemented using only NAND gates or only NOR gates. The universal gate theorem is often examined.
与非门和或非门具有功能完备性；任何布尔函数均可仅用与非门或仅用或非门实现。通用门定理经常出现在考题中。
NAND: ¬(A∧B) ; NOR: ¬(A∨B)
A half adder produces sum S = A ⊕ B and carry C = A∧B. A full adder includes a carry-in Cin: S = A ⊕ B ⊕ Cin, Cout = (A∧B) ∨ (Cin∧(A⊕B)).
半加器产生和 S = A⊕B 及进位 C = A∧B。全加器包含进位输入 Cin：S = A⊕B⊕Cin，进位输出 Cout = (A∧B) ∨ (Cin∧(A⊕B))。
7. Finite State Machines & Regular Expressions | 有限状态机与正则表达式
A deterministic finite automaton (DFA) is defined by the 5‑tuple M = (Q, Σ, δ, q0 a finite set of states, Σ is the input alphabet, δ: Q×Σ → Q is the transition function, q0 is the start state, and F ⊆ Q is the set of accept states.
确定型有限自动机 (DFA) 由五元组 M = (Q, Σ, δ, q₀, F) 定义，其中 Q 为有限状态集，Σ 为输入符号表，δ: Q×Σ → Q 为转移函数，q₀ 为起始状态，F ⊆ Q 为接受状态集。
put). Moore machines produce outputs based solely on the current state: output = H(state).
Mealy 机在转移时产生输出：输出 = G(状态, 输入)。Moore 机仅基于当前状态产生输出：输出 = H(状态)。
Regular expressions and finite automata are equivalent. Basic operations: concatenation (ab), union (a|b), and Kleene star (a*). Thompson's construction algorithm transforms a regex into an NFA.
正则表达式与有限自动机等价。基本运算包括：连接 (ab)、并 (a|b) 和 Kleene 星号 (a*)。Thompson 构造法将正则表达式转换为 NFA。
8. Turing Machines & Computability | 图灵机与可计算性
A Turing machine is formally a 7‑tuple M = (Q, Γ, b, Σ, δ, q0, F), where Γ is the tape alphabet, b ∈ symbol, and δ: Q×Γ → Q×Γ×{L,R} is the transition function. It captures what is computable.
图灵机形式化为七元组 M = (Q, Γ, b, Σ, δ, q₀, F)，其中 Γ 为带符号表，b ∈ Γ 是空白符，δ: Q×Γ → Q×Γ×{L,R} 为转移函数。它刻画了可计算的概念。
The Church‑Turing thesis states that any effectively calculable function can be computed by a Turing machine. The halting problem is undecidable: there is no algorithm that decides for every program-input pair whether the program halts.
丘奇-图灵论题声称任何有效可计算的函数均可由图灵机计算。停机问题是不可判定的：不存在这样一个算法，能对任意程序-输入对判定程序是否停机。
9. Computer Arithmetic & Data Representation | 计算机算术与数据表示
In two's complement with n bits, the representable integer range is -2n-1 to 2n-1 - 1. To negate a number, invert all bits and add 1.
在 n 位二进制补码表示中，整数范围为 -2ⁿ⁻¹ 至 2ⁿ⁻¹ - 1。求负数时可按位取反再加 1。
IEEE 754 single-precision floating-point uses 1 sign bit, 8 exponent bits (bias 127), and 23 mantissa bits. The value is:
(-1)s × (1.M) × 2E-127
hich is not stored (hidden bit). Denormalised numbers use exponent 0 and represent 0.M × 2-126.
规格化规则在二进制小数点前隐含一个 1（隐藏位），不存储。非规格化数使用指数 0，表示 0.M × 2⁻¹²⁶。
10. Processor Performance & Memory Hierarchy | 处理器性能与存储层次
CPU execution time is governed by the classic formula:
CPU Time = Instruction Count × CPI × Clock Cycle Time
MIPS (Million Instructions Per Second) = (Clock Rate) / (CPI × 106). Amdahl' speedup from enhancing a fraction f of a task by factor S: speedup = 1 / [(1 - f) + f/S].
MIPS（每秒百万指令）= 时钟频率 / (CPI × 10⁶)。Amdahl 定律指出，若将任务中占比 f 的部分加速 S 倍，则整体加速比 = 1 / [(1 - f) + f/S]。
Average Memory Access Time (AMAT) for a cache is:
AMAT = Hit Time + Miss Rate × Miss Penalty
For a direct-mapped cache with C bytes capacity, block size B
Published by TutorHao | Year 13 Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图