COMP5270 Week 1 总结：随机性、概率与算法（题解 + 知识点）

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 1 Lecture Notes + Tutorial 1 Solutions

---

Part 1: Tutorial 1 详细题解

Tutorial 开头的难度/要求说明

Tutorial 1 开头的要求不是按星号分级，而是按“lecture 前能不能做”来分。核心意思是：先尝试很重要，就算证明暂时不够严谨，也可以在 tutorial 里继续打磨。

题目	Tutorial 原文难度/要求	复习时怎么安排
Problem 1	更适合 lecture 后做，或者至少先看 lecture notes	用来练 indicator random variable 和期望线性性
Problem 2	更适合 lecture 后做，或者至少先看 lecture notes	继续练 run/counting problem 的建模
Problem 3	更适合 lecture 后做，或者至少先看 lecture notes	固定点的期望和方差，注意随机变量之间不独立也能算协方差
Problem 4	更适合 lecture 后做，或者至少先看 lecture notes	理解“期望可以是无穷大”
Problem 5	更适合 lecture 后做，或者至少先看 lecture notes	方差恒等式，属于后面分析随机算法的基础工具
Problem 6	更适合 lecture 后做，或者至少先看 lecture notes	自然数随机变量的 tail-sum expectation 公式
Problem 7	lecture 前也应该可以尝试并解决；第二部分若不直接使用 geometric 期望会比较 technical	必做，von Neumann trick 是很经典的随机化构造
Problem 8	lecture 前也应该可以尝试并解决	适合先自己想，重点是把条件概率关系列清楚
Problem 9	更适合 lecture 后做，或者至少先看 lecture notes	record/prefix maximum 的 indicator 分析
Problem 10	更适合 lecture 后做，或者至少先看 lecture notes	理解 XOR 随机变量和独立性的区别

Problem 1: 同花色连续对的期望数量

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。重点是把“相邻两张牌同花色”写成 indicator，再用期望线性性求总期望。

problem-1-cards-same-suit.png

题目: 4n 张牌，4 种花色各 n 张。随机洗牌后，相邻同花色对数的期望是多少？

详细题解:

第一题可以用"指示变量 + 期望线性性"完整做出来。

设随机变量

牌位有 ，所以相邻对一共有 个：。

对每个 ，定义

那么

由期望线性性：

现在算 （任意 都一样）：

• 先看第 张，不管它是什么花色；
• 剩下 张里，和它同花色的还剩 张。

所以

代回去：

结论：

补充两个容易错的点：

1. 不是 个相邻对，而是 个。
2. 不需要假设这些相邻事件独立；期望线性性永远成立。

---

Problem 2: 连续3个1的run的期望数量

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。本题延续 Problem 1 的思路，但事件变成“长度为 3 的窗口全是 1”。

problem-2-consecutive-runs-of-3-ones.png

第二题本质是在数：长度为 2024 的随机比特串里，有多少个位置 满足 。注意这里允许重叠，因为题目给了 1111 有 2 个（位置 1-3 和 2-4）。

设比特串是 ，每位独立且 。

1. 定义指示变量

为什么是 2022？因为长度为 3 的窗口起点只能到 。

2. 总个数写成和

3. 求每一项期望

4. 用期望线性性

结论：

补充：期望可以不是整数；它表示"重复很多次实验后的平均个数"。（这里不需要窗口之间独立，线性性直接成立。）

---

Problem 3: 排列的固定点期望与方差

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。这题比前两题更技术，因为方差部分要处理不同位置固定点之间的依赖关系。

problem-3-fixed-point-permutation.png

题目: 在 的均匀随机排列 中，定义不动点为满足 的位置 。设 为不动点个数。求 和 。

1. 定义指示变量

则

2. 先求期望

对任意 ，因为排列均匀随机， 在 上等可能：

所以

由期望线性性：

3. 求方差

已知 ，只需算 。

4. 展开

取期望：

关键在于"交叉项怎么计数"：

有两种等价写法：

• 按无序对写：（有系数 2）
• 按有序对写：（无显式 2）

不是 ，"2"乘的是交叉项，不是平方项。

5. 计算第一项

，所以 。因此

6. 计算第二项

用条件概率：

而 的有序对 个数是 ： - 有 种选择（ 到 任取） - 有 种选择（除了 之外的任意位置） - 所以共 个有序对

（注意这里是有序对， 和 算两个；如果写成无序对 ，则个数是 ，但此时每个无序对只出现一次，不需要前面展开时的系数 2。两种写法等价，只是计数方式不同。）

所以

7. 合并

结论：

---

知识点总结

1. 指示变量法：计数问题写成 。
2. 期望线性性：，不要求独立。
3. 随机排列对称性：。
4. 平方展开：。
5. 指示变量性质：。
6. 交集概率计算：，不是默认直接相乘。
7. 有序对计数： 共 个。
8. 方差公式：。

---

Problem 4: 期望无穷的随机变量

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。它的目标是提醒你：随机变量取值都有限并不代表期望一定有限。

problem-4-infinite-expectation.png

题目: 1. 给出一个定义在 上的随机变量 ，使得 。 2. 给出一个定义在 上的随机变量 ，使得 。

口诀

都是 收敛， 发散。

看"收敛/发散"就看极限是不是有限数。

1. 积分的收敛/发散（广义积分）

• 极限是有限数：收敛
• 极限是 或不存在：发散

2. 级数的收敛/发散

• 极限有限：收敛
• 否则发散

常用秒判：

-型积分

• 收敛
• 发散

-型级数

• 收敛
• 发散（如调和级数 发散）

比较法：如果 在无穷远处"长得像" ，就按上面判。你那题里：

所以积分发散，。

离散型 vs 连续型随机变量：

• 离散型：取值可数，用概率质量函数 ，期望：
• 连续型：取值在区间上，用密度函数 ，期望：

一句话：离散型用"求和"，连续型用"积分"。

3步模板（构造 ）

1. 先选"慢衰减尾巴"
   • 连续型常用：（在 ）
   • 离散型常用：
2. 调成合法分布（总概率=1）
   • 连续：乘常数 让
   • 离散：乘常数 让
3. 检查期望
   • 连续： 是否发散（通常变成 ）
   • 离散： 是否发散（通常变成 ）

4. 连续（）

5. 离散（）

---

Problem 5: 方差公式证明

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。这是基础证明题，后面用 Chebyshev、Chernoff 或分析 randomized algorithms 时会反复用到。

题目翻译: 证明课上的结论：如果随机变量 的方差有限，那么

解题过程:

设

由方差定义：

展开平方：

两边取期望（用期望线性性）：

因为 ，所以

证毕。

知识点:

1. 方差定义：
2. 代数展开：
3. 期望线性性：，
4. "方差有限"保证相关期望量是良定义的，推导合法。

---

Problem 6: 自然数随机变量的期望表示

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。本题是 tail-sum expectation 公式，之后 coupon collector 和很多 waiting-time 分析都会用到。

problem-4-infinite-expectation.png

题目翻译: 证明课上的结论：如果随机变量 取值于 ，且 ，那么

解题过程:

对每个样本点 ，因为 是非负整数，有恒等式

（若 ，右边前 项是 1，后面全是 0，总和就是 。）

两边取期望：

由于求和项非负，可用单调收敛定理（等价地 Tonelli）交换期望与无穷求和：

即得所证。

知识点:

1. 非负整数随机变量可写成指示变量和：。
2. 指示变量期望：。
3. 单调收敛定理 / Tonelli：非负项时可交换 与无穷和。
4. 尾和公式（tail-sum formula）：。
5. 条件 保证右侧级数是有限值。

---

Problem 7: von Neumann 公平硬币技巧

Tutorial 难度/要求: lecture 前也应该可以尝试并解决；但第二部分如果不直接使用 geometric random variable 的期望公式，会比较 technical。

problem-7-biased-coin-fair-toss.png

中文翻译:

假设你有一枚有偏硬币，正面概率为 ，但 的值未知。你的目标是：只能使用这枚有偏硬币，生成一次均匀随机的掷硬币结果（即公平硬币结果）。

1. 描述一种实现该目标的策略。
2. 给出一个关于未知参数 的界：为了生成一次公平结果，期望需要掷这枚有偏硬币多少次。

解题思路（标准做法：Von Neumann 方法）:

1. 连掷两次硬币。
2. 若结果是 HT，输出 H；若结果是 TH，输出 T。
3. 若结果是 HH 或 TT，丢弃这一轮，重新做第 1 步。

为什么公平：

两者相等，所以在"接受事件" 下，

期望掷币次数:

• 一轮成功概率

• 令 表示「直到第一次成功为止，需要尝试多少轮」。这里一轮就是连续掷两次硬币。

因为每一轮都是重新独立掷两次硬币，所以每轮成功概率都相同，都是 。因此：

一般地，第 轮才第一次成功，意思是前 轮都失败，第 轮成功，所以

这说明 服从参数为 的几何分布。为了看清楚为什么 ，可以用尾和公式：

其中 表示前 轮都失败。每轮失败概率是 ，所以

因此尾和公式变成

这是一个无穷等比级数。它的首项是 ，公比是 。因为 ，所以 ，可以使用公式

这个公式可以这样推出来。令

两边同时乘以 ：

两式相减，右边除了第一项 以外全部抵消：

所以

这里令 ，所以

• 每轮 2 次掷币，所以

这个值对该策略是精确值（不只是上界）。并且不存在与 无关的统一常数上界（当 或 时会变大）。

解这题需要知道的知识点:

1. 独立伯努利试验（每次掷币独立）。
2. 条件概率与对称性（）。
3. 拒绝采样思想（HH/TT 丢弃重来）。
4. 几何分布的期望（）。
5. 期望线性放缩（）。

---

Problem 8: 老鼠与猫的概率问题

Tutorial 难度/要求: lecture 前也应该可以尝试并解决。重点不是复杂公式，而是把状态、条件概率和对称性写清楚。 ![[Pasted image 20260526173735.png]] 题目: 老鼠要从 M 走到 C，图中有若干条路径。每条边独立地以概率 被猫占据。求：

(a) 老鼠仍有路径到达奶酪的概率； (b) 老鼠有长度不超过3的路径的概率； (c) 地图上猫的期望数量。

题解:

(a) 有路径的概率:

用补集计算更方便：

老鼠无路径当且仅当三条路径（上、中、下）都被阻断：

注意这里不是要求一条路径上的边全部被占。对老鼠来说，只要一条路径上有至少一条边被猫占据，这条路径就不能走了。

所以要区分两个事件：

• “路径完全畅通”：这条路径上的每条边都没有猫；
• “路径被阻断”：这条路径上至少有一条边有猫。

假设某条路径有 条边。每条边被猫占据的概率是 ，所以每条边没有猫的概率是 。由于题目说每条边是否被占据是独立的，因此这 条边都没有猫的概率是

这就是“这条路径完全畅通”的概率。

因此“这条路径被阻断”的概率是它的补集：

代入三条路径的长度：

• 上路有 2 条边，被阻断概率：；
• 中路有 3 条边，被阻断概率：；
• 下路有 4 条边，被阻断概率：。

老鼠“无路径”表示三条路都被阻断。因为三条路径使用的是不同的边，而每条边是否被占据相互独立，所以三条路径被阻断这三个事件也可以相乘：

验证: - : 概率 = ✅ - : 概率 = ✅

(b) 长度 的路径:

只考虑上路（2 边）和中路（3 边），忽略下路（4 边）：

(c) 猫的期望数量:

思路：把“总猫数”拆成每条边上“有没有猫”

设总共有 条边。对每条边 ，定义一个指示随机变量（indicator random variable）：

第一步：每条边的期望

题目说每条边以概率 被猫占据，所以：

对指示变量求期望：

这就是“一条边上猫的期望数量”——虽然只有 0 或 1 只猫，但期望就是概率 。

第二步：总猫数

设总猫数为 ，它是所有边上指示变量之和：

第三步：用期望的线性性

期望有一个非常好的性质——线性性：和的期望等于期望的和，无论这些随机变量是否独立！

第四步：数图中的边数

看回题目图： - 上路：M → a → C，共 2 条边 - 中路：M → b → c → C，共 3 条边 - 下路：M → d → e → f → C，共 4 条边

检查是否有共享边：从图上看三条路径的边是互不重叠的，所以总边数

最终结果：

验证： - 当 （没有猫）： ✅ - 当 （全是猫）： ✅ - 当 ：平均有 只猫 ✅

为什么这题不用管边之间的依赖？

期望线性性非常强大：不管边之间是独立还是相关，只要把它们拆成一个个 指示变量，期望就可以直接相加。这也是为什么指示随机变量在计数问题中特别好用。

解这题需要知道的知识点:

1. 补集思想：求"有路径"的概率，先算"无路径"再取补，往往更简单。
2. 独立事件的概率乘法：不同路径的阻断事件相互独立（因为边不重叠），可以直接相乘。
3. 路径畅通 vs 被阻断："畅通"要求所有边都没猫；"被阻断"只要求至少一条边有猫，用补集计算：。
4. 指示随机变量：把"边 上有没有猫"编码成 变量，方便计数和求期望。
5. 期望线性性：，无论变量是否独立都成立。
6. Bernoulli 变量的期望：，则 。

---

Problem 9: 前缀最大值的期望

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。这题是 record / prefix maximum 的经典 indicator 分析。 ![[Pasted image 20260526190118.png]]

题目: 设 是 个不同数的数组。若 是前 个元素中最大的，则称 为"prefix-maximum"（前缀最大值）。记 为数组 中 prefix-maximum 的总个数。

直观理解：从左往右扫描数组，每次遇到一个"创纪录"的新高，就算一个 prefix-maximum。例如数组 中，位置 1（值为3）、位置 3（值为4）、位置 5（值为5）都是 prefix-maximum，所以 。

(a) 若 递增排序， 是多少？ (b) 若随机排列得到 ，证明 。

题解:

(a) 递增数组:

每个元素都比前面所有元素大，所以所有 个位置都是 prefix-maximum：

（第1个元素也计入，因为它"大于前面空集合的所有元素"）

(b) 随机排列:

思路：用指示变量 + 期望线性性

设 为指示变量：

则 prefix-maximum 的总数为

关键：算

考虑前 个元素 。因为这 个数各不相同，且排列是均匀随机的，所以这 个元素在前 个位置上的分布也是均匀的。

换句话说：前 个位置中的最大值，等可能地出现在这 个位置中的任何一个。

因此，最大值恰好落在位置 的概率是：

用期望线性性求和

其中 是第 个调和数（Harmonic number）：

为什么 ？

调和数的增长速度可以用积分估计：

即

因此

更精确地，，其中 是欧拉常数。

结论：

直观理解： - ： 总是 prefix-maximum（概率 ） - ： 要成为 prefix-maximum，必须比 大，概率 - ： 要成为 prefix-maximum，必须是前 3 个中最大的，概率 - ... - ：概率

加起来就是调和数，增长非常慢（对数级）。

---

解这题需要知道的知识点:

1. 指示随机变量：把"位置 是否是 prefix-maximum"编码成 。
2. 期望线性性：，不需要独立性。
3. 随机排列对称性：前 个元素中最大的那个等可能出现在 个位置中任何一个。
4. 调和数：。
5. 积分估计调和数：。
6. 前缀最大值的意义：在随机数据流中，"创纪录"的次数期望是对数级的。

Problem 10: XOR 的随机变量

Tutorial 难度/要求: 更适合 lecture 后做，或者至少先看 lecture notes。重点是区分 pairwise independence、mutual independence 和由 XOR 关系带来的约束。 ![[Pasted image 20260526191938.png]]

题目: 设 是独立 Bernoulli() 随机变量， 也是 Bernoulli()。

(a) 对 ，计算前几项并给出通项； (b) 求 ； (c) 给出递推关系； (d) 求解递推并证明收敛性。

题解:

先把符号说清楚。

的意思是：

也就是说，每个 都是一个随机比特。

表示 XOR，也叫异或。两个比特的异或规则是：

0	0	0
0	1	1
1	0	1
1	1	0

一句话记忆：

多个比特异或时，有一个很重要的等价理解：

当且仅当 里面 1 的个数是奇数。

例如：

因为有 1 个 ，是奇数。

因为有 2 个 ，是偶数。

题目说 也是 Bernoulli()，意思是：

所以这题本质是在问：

个独立 Bernoulli() 随机变量异或起来，结果等于 1 的概率是多少？

---

(a) 特殊情况

情况 1：

如果 ，那么每个 都一定是 0：

所以

因此：

也就是：

---

情况 2：

如果 ，那么每个 都一定是 1：

所以 就是 个 1 的 XOR。

看前几项：

这里 表示空 XOR，通常定义为 0。

所以规律是：

• 为奇数时，
• 为偶数时，

因此：

也可以写成：

因为：

• 偶数时，，所以
• 奇数时，，所以

---

情况 3：

如果 ，每个 都是公平比特：

直觉上，公平比特 XOR 另一个独立公平比特，结果仍然是公平比特。

看 ：

看 ：

当且仅当两个比特不同：

所以：

这个性质会一直保持下去，所以：

(b) 初始值:

这里要算 。

第一项：

是空 XOR，定义为 0：

所以：

第二项：

而 ，所以：

第三项：

当且仅当 不一样：

所以：

因为 独立：

所以：

结论：

(c) 递推关系:

现在要把 用 表示。

注意：

而

所以：

现在问 的概率。

根据 XOR 规则， 当且仅当两者不同：

1. 且
2. 且

因此：

因为 和前面的 独立，所以 和 独立。

第一项：

第二项：

所以：

展开：

因此递推式是：

(d) 求解与收敛:

我们已经有：

这是一个一阶线性递推。

直接看它不太像等比数列，因为后面多了一个 。处理这种递推的常用技巧是：先找一个稳定点。

假设 稳定在某个数 ，那么应该满足：

移项：

如果 ，得到：

所以我们以 为中心，设：

也就是：

代入递推式：

右边展开：

注意：

所以：

两边减去 ：

这就变成等比数列了。

因为：

所以：

而 ，所以：

收敛性:

看通项：

如果：

那么：

也就是：

所以：

因此：

结论：

这说明：只要每个 不是永远 0、也不是永远 1，那么很多个独立比特 XOR 之后，结果趋向于公平比特。

特殊边界情况：

• ：所有 都是 0，所以 ，不趋向 。
• ：所有 都是 1，所以 在 0 和 1 之间振荡，不收敛。
• ：从 开始就已经是 。

---

解这题需要知道的知识点:

1. Bernoulli 随机变量： 表示 只取 0 或 1，且 。
2. XOR 规则：两个比特不同则 XOR 为 1，相同则 XOR 为 0。
3. 多个 XOR 的奇偶性理解： 当且仅当 1 的个数为奇数。
4. 独立性乘法：因为 独立于前面的变量，所以 独立于 。
5. 全概率分情况： 可以拆成两种互斥情况： 和 。
6. 递推式：通过 得到 。
7. 解一阶线性递推：先找稳定点 ，再设 ，把递推变成等比数列。
8. 收敛判断：如果 ，则 ，所以 。

---

Part 2: 讲义核心知识点

---

1. 什么是随机化算法？

随机化算法的行为不仅依赖于输入，还依赖于随机比特串 。

等价视角：随机化算法可以看作确定性算法族的概率分布：

运行时先随机选 ，再运行 。

关键分析维度：

1. 输出正确性: 总是正确？还是高概率正确？
2. 运行时间: 总是有界？还是期望有界？高概率有界？

---

2. 两类随机化算法

🔷 Las Vegas 算法

• 总是正确（输出100%正确）
• 运行时间只在期望上有界（worst-case 时间无界）

