📚 Year 13 OCR Computer Science: Formulae and Theorems Quick Reference | 13年级OCR计算机科学公式定理速查手册
This quick reference guide distils the essential formulae, theorems and complexity results required for the Year 13 OCR A-Level Computer Science course. From Boolean algebra and processor performance to database normalisation, every concept is presented in a clean, bilingual format to help you revise efficiently.
本速查手册浓缩了13年级OCR A-Level计算机科学课程所需的必备公式、定理和复杂度结论。从布尔代数、处理器性能到数据库规范化，每个知识点均以清晰的双语形式呈现，助你高效复习。
1. Boolean Algebra Fundamental Theorems | 布尔代数基本定理
Boolean algebra operates on binary variables using the values 0 and 1. The following laws are foundational for simplifying logic circuits and expressions. In this notation, ∧ represents AND, ∨ represents OR, and ¬ represents NOT.
布尔代数使用值0和1对二进制变量进行运算。下列基本定律是化简逻辑电路和逻辑表达式的基石。在本文符号中，∧表示与，∨表示或，¬表示非。
Identity Law: A ∨ 0 = A, A ∧ 1 = A
同一律：A ∨ 0 = A，A ∧ 1 = A
Null Law: A ∨ 1 = 1, A ∧ 0 = 0
零律：A ∨ 1 = 1，A ∧ 0 = 0
Idempotent Law: A ∨ A = A, A ∧ A = A
幂等律：A ∨ A = A，A ∧ A = A
Complement Law: A ∨ ¬A = 1, A ∧ ¬A = 0
互补律：A ∨ ¬A = 1，A ∧ ¬A = 0
Involution (Double Negation): ¬(¬A) = A
双重否定律：¬(¬A) = A
Commutative Law: A ∨ B = B ∨ A, A ∧ B = B ∧ A
交换律：A ∨ B = B ∨ A，A ∧ B = B ∧ A
Associative Law: (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 Law: 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 Law: A ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A
吸收律：A ∨ (A ∧ B) = A，A ∧ (A ∨ B) = A
2. De Morgan’s Laws and Simplification | 德摩根定律与逻辑简化
De Morgan’s laws allow the transformation of ANDs into ORs and vice versa under negation. They are essential for turning complex gate networks into NAND-only or NOR-only implementations.
德摩根定律允许在取反条件下将“与”运算转换为“或”运算，反之亦然。这对于将复杂门电路网络转换为纯NAND或纯NOR实现至关重要。
First Law: ¬(A ∧ B) = ¬A ∨ ¬B
第一定律：¬(A ∧ B) = ¬A ∨ ¬B
Second Law: ¬(A ∨ B) = ¬A ∧ ¬B
第二定律：¬(A ∨ B) = ¬A ∧ ¬B
In practice, these laws are used alongside the fundamental theorems to minimise the number of gates in a circuit. For example, the expression ¬(A ∧ ¬B) can be rewritten as ¬A ∨ B using double negation and De Morgan.
在实践中，这些定律与基本定理一起用来最小化电路中的门数量。例如，表达式 ¬(A ∧ ¬B) 可以利用双重否定和德摩根定律重写为 ¬A ∨ B。
3. Processor Performance Formulae | 处理器性能公式
CPU performance is commonly evaluated using execution time, CPI and MIPS. These quantities link instruction count, clock speed and average cycles per instruction.
CPU性能通常通过执行时间、CPI和MIPS来评估。这些量将指令数、时钟频率和平均每指令周期数联系起来。
CPU Execution Time = (IC × CPI) / f
其中IC = 指令总数，CPI = 平均每指令周期数，f = 时钟频率。
Often CPI is given as a weighted average when different instruction types require different numbers of cycles.
通常当不同类型的指令需要不同数量的周期时，CPI以加权平均值的形式给出。
MIPS = f / (CPI × 10⁶)
MIPS即每秒百万指令数，衡量处理器的吞吐量。较高的MIPS值意味着同一程序执行得更快，但受指令集差异的限制。
When comparing machines, total execution time is a more reliable metric than MIPS alone.
在比较机器时，总执行时间比单纯的MIPS更可靠。
4. Amdahl’s Law | 阿姆达尔定律
Amdahl’s Law predicts the maximum theoretical speedup achievable when part of a program is parallelised. It demonstrates the limiting effect of the serial fraction.
阿姆达尔定律预测了当程序的一部分被并行化时可达到的最大理论加速比。该定律展示了串行部分带来的限制效应。
Speedup = 1 / ((1 – P) + P/N)
其中P是可以并行化的程序比例，N是处理器数量。即使N无限大，加速比也受限于1/(1-P)。若P=0.9，最大加速比不超过10。
This law is critical when evaluating the benefit of adding more cores to a system. It also applies to multicore programming and GPU computing discussions in the OCR syllabus.
该定律在评估为系统添加更多核的收益时至关重要。它也适用于OCR教学大纲中关于多核编程和GPU计算的讨论。
5. Data Representation: Two’s Complement and Floating Point | 数据表示：补码与浮点数
Two’s complement is used to represent signed integers. For an n-bit word, the range of representable values is:
二进制补码用于表示有符号整数。对于n位字长，可表示的数值范围为：
Range: -2^(n-1) to 2^(n-1) – 1
For example, an 8-bit two’s complement integer can store values from -128 to 127. The most significant bit acts as the sign bit.
例如，8位补码整数可以存储从-128到127的值。最高有效位充当符号位。
Floating point representation follows the general normalised form:
浮点数表示遵循通用的规范化形式：
Value = ± mantissa × 2^exponent
OCR expects familiarity with the IEEE 754 single-precision format: 1-bit sign, 8-bit biased exponent (bias = 127), and 23-bit mantissa with implicit leading 1. Normalisation ensures the mantissa begins with 1.01… (binary).
OCR要求熟悉IEEE 754单精度格式：1位符号，8位移码指数（偏移量=127），23位尾数（含隐含的前导1）。规格化确保尾数以1.01…（二进制）开头。
6. Big O Notation Reference | 大O复杂度参考
Big O notation describes the upper bound of an algorithm’s time or space complexity as the input size n grows. It ignores constant factors and lower-order terms.
大O表示法描述的是随着输入规模n增长，算法时间或空间复杂度的上界。它忽略常数因子和低阶项。
O(1) – constant time: array index access, stack push/pop.
O(1) – 常数时间：数组索引访问，栈的压入/弹出。
O(log n) – logarithmic time: binary search in a sorted array.
O(log n) – 对数时间：有序数组中的二分查找。
O(n) – linear time: simple linear search, traversing a list.
O(n) – 线性时间：简单线性搜索，遍历链表。
O(n log n) – log-linear time: efficient sorting algorithms such as merge sort and quick sort (average case).
O(n log n) – 线性对数时间：归并排序、快速排序（平均情况）等高效排序算法。
O(n²) – quadratic time: bubble sort, insertion sort (worst case).
O(n²) – 平方时间：冒泡排序、插入排序（最坏情况）。
O(2^n) – exponential time: recursive Fibonacci calculation without memoisation.
O(2^n) – 指数时间：无记忆化的递归斐波那契计算。
O(n!) – factorial time: travelling salesman problem via brute force.
O(n!) – 阶乘时间：暴力求解旅行商问题。
7. Sorting and Searching Algorithm Complexities | 排序与搜索算法复杂度
Understanding the best, average and worst-case time complexities of common algorithms is required for algorithm selection and exam analysis.
理解常见算法的最佳、平均和最坏情况时间复杂度对于算法选择和考试分析是必需的。
Linear Search: O(n) in all cases. Simple but inefficient for large datasets.
线性搜索：所有情况下均为O(n)。简单但用于大数据集时效率低下。
Binary Search: O(log n) worst case. Requires the data to be sorted first.
二分查找：最坏情况O(log n)。要求数据预先排序。
Bubble Sort: O(n²) average and worst, O(n) best if already sorted with an early-exit optimisation.
冒泡排序：平均和最坏情况O(n²)，若加入提前退出优化则最佳情况为O(n)（已排好序时）。
Insertion Sort: O(n²) worst, O(n) best. Efficient on small or nearly sorted data.
插入排序：最坏O(n²)，最佳O(n)。对小规模或已接近排序的数据高效。
Merge Sort: O(n log n) in all cases. Stable and uses divide-and-conquer, requiring O(n) auxiliary space.
归并排序：所有情况下O(n log n)。稳定，采用分治法，需要O(n)辅助空间。
Quick Sort: O(n log n) average, O(n²) worst case (e.g. already sorted or reverse sorted array with poor pivot selection). The best case is O(n log n).
快速排序：平均O(n log n)，最坏O(n²)（如数组已排序或逆序且基准选取不当）。最佳情况为O(n log n)。
8. Data Structure Operation Complexities | 数据结构操作复杂度
Selecting the right data structure depends on the expected frequency of operations. The table below summarises the time complexities for fundamental data types, where n is the number of elements.
选择合适的数据结构取决于操作的预期频率。下表总结了基本数据结构的各种操作时间复杂度，其中n为元素个数。
| Data Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | Published by TutorHao | Year 13 Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信） CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导