COMP5270 Week 8 总结：Streaming and Sketching I（题解 + 知识点）

Posted on 2026-06-14 Edited on 2026-09-29 In Course Notes , COMP5270 Word count in article: 8.9k Reading time ≈ 32 mins.

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

Part 1: Tutorial 8 详细题解

本部分按官方 Solutions PDF整理，每题含完整题目和逐步展开的详细解答。

Tutorial 难度总览

题目	所属部分	难度	复习建议
Problem 1	Warm-up	需读讲义；median-of-means 证明梳理	必做：理解为什么要"均值的中位数"
Problem 2	Warm-up	需读讲义；"mean-of-medians" 对比	概念题：理解顺序不能互换
Problem 3	Warm-up	需读讲义；BJKST 真随机 vs 强 universal	概念题：理解强 universal 省空间的作用
Problem 4	Warm-up	需读讲义；BJKST 用的原因	概念题：理解两层哈希省空间
Problem 5	Problem Solving	重要，必须检查是否理解 Morris Counter	重点：逐步推导 careful variant 的期望、方差和空间
Problem 6	Problem Solving	短但需要关键想法；若没思路可直接看解答	推荐：Heavy Hitters 如何从 Misra-Gries 修改得到
Problem 7	Problem Solving	较复杂，但有价值；可以跳过但要看算法和解答	推荐：Bottom- 算法的 distinct elements 分析
Problem 8	Advanced	了解即可	扩展：流式 JL 降维计算均值向量大小

Problem 1: Morris Counter 的 median-of-means 证明梳理

题目: 过一遍 Morris Counter 的"median-of-means"证明，理解为什么需要这个技巧。

题解:

已知 Morris Counter 的随机变量（最终返回）满足（见 Lemma 40.1）：

为什么直接用 Chebyshev 不够

由 Chebyshev 不等式，对估计量：

当时，，这是一个无意义的界（失败概率）。问题的本质是方差与均值的平方同阶（，），Chebyshev 给不出小的相对误差界。

第一步：均值法降方差（means）

独立运行个 Morris Counter，取均值：

现在 Chebyshev 给出：

取，可以让失败概率降到（常数，比如），获得以常数概率成立的估计。

第二步：中位数法升概率（medians）

对失败概率为常数（比如）的算法，独立运行份，取这些估计的中位数。

若超过一半的运行都失败了，则中位数也会是坏估计，但这事件的概率以指数速度衰减（类似 Chernoff 界），最终失败概率降到。

组合：总空间

每份均值组需个 Counter，每个 Counter 用 bits（下文讲义分析），共份：

Problem 2: "mean-of-medians" 为什么不行

题目: 如果换成"先取中位数、再取均值"（mean-of-medians），会发生什么？

题解:

"均值的中位数"（median-of-means）有效是因为：先用均值法让每个副本的失败概率降到常数（比如），然后对多个副本取中位数，中位数在多数副本正确时也正确，以指数速度降低总失败率。

如果改成"中位数的均值"（mean-of-medians）：先对个 Counter 取中位数，再对多个这样的副本取均值——但问题是，单个 Counter 的失败概率本来就很高（接近），取中位数并不能改变这一点（中位数和单个副本的失败概率相仿）。然后对这些"质量差"的估计取均值，均值的失败概率依然很高。

结论: 降概率的正确顺序是"先均值降方差，再中位数降尾概率"，顺序不能互换。

Problem 3: BJKST 中用真随机 hash 会怎样

题目: 如果 BJKST 算法中用真随机 hash function 替代强 universal hash family，空间复杂度变成多少？

题解:

强 universal hash family 只需 bits 来描述（例如用线性哈希，只存）。

而一个真随机 hash function 需要为每个输入独立记录输出，需要 bits 来存储完整的真值表。

BJKST 中的空间代价里，存的项从增长到，这远超我们的目标 ——完全失去了流式算法的意义。所以必须使用具有紧凑表示的哈希族（如强 universal family）。

Problem 4: BJKST 中为什么存而不是

题目: 理解 BJKST 算法为什么使用哈希函数，如果把换成直接存，会怎样？

题解:

BJKST 里维护一个集合，存的是对。把元素映射到一个小空间（），存只需 bits。

如果改为直接存，每个元素需要 bits，最大约，总共需要

而存只需 bits，指数级更省。的作用就是在保留"指纹"功能（能区分不同的元素）的同时大幅缩短每个元素的表示长度，节省空间是其核心目的。

Problem 5: Morris Counter 的"careful variant"分析

题目: 分析 Morris Counter 的"careful variant"——将乘以的概率是（而非原版的乘以的概率）。

(a) 计算算法末尾的期望。 (b) 计算方差，并用 Chebyshev 得出结论。 (c) 如何设置以得到带中位数技巧的估计？给出空间复杂度。 (d) 如何设置以不用中位数技巧得到估计？给出空间复杂度，从而证明 Theorem 42。 (e) 如何实现增量步骤（"以概率将乘以 "）？

题解:

(a) 计算期望

设为第步被乘以的事件的指示随机变量（概率），则

条件期望：

由全期望律：（若第步事件发生，否则）。

以为初值，归纳得

因此是（真实计数）的无偏估计。

(b) 计算方差

计算：

（展开，利用（指示变量），。）

由，递推：

方差：

等价地，（对大）。

由 Chebyshev：

为让失败概率（常数），需，取。

(c) 带中位数技巧的参数设置

设，此时 Chebyshev 给出常数成功概率（）。再用中位数技巧：独立运行份，取中位数，总失败概率。

空间分析: 算法存储变量，其中，故

（利用对小）。存储需 bits：

总空间（份）：

(d) 不用中位数技巧

直接让单次成功概率，需，取。

此时的最大值为，存储需

总空间（单份）：

与 Theorem 42 一致：doubly logarithmic in ，logarithmic in 和。

(e) 如何实现增量步骤

需要以概率产生 Bernoulli 随机变量。

关键障碍: 是的整数次幂，即，所以。若是无理数，没有有限精度表示。

解决方案: 先把四舍五入到最近的有理数，满足（有理数稠密，总能做到）。用代替运行算法：误差不会变大（因为），空间只多常数 bits（）。

此时是有理数。实现 Bernoulli：均匀随机选，若则返回 1，否则返回 0。

Problem 6: -Heavy Hitters（频繁元素集合）

题目: 设为 -heavy hitters 集合。修改 Misra-Gries 算法，使其输出满足，即输出所有 -heavy hitters（不遗漏）且输出的元素都至少是 -heavy hitter（不误报太多）。要求一趟、空间。

题解:

用参数运行 Misra-Gries 算法，得到估计，其误差保证为（Theorem 40，参数对应）。

输出。

包含性 ：若，即，则

所以。不会遗漏任何 -heavy hitter。

包含性 ：若，即，则（因为），所以。

空间: 个元素，每个 bits，总空间。

Problem 7: Bottom- 算法的 Distinct Elements 分析

题目: 考虑以下"Bottom-"算法，为参数。选强 universal hash ，维护（流中所有元素哈希值的最小个），最终返回。

(a) 证明对，以至少概率返回估计的。

(b) 空间复杂度是多少？

题解:

(a) 正确性分析

设为 distinct elements 的数目。

关键转化: 定义指示随机变量，其中遍历所有 distinct elements。则：

$至少个的值$

期望: 由的 marginal uniformity（强 universal 每个均匀分布在）：

方差: 由 pairwise independence（强 universal family 保证），两两独立，且：

Chebyshev: 取，对关于均值的偏离：

（最后一步取）。

即。

对称地（定义，类似分析），可得

Union bound：（需要多次重复 + 中位数以达到）。

实际上对使用中位数技巧后总失败率，即以概率成功。

(b) 空间复杂度

需存： - hash function （取为有理化版本）： bits - 个哈希值： bits - 中位数技巧份

总空间：

Part 2: 讲义知识点详解

按讲义（Week 8 - Streaming and Sketching I）结构整理，涵盖所有 Algorithm、Theorem、Lemma 及其完整证明。

§0 名词与符号速查

符号	含义
	流的长度（stream length）
	universe 大小（）
	算法使用的空间（bits）
	元素在流中出现的频率：
	distinct elements 的数目（）
	distinct elements 数：
	流长度：
	的二进制表示中末尾的个数（等价于整除的最大的幂次）

§1 流式算法的基本设定

设定: 输入通过流给出，每个。算法只能使用 bits 的工作内存，通常目标是：

$或$

允许随机算法和近似算法，近似参数（通常视为小常数）。

Quiz 知识点：Canvas 原题问 "流式设定中，输入以____顺序到达"，答案是 Arbitrary（任意顺序）。这与上面的设定一致——streaming 算法不假设输入顺序。

Quiz 知识点：原题问 "大多数 streaming 问题可用随机化算法以空间精确求解"（True/False），答案是 False。许多 streaming 问题需要空间才能精确求解，这是 streaming 理论的核心下界。

§2 Majority 问题

问题: 流中是否存在某个元素使得？

为什么这个问题在 streaming 中不 trivial：

在普通（非 streaming）设置中，这个问题很简单：遍历一次数组，用哈希表或数组记录每个元素的出现次数，然后找最大值。这需要或的空间。

但在 streaming 设置中，universe 大小可能远大于可用空间。例如，（所有可能的 IP 地址），但内存只有 bits。此时无法存储所有元素的计数器。

关键观察：如果某个元素是 majority（出现次），那么它有一个非常有用的性质：如果把和其他每个元素都 "配对" 然后一起删除，仍然会剩下至少一个。这个观察是 Boyer-Moore Majority Vote 算法的基础，也是 Misra-Gries 算法的核心思想。

Majority 的特殊性： - 最多只有 2 个元素可以出现次 - 最多只有 1 个元素可以出现次 - 所以如果我们能筛选出候选集合（大小只有），就可以用第二趟来精确验证

§3 Misra-Gries 算法（Algorithm 15）

历史背景：由 Jayadev Misra 和 David Gries (1982) 提出。算法也称为 "Frequent" 或 "Heavy Hitters" 算法。是 Boyer-Moore Majority Vote 算法的推广。

算法描述（用 "配对抵消" 直观理解）

参数，。维护一个最多个元素的计数器字典（用平衡二叉搜索树或链表实现）。

每个计数器表示元素的当前估计频率。算法的核心操作可以重新表述为：

元素出现：若已在中，计数加（ "多了一次自由出现"）
新元素加入：若不在中但，加入且计数为
配对抵消（关键步骤）：若不在中且（已满），则将中所有计数器减（到则删除）。这相当于：新来的和中每个已有的元素各"配对"一次，然后全部删除。

直观：把个元素（新来的加上中个已有元素）各取一次组成一组，全部抵消。这个元素各减少一次出现，相当于"消耗"了个流中的元素。

Theorem 40: Misra-Gries 算法保证

定理: Misra-Gries 算法是确定性的一趟算法，对参数，输出所有元素的频率估计满足：

空间复杂度。特别地，可以用两趟解决 Majority 问题。

证明:

空间复杂度分析: 中至多个元素，每个元素需要存储其标识（ bits）和计数器值（ bits，因为计数）。总计。

上界：

的值只在以下两种情况增加： - 元素出现时且已在中（Line 6）： - 元素出现且不在中但（Line 8）：

只在出现时才会增加，且每次最多增加。因此不会超过在流中真实出现的次数：

下界（关键证明）：

考虑被减少的次数。只在 Line 11（"全体减 "）时被减少。每次 Line 11 执行时，恰好个已有计数器各减，加上新元素那一次未被加入（因为已满），总共可以看作是 个计数器各减 。

等价视角：每次执行 Line 11，相当于从流中选取了个元素（个已在中的元素，加上新来的元素），把这个元素各取一次配对，然后全部删除。因此每次 Line 11 "消耗"了个流中的元素。

整个流共有个元素，所以 Line 11 最多执行次。因此被减少的总次数至多为：

$被减少的次数$

由于，所以：

Majority 问题的两趟解法（详细说明）

第一趟：用运行 Misra-Gries，即（最多维护个计数器）。

得到候选集合
若存在 majority 元素（即），则：

所以（不会遗漏 majority 元素）。

集合大小（至多个候选）。实际上因为中每个元素满足，而（每个计数器的值不超过其真实频率），所以。

第二趟：重新遍历流（或保留流的数据），精确计数中每个候选元素的出现次数。检查是否有某个候选元素出现次。

第二趟只需记录最多个计数器，每个 bits
总空间：（第一趟存）（第二趟）

Quiz 知识点：Canvas 原题问 "Misra-Gries 算法是____的"（Randomised/Deterministic），答案是 Deterministic。MG 的确定性源于它不依赖任何随机比特——计数器更新规则完全由输入决定。

Quiz 高频混淆点：原题问 "Misra-Gries 可用单次遍历、空间解决 MAJORITY 问题"（Yes/No），答案是 No。MG 解决的是 Frequent Elements（Heavy Hitters），不是 MAJORITY 问题本身。虽然可以用 MG 配合第二趟验证来解决 MAJORITY，但单次遍历只能给出频率估计，不能直接判断是否存在。

为什么不能一趟解决 Majority？

如果要求一趟算法，且的小空间，那么必须允许随机化和近似。但 Misra-Gries 本身已经是确定性的了，一趟给出的是的估计。对于 Majority 问题，我们需要的精确判断（或），而 Misra-Gries 一趟只能保证，无法区分和（差距只有，而误差界是）。所以需要第二趟来精确验证。

§4 近似计数问题（Approximate Counting）

问题: 流中有个（其余为），估计的值，允许近似误差。

§5 Morris Counter（Algorithm 16）

算法描述

维护整数（初始为）：

每次事件时，以概率令（用 Bernoulli）。
输出。

空间（只存，的值以高概率不超过，故用 bits）。

Lemma 40.1: Morris Counter 的期望与方差

引理: 设（第步后的值），。则：

证明（期望）:

对任意：

$若且成功（概率）否则$

其中。条件期望：

由全期望律（Law of Total Expectation），。从递推：

同时得到更一般的公式（式 58）：。

证明（方差，计算）:

计算条件期望：

展开平方：

由于，故；且，故。因此：

取期望：

所以：

由全期望律：

代入式 (58)：，得：

关键化简（讲义中称为 "magical" step）：由于，分两种情况验证： - 若：左边，右边，等式成立； - 若：左边，右边，等式成立。

因此：

累加求和：

对双求和进行化简：

其中用到故。令，则上式等于。因此：

故：

Quiz 知识点： - 原题问 "Morris Counter 用_空间近似统计流中非零元素个数"，答案是。Vanilla Morris Counter 只存一个计数器，而 whp，所以只需 bits。 - 原题问 "Vanilla Morris Counter 的估计方差为_"，答案是。由 Lemma 40.1，（因为是的个数，最坏情况）。这意味着标准差与估计值同阶，误差很大。 - 原题问 "Morris Counter 可通过____提供 -factor 近似"，答案是 Median-of-means trick。Vanilla 版本方差太大，需要先用个副本取均值降低方差，再用组取中位数提升概率。注意顺序不能反（Tutorial 8 Problem 2）。

定理: median-of-means 版 Morris Counter 是随机一趟算法，对参数，输出满足：

空间复杂度：

分析思路: 取个 Morris Counter 的均值得到方差减小倍的估计，由 Chebyshev 得常数概率的估计。取组，对组均值取中位数，成功概率升至。

§6 Morris Counter 的 careful variant

算法

将乘以（而非）的概率为。输出。

Theorem 42: careful Morris Counter

定理: careful Morris Counter 的一趟算法，对参数，输出满足：

空间复杂度：

这是双对数于的空间——比 Theorem 41 更好，且是加法项（而非乘法项），不依赖。

参数设置: 取，由 Chebyshev 直接得到，不需要 median trick。详细推导见 Problem 5(d)。

§7 Distinct Elements 问题

问题: 估计流中 distinct elements 的数目，允许或常数倍近似。

§8 Tidemark（AMS）算法（Algorithm 17）

算法描述

选强 universal hash ，维护整数（初始）。处理每个：若，令。输出。

空间（存用，存用）。

算法分析

定义: ，即经过哈希后末尾至少个的 distinct elements 个数。

注意：。

期望: 由强 universal 保证均匀分布，。

方差: 由 pairwise independence（强 universal），（指示变量的方差期望）。

双侧分析:

上界（Markov 不等式）。
下界（Chebyshev）。

取：

结合中位数技巧：

Theorem 43: Tidemark 算法（median 版本）

定理: Tidemark（AMS）算法（加 median trick）是随机一趟算法，对参数，输出满足：

空间复杂度：

限制: 这只给出常数倍（）近似，不能任意精度。

Quiz 知识点：原题问 "Vanilla Tidemark（AMS）算法对 Distinct Elements 给出____近似"，答案是 constant-factor。Tidemark 通过 median trick 只能达到常数倍近似（如），而不是任意精度的。

Quiz 高频混淆点：原题问 "Tidemark 算法解决 MAJORITY 问题"（True/False），答案是 False。Tidemark 解决的是 Distinct Elements（估计），不是 MAJORITY 问题。这是完全不同的两个问题。

§9 BJKST 算法（Algorithm 18）

算法描述

参数，，。

选两个强 universal hash：（用于），（用于压缩元素标识）。

维护阈值和集合（存对）：

若，将加入；
当时，令，并删除中所有的对。

输出。

两个 hash 的分工: - ：用于"尾随零"过滤，保证近点碰撞，按进行层次筛选 - ：用于压缩元素索引，把压缩到，大幅节省存储每个元素所需的 bits

Theorem 44: BJKST 算法

定理: BJKST 算法（加 median trick）是随机一趟算法，对参数，输出满足：

空间复杂度：

这比 Tidemark 更好：近似精度可以任意小（可趋近）。

Quiz 知识点：原题问 "Vanilla BJKST 算法对 Distinct Elements 给出____近似，空间 "，答案是 -factor。BJKST 通过两层哈希（做 zeros 过滤，做压缩）将空间降至，同时提供任意精度的近似。这是 BJKST 相比 Tidemark 的核心优势。

与 Tidemark 的对比:

	Tidemark	BJKST
近似比	常数	任意
空间
精度	固定常数	可调

§10 核心记忆卡片

算法/定理	问题	误差/保证
Misra-Gries（Theorem 40）	Frequency estimation（频率估计）	，确定性
Morris Counter（Theorem 41）	Approximate counting（近似计数）	，概率
Careful Morris（Theorem 42）	Approximate counting	，概率
Tidemark/AMS（Theorem 43）	Distinct elements	常数倍近似
BJKST（Theorem 44）	Distinct elements	，概率
Bottom-（Problem 7）	Distinct elements	，概率

核心技巧汇总:

Median-of-means: 先取份均值降方差，再取份的中位数升概率。顺序不能反（Problem 2）。
两层哈希: 第一层做功能哈希（如 LSH 中的 locality-sensitive，或过滤）；第二层做压缩（如或普通 hash table），前者定性，后者省空间。
强 universal vs 真随机: 强 universal family 只需 bits 存储，且保证 pairwise independence，足以用 Chebyshev 分析；真随机需要 bits（Problem 3）。
的概率: （由均匀分布），这是 Tidemark 和 BJKST 的核心随机结构。
Morris Counter 的关键: 的期望递推，精确来自 Bernoulli 的期望恰好是 ——计数器在期望上是线性的。

Part 3: Week 8 Quiz 回顾

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

Question 1

[EN] The Misra-Gries algorithm allows us to solve the MAJORITY problem in one pass, using space .

[CN] Misra-Gries 算法可用单次遍历、空间解决 MAJORITY 问题。

选项	答案
No	✅
Yes	❌

知识点：MG 解决的是 Frequent Elements（Heavy Hitters），不是 MAJORITY。虽然可用 MG 配合第二趟验证来解决 MAJORITY，但单次遍历只能给出频率估计。

Question 2

[EN] In the standard streaming streaming setting, the input comes one element at a time, in _________ order.

[CN] 标准数据流设定中，输入元素以____顺序到达。

选项	答案
Uniformly random	❌
Arbitrary	✅
Sorted	❌
Best-case	❌

知识点：Streaming 算法不假设输入顺序，必须在任意顺序下都能正确工作。

Question 3

[EN] Most streaming problems can be solved exactly by a randomised algorithm using space .

[CN] 大多数数据流问题可用随机化算法以空间精确求解。

选项	答案
True	❌
False	✅

知识点：许多 streaming 问题需要空间才能精确求解。因此必须允许近似算法和概率保证。

Question 4

[EN] The Misra-Gries algorithm is ________.

[CN] Misra-Gries 算法是____的。

选项	答案
Randomised	❌
Deterministic	✅

知识点：MG 的计数器更新完全由输入决定，不依赖任何随机比特。这是 streaming 中罕见的确定性算法。

Question 5

[EN] The Morris Counter algorithm provides an approximate count of the number of non-zero elements in a stream of length using space:

[CN] Morris Counter 用____空间近似统计流中非零元素个数。

选项	答案
	❌
	✅
	❌
	❌

知识点：Vanilla Morris Counter 只存一个计数器，而 whp，所以只需 bits。对比直接存储需要 bits。

Question 6

[EN] The "vanilla" version of the Morris Counter gives an estimate of which has variance ____

[CN] "Vanilla" Morris Counter 给出的估计，方差为____。

选项	答案
	❌
	❌
	✅
	❌

知识点：由 Lemma 40.1，。最坏情况，方差为。标准差与估计值同阶，误差很大，需要 Median-of-means 改进。

Question 7

[EN] The "vanilla" Tidemark (AMS) algorithm gives a ____ approximation for the Distinct Elements problem using space . [Select the best that applies]

[CN] "Vanilla" Tidemark（AMS）算法对 Distinct Elements 给出____近似，空间。

选项	答案
additive	❌
constant-factor	✅
-factor	❌

知识点：Tidemark 通过 median trick 只能达到常数倍近似（如），不是任意精度的。达到需要 BJKST。

Question 8

[EN] The "vanilla" BJKST algorithm gives a ____ approximation for the Distinct Elements problem using space . [Select the best that applies]

[CN] "Vanilla" BJKST 算法对 Distinct Elements 给出____近似，空间。

选项	答案
additive	❌
-factor	✅
constant-factor	❌

知识点：BJKST 通过两层哈希（做 zeros 过滤，做压缩）将空间降至，同时提供任意精度的近似。这是 BJKST 相比 Tidemark 的核心优势。

Question 9

[EN] The Morris Counter can be made to provide an -factor approximation to the number of non-zero elements in a stream using the ____________.

[CN] Morris Counter 可通过____提供 -factor 近似。

选项	答案
Median trick	❌
Median-of-means trick	✅
Trick-or-treat strategy	❌
Mean trick	❌

知识点：Median-of-means = 先取份均值降方差，再取份的中位数升概率。顺序不能反（Tutorial 8 Problem 2）。

Question 10

[EN] The Tidemark algorithm solves the MAJORITY problem in two passes.

[CN] Tidemark 算法用两次遍历解决 MAJORITY 问题。

选项	答案
False	✅
True	❌

知识点：Tidemark 解决的是 Distinct Elements（估计），不是 MAJORITY。MAJORITY 是 Heavy Hitters 问题，应使用 Misra-Gries 或 CountMinSketch。

Week 8 Quiz 速查表

题号	核心概念	正确答案
1	MG 解决 MAJORITY	No
2	输入顺序	Arbitrary
3	精确求解可能性	False
4	MG 确定性	Deterministic
5	Morris Counter 空间
6	Morris Counter 方差
7	Tidemark 近似	constant-factor
8	BJKST 近似	-factor
9	Morris 改进方法	Median-of-means
10	Tidemark 解决 MAJORITY	False

高频混淆点： - MG 解决的是 Heavy Hitters 不是 MAJORITY（Q1, Q10） - Morris Counter 空间但方差 （Q5 vs Q6）——方差太大需要改进 - Tidemark 是 constant-factor，BJKST 是 -factor（Q7 vs Q8）——BJKST 更精确但空间更大

Part 1: Tutorial 8 详细题解

Tutorial 难度总览

Problem 1: Morris Counter 的 median-of-means 证明梳理

为什么直接用 Chebyshev 不够

第一步：均值法降方差（means）

第二步：中位数法升概率（medians）

组合：总空间

Problem 2: "mean-of-medians" 为什么不行

Problem 3: BJKST 中用真随机 hash 会怎样

Problem 4: BJKST 中为什么存 而不是

Problem 5: Morris Counter 的"careful variant"分析

(a) 计算期望

(b) 计算方差

(c) 带中位数技巧的参数设置

(d) 不用中位数技巧

(e) 如何实现增量步骤

Problem 6: -Heavy Hitters（频繁元素集合）

Problem 7: Bottom- 算法的 Distinct Elements 分析

(a) 正确性分析

(b) 空间复杂度

Part 2: 讲义知识点详解

§0 名词与符号速查

§1 流式算法的基本设定

§2 Majority 问题

§3 Misra-Gries 算法（Algorithm 15）

算法描述（用 "配对抵消" 直观理解）

Theorem 40: Misra-Gries 算法保证

Majority 问题的两趟解法（详细说明）

§4 近似计数问题（Approximate Counting）

§5 Morris Counter（Algorithm 16）

算法描述

Lemma 40.1: Morris Counter 的期望与方差

§6 Morris Counter 的 careful variant

算法

Theorem 42: careful Morris Counter

§7 Distinct Elements 问题

§8 Tidemark（AMS）算法（Algorithm 17）

算法描述

算法分析

Theorem 43: Tidemark 算法（median 版本）

§9 BJKST 算法（Algorithm 18）

算法描述

Theorem 44: BJKST 算法

§10 核心记忆卡片

Part 3: Week 8 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 8 Quiz 速查表

Problem 4: BJKST 中为什么存而不是