Year 13 Edexcel Computer Science: Formula & Theorem Quick Reference | Year 13 Edexcel 计算机：公式定理速查手册

📚 Year 13 Edexcel Computer Science: Formula & Theorem Quick Reference | Year 13 Edexcel 计算机：公式定理速查手册

This quick reference handbook collects essential formulas, laws, and theorems for the Year 13 Edexcel A‑Level Computer Science course. Use it to check asymptotic complexities, Boolean algebra rules, data representation calculations, normalisation steps, and more – all paired with concise Chinese translations to reinforce understanding.

本速查手册汇集了 Year 13 Edexcel A‑Level 计算机科学课程的核心公式、定律与定理。您可以在此查阅渐近复杂度、布尔代数规则、数据表示计算、规范化步骤等内容，每个条目均配有简洁的中文翻译以加深理解。

1. Big O Notation & Asymptotic Complexity | Big O 表示法与渐近复杂度

Big O notation describes the tightest upper bound on an algorithm’s time or space growth rate as the input size n grows. It focuses on the dominating term and ignores constant factors.

Big O 表示法描述当输入规模 n 增大时算法时间或空间增长率的最紧上界。它关注主导项并忽略常数因子。

O(1) – Constant time: runtime is independent of input size, e.g., array index access or a single arithmetic operation.

O(1) – 常数时间：运行时间与输入规模无关，例如数组索引访问或单个算术运算。

O(log n) – Logarithmic time: the algorithm discards a portion of the data at each step; binary search walking down a balanced tree is a classic example.

O(log n) – 对数时间：算法每步都舍弃一部分数据；二分查找和在平衡树中向下遍历是最佳实例。

O(n) – Linear time: the work grows in direct proportion to n; typical for a single loop, linear search, or traversing an entire list.

O(n) – 线性时间：工作量与 n 成正比；常见于单层循环、线性搜索或遍历整个列表。

O(n log n) – Linearithmic time: often seen in efficient divide‑and‑conquer sorting algorithms such as merge sort and the average case of quicksort.

O(n log n) – 线性对数时间：常见于高效分治排序算法，如归并排序和快速排序的平均情况。

O(n²) – Quadratic time: runtime scales with the square of the input size; typical for nested loops (bubble sort, insertion sort) or simple matrix operations.

O(n²) – 平方时间：运行时间与输入规模的平方成正比；典型例子有嵌套循环（冒泡排序、插入排序）或简单的矩阵运算。

O(2ⁿ) – Exponential time: the growth doubles with each additional element; frequently appears in brute‑force combinatorial problems and naive Fibonacci recursion.

O(2ⁿ) – 指数时间：每增加一个元素，工作量翻倍；经常出现于暴力组合问题和朴素递归求斐波那契数。

Space complexity follows the same Big O conventions and counts the extra memory (beyond the input) that an algorithm allocates.

空间复杂度遵循相同的 Big O 规则，并计量算法额外分配的内存（输入本身除外）。

2. Array & Linked List Operations | 数组与链表操作复杂度

An array provides O(1) indexed read/write but requires O(n) for insertion or deletion at arbitrary positions because elements must be shifted.

数组提供 O(1) 的索引读写，但因元素需要平移，在任意位置插入或删除需要 O(n)。

Inserting at the end of a dynamic array (e.g., Java ArrayList) is O(1) amortised; a resize copies all elements only occasionally, giving an overall constant average cost.

在动态数组（如 Java ArrayList）末尾插入的均摊复杂度为 O(1)；扩容仅偶尔发生，整体平均开销为常量。

A singly linked list supports O(1) insertion or deletion at the head, but accessing an element by index or searching takes O(n) because the list must be traversed from the head.

单向链表支持表头 O(1) 的插入或删除，但按索引访问或搜索需 O(n)，因为必须从头遍历。

Deleting a given node in a singly linked list typically requires O(n) to find the predecessor unless a doubly linked list is used, which permits O(1) deletion when the node reference is already known.

删除单向链表中给定节点通常需要 O(n) 寻找前驱；若使用双向链表且在已知节点引用时，删除可做到 O(1)。

A doubly linked list supports O(1) insertion or removal at both ends and O(1) removal of a referenced node, but search remains O(n).

双向链表支持两端 O(1) 插入或删除，以及 O(1) 删除已知引用的节点，但搜索仍为 O(n)。

3. Stacks, Queues & Basic Tree Operations | 栈、队列与基本树操作

Stack operations (push, pop, peek) all run in O(1) when implemented with an array and a top pointer, or with a linked list.

栈操作（push、pop、peek）若使用数组加栈顶指针或链表实现，均为 O(1)。

Published by TutorHao | Year 13 Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）