🔶 Monte Carlo 算法

• 只在高概率下正确（可能出错）
• 运行时间总是有界（worst-case 确定）

示例：找偶数

问题: 给定数组 包含 到 的所有数，输出一个偶数的下标。

类型	结论
确定性	最坏情况时间
Las Vegas	期望时间 ，总是正确
Monte Carlo	最坏情况时间 ，成功率 99%

Las Vegas 做法：随机选下标，若为奇数则重来。期望 次抽到偶数。

---

3. 四种分析类型总结

分析类型	公式	含义
Worst-case		最坏输入下的表现
Expected		算法随机化时最坏输入的期望时间
Average-case		输入服从某个分布时的期望
Amortized		多次运行时的平均最坏表现

---

4. 随机化 QuickSort 分析

算法回顾

QuickSort(A):
  if |A| ≤ 1: return A
  随机选 pivot p
  划分 A 为 A₁(<p), A₂(=p), A₃(>p)
  递归排序 A₁ 和 A₃
  合并返回

期望时间复杂度

定理: 随机化 QuickSort 的期望运行时间为 。

证明方法 1: 猜测 + 归纳法（设 ）

证明方法 2: 将递推与微分方程比较

引入原函数 后化为：

解得 。

比较次数分析（更优雅的证明）

定理: 期望比较次数 = 。

设 为排序后的元素， 指示 和 是否被比较过。

总比较次数：

由线性性：

关键观察: 两个元素被比较，当且仅当它们中第一个被选为 pivot 时，另一个还在同一子数组中。即 pivot 必须是 或 ，且落在 到 的范围内。

所以：

其中 为第 个调和数。

⚠️ 注意：最坏情况时间仍是 ！

---

5. 概率论基础工具箱

期望的基本定义

设 是离散随机变量，取值集合为 ，概率质量函数为 。则 的期望（Expectation）定义为：

直观：期望就是每个可能取值乘以其发生概率的加权和。它代表「长期重复实验中的平均值」。

例如， 是以概率 取值 1、以概率 取值 0 的 Bernoulli 随机变量：

再如，彩票问题中一张票净盈亏 的分布为：中奖时净赚 （概率 ），不中时亏 （概率 ），则：

注意： 不一定是 能取到的值（比如 Bernoulli 期望是 ，但 只能取 0 或 1）。期望是「平均值」，不是「最可能值」。

---

Fact 1: 自然数随机变量的期望

若 取值于 ：

记忆技巧：令 ，则 ，若从 开始 ，所以从 开始。

Fact 2: 方差公式

推论: （有时有用）。

Fact 3: 期望的线性性（最核心！）

不需要 独立！

推广：

Fact 4: 方差的性质

• 若 独立：
• 若 两两独立（pairwise independent）：

⚠️ 两两独立比相互独立弱！

Jensen 不等式

若 是凸函数：

若 是凹函数，不等号反向。

记忆：用 （凸函数），，所以 。

---

6. Bernoulli 分布与指示随机变量

Bernoulli 随机变量

Bernoulli 随机变量就是只记录一件事：成功还是失败。

如果成功记为 ，失败记为 ，且成功概率是 ，那么

并且

这时记作

举例：

• 掷一枚公平硬币，令 表示正面， 表示反面，则 。
• 随机抽一张牌，令 表示抽到红桃， 表示没抽到红桃，则 。

期望的计算直接来自定义：

所以 Bernoulli 随机变量的期望就是它取 的概率。

还有一个很常用的性质：

原因是 只能取 或 ：

因此

方差为

并且 ，最大值在 处。

指示随机变量

指示随机变量是 Bernoulli 随机变量最常见的用法：把一个事件 是否发生，转成 。

对于事件 ，定义：

因为 也只会取 或 ，所以它是一个 Bernoulli 随机变量。它取 的概率就是事件 发生的概率：

所以

因此它的期望是

这句话非常重要：指示随机变量的期望 = 对应事件发生的概率。

例如 Problem 1 中，我们定义

那么

