📚 CCEA Year 13 Computer Science: Formula & Theorem Quick Reference | CCEA Year 13 计算机科学：公式定理速查手册
This quick reference handbook compiles essential formulas, laws, and theorems from the CCEA Year 13 Computer Science curriculum. It is designed to support your revision by summarising key concepts in logic, algorithm analysis, data representation, databases, encryption, and automata. Use it to reinforce your understanding and speed up problem-solving during exam preparation.
本速查手册汇编了 CCEA Year 13 计算机科学课程中的核心公式、定律和定理，旨在帮助你高效复习逻辑、算法分析、数据表示、数据库、加密和自动机等关键模块。用它来巩固理解，提升考试中的解题速度。
1. Boolean Algebra Laws | 布尔代数法则
Boolean algebra provides the mathematical foundation for digital logic circuits and programming conditions. The laws operate on binary variables with two primary operations: AND (·) and OR (+), complemented by NOT (¬ or overline). Every law has a dual form obtained by swapping 0↔1 and AND↔OR.
布尔代数为数字逻辑电路和编程条件提供了数学基础。这些定律作用于二元变量，主要运算为与（AND，·）和或（OR，+），并通过非（NOT，¬）取反。每条定律都有一个对偶形式，可通过互换 0↔1 以及 AND↔OR 得到。
| Law (定律) | AND Form | OR Form |
|---|---|---|
| Identity (恒等律) | A · 1 = A | A + 0 = A |
| Null (零律) | A · 0 = 0 | A + 1 = 1 |
| Idempotent (幂等律) | A · A = A | A + A = A |
| Complement (互补律) | A · ¬A = 0 | A + ¬A = 1 |
| Double Negation (双重否定) | ¬(¬A) = A | |
| 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) |
| Absorption (吸收律) | A · (A + B) = A | A + A·B = A |
Note that the AND and OR distributive laws are not symmetric – the OR‑over‑AND form differs from standard algebra. These identities are essential when simplifying logic expressions and minimising gate counts in circuit design.
注意，与运算和或运算的分配律并不对称——或对与的分配形式与常规代数不同。这些恒等式在简化逻辑表达式和减少电路设计中门数量时至关重要。
2. De Morgan’s Theorems | 德摩根定理
De Morgan’s theorems describe how negation distributes over conjunction and disjunction. They are crucial for converting between AND/OR/NAND/NOR logic and for deriving alternative implementations.
德摩根定理描述了否定运算如何在合取和析取上分配。它们在 AND/OR/NAND/NOR 逻辑转换和导出替代实现中至关重要。
¬(A ∧ B) = ¬A ∨ ¬B and ¬(A ∨ B) = ¬A ∧ ¬B
¬(A · B) = ¬A + ¬B 以及 ¬(A + B) = ¬A · ¬B
In words: the complement of a product equals the sum of the complements; the complement of a sum equals the product of the complements. These theorems generalise to multiple variables and underpin the transformation between sum‑of‑products and product‑of‑sums forms.
换句话说：积之补等于补之和；和之补等于补之积。这些定理可推广到多个变量，是积之和与和之积形式互相转换的基础。
3. Algorithm Complexity & Big‑O Notation | 算法复杂度与大 O 表示法
Big‑O notation describes the upper bound of an algorithm’s running time or space usage as a function of input size n. It ignores constant factors and lower‑order terms. Common classes and their growth rates are shown below.
大 O 表示法描述算法运行时间或空间占用随输入规模 n 增长的上界，忽略常数因子和低阶项。常见复杂度类和增长率如下表。
| Notation | Name | Example | 中文 |
|---|---|---|---|
| O(1) | Constant | Array access | 常数 |
| O(log n) | Logarithmic | Binary search | 对数 |
| O(n) | Linear | Linear search | 线性 |
| O(n log n) | Linearithmic | Merge sort, quicksort avg | 线性对数 |
| O(n²) | Quadratic | Bubble sort | 平方 |
| O(n³) | Cubic | Naive matrix multiplication | 立方 |
| O(2ⁿ) | Exponential | Towers of Hanoi | 指数 |
| O(n!) | Factorial | Brute‑force TSP | 阶乘 |
To determine Big‑O, drop all but the fastest‑growing term and eliminate coefficients. For recursive divide‑and‑conquer algorithms, the Master Theorem gives a shortcut when the recurrence is in the form T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1, and f(n) is asymptotically positive. The solution depends on comparing f(n) with n^(log_b a):
确定大 O 时，只保留增长最快的项并略去系数。对于递归分治算法，若递推式形如 T(n) = aT(n/b) + f(n)（a ≥ 1, b > 1 且 f(n) 渐近正），主定理提供如下捷径，其解取决于 f(n) 与 n^(log_b a) 的比较：
Case 1: if f(n) = O(n^(log_b a – ε)) then T(n) = Θ(n^(log_b a))
Case 2: if f(n) = Θ(n^(log_b a)) then T(n) = Θ(n^(log_b a) · log n)
Case 3: if f(n) = Ω(n^(log_b a + ε)) and a·f(n/b) ≤ c·f(n) (c < 1) then T(n) = Θ(f(n))
These cases help you rapidly classify divide‑and‑conquer algorithms such as binary search, merge sort, and many others without unrolling the full recurrence.
这些情形可帮助你快速分类分治算法（如二分查找、归并排序等），而无须展开完整的递推式。
4. Sorting & Searching Algorithm Performance | 排序与搜索算法性能
The following table summarises the time and space complexity of key algorithms required for CCEA Year 13. Understanding the best, average, and worst cases aids in choosing an appropriate algorithm for a given scenario.
下表总结了 CCEA Year 13 所需关键算法的时间与空间复杂度。理解最佳、平均和最差情况有助于在具体场景中选择合适的算法。
| Algorithm | Best | Average | Worst | Space | 中文 |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | 冒泡排序 |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | 选择排序 |
| Insertion 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) | 归并排序 |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) (stack) | 快速排序 |
更多咨询请联系16621398022（同微信）
CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply