COMP4270 口诀速记

0. 复杂度速记

• 增长阶序： \[ O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!)<O(n^n) \]
• O(g(n))：最多这么快（上界）。
• \Omega(g(n))：至少这么快（下界）。
• \Theta(g(n))：上下都卡住（同阶）。

1. 指示变量（计数题万能）

• 数“发生了多少次”时，先写：\(X=\sum I_i\)，其中 \(I_i\in\{0,1\}\)。
• 期望直接拆：\(\mathbb E[X]=\sum \mathbb E[I_i]=\sum \Pr(I_i=1)\)。
• 不需要独立性：线性性永远成立。
• 记忆句：先定位置/窗口，再算单项概率，再乘项数。

2. and 概率怎么写

• \(\Pr(A\cap B)=\Pr(A)\Pr(B\mid A)\)。
• 只有独立时才可写 \(\Pr(A\cap B)=\Pr(A)\Pr(B)\)。
• 固定点题常用：\(\Pr(\pi(i)=i,\pi(j)=j)=\frac1n\cdot\frac1{n-1}\)（\(i\neq j\)）。

3. 平方展开防错

• \((\sum_i X_i)^2=\sum_i X_i^2+\sum_{i\ne j}X_iX_j\)。
• 等价写法：\((\sum_i X_i)^2=\sum_i X_i^2+2\sum_{i<j}X_iX_j\)。
• 记忆句：系数 2 在交叉项，不在平方项。

4. 收敛发散秒判

• 看极限是否有限（部分和或截断积分）。
• 口诀： \[ \sum \frac1{n^p},\ \int_1^\infty \frac1{x^p}\,dx \] 都是 \(p>1\) 收敛，\(p\le1\) 发散。
• 典型：\(\sum 1/n\) 发散，\(\int_1^\infty 1/x\,dx\) 发散。
• 通式（\(p>1\)）： \[ \int_1^\infty x^{-p}\,dx=\frac1{p-1}. \]

5. 离散型 vs 连续型

• 离散型：用 pmf \(\Pr(X=k)\)，期望 \(\mathbb E[X]=\sum_k k\Pr(X=k)\)。
• 连续型：用 pdf \(f(x)\)，\(\int f(x)dx=1\)，期望 \(\mathbb E[X]=\int x f(x)dx\)。
• 单点概率：连续型 \(\Pr(X=a)=0\)。
• 一句话：离散用“求和”，连续用“积分”。

6. 构造 \(\mathbb E[X]=\infty\) 三步模板

1. 选慢衰减尾巴（连续常用 \(\sim1/x^2\)，离散常用 \(\sim1/n^2\)）。
2. 调成合法分布（总概率为 1）。
3. 乘上 \(x\) 或 \(n\) 后若变成 \(1/x\) 或 \(1/n\)，均值通常发散。

标准例子： - 连续：\(f(x)=1/(1+x)^2,\ x\ge0\)，则 \(\mathbb E[X]=\infty\)。 - 离散：\(\Pr(X=n)=1/[n(n+1)]\)，则 \(\mathbb E[X]=\infty\)。

7. 常见结论一行记

• 随机排列不动点数 \(X\)：\(\mathbb E[X]=1,\ \mathrm{Var}(X)=1\)。
• 4 花色各 \(n\) 张、共 \(4n\) 张：相邻同花色对期望 \(n-1\)。
• \(n\) 人从 \(m\) 道菜独立等概率点菜：没被点到菜数期望 \[ m\left(1-\frac1m\right)^n. \]
• 长度 \(L\) 公平比特串中 111 出现次数（可重叠）期望：\((L-2)/8\)。

8. 微积分符号快查

• \([F(x)]_a^b=F(b)-F(a)\)。
• \(\ln\) 是自然对数（底 \(e\)）。
• \(\int \frac1{1+x}dx=\ln(1+x)+C\)。
• \(\int \frac1{(1+x)^2}dx=-\frac1{1+x}+C\)。