所以如果总数是

那么用期望线性性：

这就是为什么很多计数题都会先定义指示随机变量：它把“数有多少个事件发生”变成了“把很多个 0/1 加起来”。

二项分布

： 个独立同分布 Bernoulli() 之和。

也就是说，如果

其中每个 ，并且它们相互独立，那么

直观理解： 表示 次独立尝试中，成功了多少次。

例如掷 次硬币，每次正面概率是 ，令 表示正面出现次数，则

期望：

如果这些 Bernoulli 变量独立，则方差也可以相加：

---

7. 使用随机化的原因与局限

✅ 优点

• 快速找到代表性样本（大数据集采样）
• 避开病态的最坏情况输入
• 避免可预测的行为（安全性）
• 允许更简单或更高效的算法设计

⚠️ 局限

• 行为是随机的（输出或运行时间不确定）
• 随机比特从哪来？（实际中靠伪随机数生成器）

---

Part 3: 符号速查表

一、渐近复杂度符号（详细版）

渐近复杂度符号用来描述函数在 很大时的增长趋势。核心思想是：忽略常数和低阶项，只关心主导项的数量级。

例如：，当 时， 项主导，所以 。

---

1. 为什么需要渐近符号？

实际算法分析中，我们关心的是：当输入规模 很大时，运行时间/空间随 增长的趋势。不同机器上的常数因子差异（CPU速度、语言实现）可以忽略，但增长趋势决定了算法在大数据上的可扩展性。

---

2. ：上界（Big-O）

定义：存在正常数 和 ，使得对所有 ：

记作 。

直观： 的增长速度至多是 的常数倍。

例子验证： - ：取 ，则 对 成立。 - ：取 ，则 对 成立。 - ：虽然不够精确，但数学上成立（线性不会超过二次）。

常见误区： 只是上界，不是最紧的。说 是对的，但比较粗糙。

---

3. ：下界（Big-Omega）

定义：存在正常数 和 ，使得对所有 ：

记作 。

直观： 的增长速度至少是 的常数倍。

例子验证： - ：取 ，则 对 成立。 - ：二次函数至少比线性快。

---

4. ：紧确界（Big-Theta）

定义：存在正常数 和 ，使得对所有 ：

记作 。

直观： 和 是同一量级的增长速度。同时有上界和下界。

等价条件： 当且仅当 且 。

例子： - ：因为 和 都成立。

---

5. 和 ：严格上界/下界（小 o 和小 omega）

这些符号表示严格更小/更大的渐近关系，不带常数。

小 o： 当且仅当

直观： 的增长速度严格慢于 ，即使乘以任何常数也不够。

例子： - ：。 - ：比值趋于 1，不是 0。 - ：对数增长严格慢于线性。

小 omega： 当且仅当

例子： - ：。

---

6. 常见复杂度等级（从慢到快）

复杂度	名称	例子
	常数	数组随机访问
	对数	二分查找
	线性	遍历数组
	线性对数	归并排序、快速排序（期望）
	平方	冒泡排序、嵌套循环
	指数	子集枚举
	阶乘	全排列枚举

重要： 虽然比 多一个 因子，但它仍然属于"高效"算法，因为 这种指数级会完全碾压它。

---

7. 多项式函数的渐近判断法

对多项式 （）：

原因：提取最高次项：

当 时，括号内趋于 ，所以 。

例子： - - （这里 是常数， 是低阶线性项，被 主导）

---

8. 三个符号关系总结

符号	中文	含义	与 的关系
	Big-O	上界
	Big-Omega	下界
	Big-Theta	紧确界	上下都卡住
	Small-o	严格上界
	Small-omega	严格下界

一句话记忆： - ：不要超过它（最多） - ：不会低于它（至少） - ：上下都卡住，刚好这个量级 - ：严格比它小 - ：严格比它大

---

9. 为什么 ？

这是 Week 3 Coupon Collector 中出现的典型例子。详细拆解：

当 时：

所以括号内 ，因此 。

验证 定义： - 上界：取 ，，所以 ，取 。 - 下界：取 ，，所以 ，，取 。

