📚 IB Computer Science: Formula Handbook | IB 计算机：公式汇总手册
Welcome to the ultimate IB Computer Science formula handbook, designed to consolidate the key equations, conversions, and computational rules you will encounter across the syllabus. From time complexity and Boolean algebra to data compression and network latency, this resource serves as a quick reference for both exam preparation and coursework. Each formula is paired with a concise explanation in English and Chinese, ensuring clarity for bilingual learners.
欢迎使用这本 IB 计算机科学公式汇总手册，它汇集了教学大纲中涉及的关键方程、转换方法和计算规则。从时间复杂度和布尔代数，到数据压缩和网络延迟，这本手册可作为考试复习和课程作业的快速参考。每个公式都配有中英文简要说明，确保双语学习者都能清晰理解。
1. Time Complexity and Big-O Notation | 时间复杂度与 Big-O 表示法
The efficiency of an algorithm is expressed using Big-O notation, which describes the worst-case growth rate of time or space requirements as the input size n ms often lead to recurrence relations, such as T(n) = T(n/2) + O(1) for binary search, yielding O(log n).
算法的效率用 Big-O 表示法来描述，它表示随着输入规模 n 增大，时间或空间需求在最坏情况下的增长率。常见类别包括 O(1) 常数时间，O(n) 线性时间，O(n²) 平方时间，以及 O(log n) 对数时间。递归算法常导出递推关系，例如二分查找的 T(n) = T(n/2) + O(1)，结果为 O(log n)。
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
The above inequality shows the relative growth rates. Choosing algorithms with lower Big-O complexity is crucial for scalable software.
上述不等式展示了相对增长率。选择 Big-O 复杂度更低的算法对于可扩展软件至关重要。
2. Recursive Algorithms and Recurrence Relations | 递归算法与递推关系
Recurrence relations define the time complexity of divide‑and‑ ich solves to O(n log n) by the Master Theorem. Binary search follows T(n) = T(n/2) + O(1) ⇒ to set up these relations helps in analysing recursion depth and work done at each level.
递推关系定义了分治算法的时间复杂度。归并排序的递推式为 T(n) = 2T(n/2) + O(n)，根据主定理可得 O(n log n)。二分查找的递推式为 T(n) = T(n/2) + O(1) ⇒ O(log n)。理解如何建立这些关系有助于分析递归深度和每层的工作量。
T(n) = a·T(n/b) + f(n)
Where a is the number of subproblems, n/b is the size of each, and f(n) is the cost of dividing and combining. The Master Theorem provides the asymptotic bound:
其中 a 是子问题个数，n/b 是每个子问题规模，f(n) 是分解与合并的开销。主定理提供了渐近界：
- If f(n) = O(nᶜ) with c < log_b a → T(n) = Θ(nlog_b a)
- If f(n) = Θ(nᶜ) with c = log_b a → T(n) = Θ(nᶜ log n)
- If f(n) = Ω(nᶜ) with c > log_b a and a·f(n/b) ≤ k·f(n) → T(n) = Θ(f(n))
如果 f(n) = O(nᶜ) 且 c < log_b a，则 T(n) = Θ(nlog_b a)；若 c = log_b a，则 T(n) = Θ(nᶜ log n)；若 c > log_b a 且满足正则条件，则 T(n) = Θ(f(n))。
3. Binary and Hexadecimal Conversions | 二进制与十六进制转换
Data representation is fundamental in IB Computer Science. To convert a positive decimal integer to binary, repeatedly divide by 2 and record the remainders. For hexadecimal, group binary digits in sets of four. The conversion formulas are:
数据表示是 IB 计算机科学的基础。将十进制正整数转换为二进制，可反复除以 2 并记录余数。转换为十六进制时，将二进制位按四位一组进行分组。转换公式如下：
Decimal to binary: (d)₁₀ = (bₖ₋₁ … b₁ b₀)₂, where bᵢ = (d div 2ⁱ) mod 2
Binary to hex: group 4 bits from right, map 0000→0 … 1111→F
For negative numbers in two’s complement, invert all bits and add 1 to obtain the representation. An 8‑bit two’s complement number has range –128 to +127.
对于负数的补码表示，将所有位取反再加 1 即可得到补码。8 位补码表示的范围是 –128 到 +127。
- Two’s complement value = –bₙ₋₁·2ⁿ⁻¹ + Σ(bᵢ·2ⁱ) for i=0 to n−2
- 补码值 = –bₙ₋₁·2ⁿ⁻¹ + Σ(bᵢ·2ⁱ)，i 从 0 到 n−2
4. Data Size and Storage Calculations | 数据大小与存储计算
nd, size = sample rate (Hz) × bit depth × number of channels × duration (s). Use the following units:
计算文件大小是常见的考试内容。对于位图图像，文件大小 = 宽 (像素) × 高 (像素) × 颜色深度 (位)。对于未压缩音频，大小 = 采样率 (Hz) × 位深度 × 声道数 × 时长 (秒)。请使用以下单位：
| 1 byte = 8 bits | 1 KiB = 1024 bytes |
| 1 MiB = 1024 KiB | 1 GiB = 1024 MiB |
s. For compressed files, apply the compression ratio: compressed size = original size × (1 – space saving %).
在转换为更大单位之前，务必将位换算为字节（÷8）。对于压缩文件，可应用压缩比：压缩后大小 = 原始大小 × (1 – 空间节省百分比)。
Image size = w × h × d / 8 bytes
Sound size = rate × depth × channels × time / 8 bytes
5. Boolean Algebra Laws and Simplification | 布尔代数定律与化简
Boolean algebra is used to simplify logic circuits and conditions in programming. The fundamental laws include identity, null, idempotent, inverse, commutative, associative, distributive, absorption, and De Morgan’s theorems. Key identities are:
布尔代数用于化简逻辑电路和编程中的条件表达式。基本定律包括同一律、零律、幂等律、互补律、交换律、结合律、分配律、吸收律和德摩根定理。关键恒等式如下：
A + 0 = A, A · 1 = A
A + 1 = 1, A · 0 = 0
A + A = A, A · A = A
A + ¬A = 1, A · ¬A = 0
De Morgan: ¬(A·B) = ¬A + ¬B, ¬(A+B) = ¬A · ¬B
Using these laws, an expression like ¬A·B + A·B can be simplified to B (by distributive and inverse). Simplification reduces gate count and improves efficiency.
利用这些定律，表达式 ¬A·B + A·B 可化简为 B（通过分配律和互补律）。化简可减少逻辑门数量并提高效率。
6. Logic Gates and Truth Tables | 逻辑门与真值表
Logic gates perform basic Boolean functions. The standard gates are AND, OR, NOT, NAND, NOR, XOR, and XNOR. Each gate’s output can be expressed as a Boolean equation:
逻辑门执行基本布尔运算。标准门包括与门、或门、非门、与非门、或非门、异或门和同或门。每个门的输出可用布尔方程表示：
- AND: Q = A · B
- OR: Q = A + B
- NOT: Q = ¬A
- NAND: Q = ¬(A · B)
- NOR: Q = ¬(A + B)
- XOR: Q = A ⊕ B = A·¬B + ¬A·B
- XNOR: Q = A ⊙ B = A·B + ¬A·¬B
Truth tables enumerate all input combinations. For n inputs, there are 2ⁿ rows. Producing a truth table from a problem statement is a key skill for circuit design.
真值表枚举所有输入组合。对于 n 个输入，共有 2ⁿ 行。根据问题描述构建真值表是电路设计的关键技能。
Rows in truth table = 2ⁿ
7. Network Delay and Transmission Time | 网络延迟与传输时间
Network performance is quantified through latency, propagation delay, transmission time, and queuing delay. The total delay for a packet is:
网络性能通过延迟、传播时延、传输时间和排队时延来衡量。数据包的总时延为：
Total delay = Propagation delay + Transmission time + Queuing delay + Processing delay
Propagation delay = Distance / Propagation speed
Transmission time = Packet size (bits) / Bandwidth (bps)
For example, a 1500‑ / (100×10⁶) = 0.12 ms. Propagation delay over 1000 km of fibre at 2×10⁸ m/s is 5 ms. Round‑trip time (RTT) is twice the one‑way delay.
例如，一个 1500 字节的数据包在 100 Mbps 链路上的传输时间 = (1500×8) / (100×10⁶) = 0.12 毫秒。在 1000 公里光纤上以 2×10⁸ 米/秒传播的单向传播时延为 5 毫秒。往返时间 (RTT) 是单向时延的两倍。
8. CPU Performance Equations | CPU 性能公式
CPU performance can be evaluated using execution time, clock cycles, and instruction count. The fundamental formula is:
CPU 性能可以通过执行时间、时钟周期和指令数进行评估。基本公式如下：
CPU Time = Instruction Count × CPI × Clock cycle time
cle time = 1 / clock frequency. MIPS (millions of instructions per second) can be derived:
其中 CPI 是每条指令的平均周期数，时钟周期时间 = 1 / 时钟频率。MIPS（每秒百万指令数）可通过以下公式导出：
MIPS = Clock rate (MHz) / (CPI × 10⁶)
second, or around 1333 MIPS. To compare two processors, use speedup = Time_old / Time_new.
一个主频为 2 GHz 且 CPI = 1.5 的处理器，每秒执行约 2×10⁹ / 1.5 ≈ 1.33×10⁹ 条指令，约为 1333 MIPS。比较两个处理器时，可使用加速比 = 旧执行时间 / 新执行时间。
9. Memory Addressing and Capacity | 内存寻址与容量
Memory capacity depends on the number of addressable locations and the word size. For a memory with n address lines, the number of unique addresses is 2ⁿ. Total capacity in bits is:
内存容量取决于可寻址单元的个数和字长。对于具有 n 条地址线的存储器，唯一地址数为 2ⁿ。总容量（位）为：
Capacity (bits) = 2address lines × word size (bits)
For example, a 16‑ 6 locations. If each location stores 1 byte, the total capacity is 64 KiB. Cache memory mapping (direct, set‑associative) uses formulas for tag, index, and offset bits:
例如，16 位地址总线可寻址 2¹⁶ = 65536 个单元。若每个单元存储 1 字节，则总容量为 64 KiB。缓存映射（直接映射、组相联）中使用标签、索引和偏移位的计算公式：
Offset bits = log₂(block size)
Index bits = log₂(number of sets)
Tag bits = Address bits – (Index bits + Offset bits)
10. Data Compression Ratios | 数据压缩比
Compression reduces file size for storage and transmission. The compression ratio and space saving are defined as:
压缩可减小文件大小以便存储和传输。压缩比和空间节省率定义如下：
Compression ratio = Uncompressed size / Compressed size
Space saving = 1 – (Compressed size / Uncompressed size)
For instance, a 500 KiB file compressed to 200 KiB has a compression ratio of 2.5:1 and a space saving of 60%. Lossless compression (e.g., run‑length encoding, Huffman coding) allows exact reconstruction, while lossy compression (JPEG, MP3) sacrifices some data for higher ratios.
例如，一个 500 KiB 的文件压缩后为 200 KiB，压缩比为 2.5:1，空间节省率为 60%。无损压缩（如行程编码、哈夫曼编码）允许精确重建，有损压缩（如 JPEG、MP3）则牺牲部分数据以获得更高的压缩比。
The entropy of a data source sets a theoretical limit: Average code length ≥ Entropy. Entropy H = –Σ p(x)·log₂ p(x) for symbols with probability p(x).
数据源的熵设定了理论极限：平均码长 ≥ 熵。熵 H = –Σ p(x)·log₂ p(x)，其中 p(x) 是符号出现的概率。
11. Error Detection and Correction | 错误检测与纠正
IB Computer Science covers parity bits, check digits, checksums, and cyclic redundancy checks (CRC). A single parity bit can detect an odd number of bit errors but cannot correct them. The number of parity bits p for Hamming code to protect d data bits must satisfy:
IB 计算机科学涵盖奇偶校验位、校验位、校验和以及循环冗余校验 (CRC)。单个奇偶校验位可以检测奇数个位错误，但无法纠正。汉明码中为了保护 d 个数据位所需的奇偶校验位 p 必须满足：
2p ≥ d + p + 1
For a 4‑bit data word, p = 3 (since 2³ = 8 ≥ 4+3+1 = 8). The Hamming code then allows single‑ he data. The receiver divides the received message by the same generator polynomial; a non‑zero remainder indicates an error.
对于 4 位数据字，p = 3（因为 2³ = 8 ≥ 4+3+1 = 8）。汉明码便可以实现单错纠正。CRC 使用模 2 多项式除法；余数被附加到数据后面。接收方用同一个生成多项式去除接收到的消息；非零余数表明出现了错误。
12. Encryption and Key Space | 加密与密钥空间
Encryption transforms plaintext into ciphertext using an algorithm and a key. The security of symmetric encryption often depends on the key length. The number of possible keys for an n-bit key is 2ⁿ. For example, a 128‑bit key has 2¹²⁸ possible combinations, making brute‑force attacks infeasible. Asymmetric encryption (e.g., RSA) relies on the difficulty of factoring large integers. The RSA key generation uses:
加密使用算法和密钥将明文转换为密文。对称加密的安全性通常取决于密钥长度。n 位密钥的可能密钥数量为 2ⁿ。例如，128 位密钥有 2¹²⁸ 种可能组合，使得暴力攻击不可行。非对称加密（如 RSA）依赖大整数分解的困难性。RSA 密钥生成使用以下公式：
Select two large primes p, q; n = p·q; φ(n) = (p–1)(q–1)
Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
Compute d ≡ e⁻¹ (mod φ(n))
ption: m = cᵈ mod n. The security rests on the difficulty of finding d given only e and n.
加密：c = mᵉ mod n；解密：m = cᵈ mod n。其安全性基于仅凭 e 和 n 难以求出 d。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图