因此 。

二、概率与统计符号速查

符号	名称	核心含义
	概率	事件发生的可能性，取值
	期望	随机变量的长期平均值
	方差	随机变量围绕期望的波动程度
	服从分布	的概率分布是
	伯努利分布	，
	二项分布	次独立 Bernoulli 之和
	调和数

三、积分与级数收敛速判口诀

• : 收敛
• : 发散

常用例子： - 调和级数 发散 - 收敛（Basel问题） - 发散（对数发散）

---

核心方法总结

技巧	应用场景
期望的线性性	计数问题、指示变量求和
指示随机变量	将复杂事件分解为简单指示器
补集概率	"至少一个"转为"全都不"
交换求和顺序	双重求和、期望的积分表示
递推关系	序列问题、动态期望计算
中心化处理	找不动点简化递推

---

核心公式速查

公式	内容
期望线性性	（无需独立）
方差
自然数期望
调和数
Bernoulli 方差
二项分布	,
指示变量

---

整合自旧笔记 COMP5270.md + 新讲义总结，完成于 2026-05-25

---

Part 3: Week 1 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

If X is indicator of event E, then E[X] = Pr[E]. | 选项 | 答案 | |:---|:---| | 1 | ❌ | | 0 | ❌ | | Pr[E] | ✅ | | 1/2 | ❌ |

Question 2

Ω(n log n) lower bound doesn't apply to randomised algorithms. | 选项 | 答案 | |:---|:---| | False | ✅ | | True | ❌ | > 决策树下界与是否随机化无关。

Question 3

Randomised QuickSort is Las Vegas. | 选项 | 答案 | |:---|:---| | Both | ❌ | | Neither | ❌ | | Monte Carlo | ❌ | | Las Vegas | ✅ |

Question 4

If X has well-defined variance and expectation, Var[X] ≤ E[X²]. | 选项 | 答案 | |:---|:---| | Var[X] ≤ E[X²] | ✅ | | Var[X] = E[X] | ❌ | | Var[X] ≤ E[X]² | ❌ | | Var[X] = E[X]² | ❌ |

Question 5

Expected comparisons by Randomised QuickSort: O(n log n). | 选项 | 答案 | |:---|:---| | O(n) | ❌ | | O(1) | ❌ | | O(n log n) | ✅ | | O(n²) | ❌ |

Question 6

Randomised algorithm always gives different answers with different random strings. | 选项 | 答案 | |:---|:---| | False | ✅ | | True | ❌ |

Question 7

Fast randomised algorithm for primality testing (Miller-Rabin). | 选项 | 答案 | |:---|:---| | Primality testing | ✅ | | Prime→integer | ❌ | | Factoring | ❌ | | Factoring a prime | ❌ |

Question 8

Same input + same random bits = same output. | 选项 | 答案 | |:---|:---| | Yes | ✅ | | No | ❌ | | Depends | ❌ |

Question 9

Limitation of randomised algorithms: assume access to good randomness. | 选项 | 答案 | |:---|:---| | Always better | ❌ | | Assume good randomness | ✅ | | Harder to analyze | ❌ | | Usually slower | ❌ |

Question 10

Expected time O(1) → worst-case always O(1). False. | 选项 | 答案 | |:---|:---| | False | ✅ | | True | ❌ | > 期望小不代表最坏小（99% O(1), 1% O(n!)）。

Week 1 Quiz 速查表

题号	核心概念	正确答案
1	指示变量期望	Pr[E]
2	排序下界	False
3	QuickSort 类型	Las Vegas
4	方差不等式	Var ≤ E[X²]
5	QuickSort 期望时间	O(n log n)
6	随机串不同≠答案不同	False
7	质数判定	Primality
8	确定性	Yes
9	随机化限制	Good randomness
10	期望≠最坏	False

高频混淆点： - Las Vegas (正确但时间随机) vs Monte Carlo (时间确定但可能错)（Q3） - 指示变量期望=概率（Q1） - 期望小≠最坏小（Q10）