Step 3 03. 排列组合与概率

<!-- Title: 03. 排列组合与概率：从密码安全到垃圾邮件过滤 --> <!-- ID: 242 --> <!-- Series: 程序员的数学修养 (ID: 16) --> <!-- Author: 潘卫 --> # 排列组合与概率：从密码安全到垃圾邮件过滤 ## 1. 计数原理：复杂度的来源 计算机科学很大程度上是在处理“数量”的问题。 为什么暴力破解密码需要几百年？为什么某些算法会发生组合爆炸？ * **乘法原理（分步）**：密码有 6 位，每位有 10 种可能，总可能数是 $10 \times 10 \times ... = 10^6$。 * **加法原理（分类）**：选主食，米饭有 3 种，面条有 5 种，总共有 $3+5=8$ 种选法。 ## 2. 排列与组合：暴力枚举的边界 在算法题（如 LeetCode）中，我们经常遇到全排列、子集等问题。 * **排列 (Permutation)**: 讲究顺序。比如 `[1, 2]` 和 `[2, 1]` 是不同的。 * *公式*：$P(n, k) = \frac{n!}{(n-k)!}$ * **组合 (Combination)**: 不讲究顺序。比如选彩票号码，先选 5 后选 1 和先选 1 后选 5 是一样的。 * *公式*：$C(n, k) = \frac{n!}{k!(n-k)!}$ **应用：密码强度估算** * 纯数字 6 位密码：$10^6 = 100$ 万种。秒破。 * 数字+小写字母 8 位密码：$36^8 \approx 2.8$ 万亿种。 * 数字+大小写+符号 12 位密码：$95^{12} \approx 5.4 \times 10^{23}$ 种。宇宙毁灭也破不完。 这就是**熵 (Entropy)** 的概念，字符集越大、长度越长，系统的无序度（熵）越高，越安全。 ## 3. 概率论：不确定性的艺术 世界不是确定的，程序处理的数据往往充满噪声。 ### 独立事件与联合概率 假设硬盘损坏的概率是 $P(A) = 0.01$ (1%)。 如果你做了一个 RAID 1（双盘镜像备份），两块盘同时坏掉（数据丢失）的概率是多少？ $P(A \cap B) = P(A) \times P(B) = 0.01 \times 0.01 = 0.0001$ (万分之一)。 通过简单的冗余，可靠性提升了 100 倍。 ### 生日悖论 (Birthday Paradox) 与哈希碰撞 **问题**：一个房间里至少有多少人，才能有 50% 的概率出现两个人生日相同？ 直觉可能告诉你需要 183 人（365的一半），或者更多。 **答案**：只需要 **23** 人。 **原理**： 我们要计算的是“所有人生日都不同”的概率 $P(\bar{A})$，然后用 1 减去它。 第 1 个人随便； 第 2 个人不能和第 1 个相同：$364/365$； 第 3 个人不能和前 2 个相同：$363/365$； ... 当人数达到 23 时，这个连乘积会降到 0.5 以下。 **对程序员的启示**： **哈希碰撞 (Hash Collision)** 比你想象的更容易发生！ 如果你的 Hash ID 只有 16 位，不要心存侥幸，一定要处理碰撞冲突，或者使用更长的 Hash（如 UUID, SHA-256）。 ## 4. 贝叶斯定理 (Bayes' Theorem)：机器学习的基石 $$P(A|B) = \frac{P(B|A) \cdot P(A)}{P(B)}$$ 这个公式看起来很枯燥，但它是**朴素贝叶斯分类器**（最早的垃圾邮件过滤器）的核心。 **场景：判断一封邮件是否为垃圾邮件 (Spam)** * $A$：邮件是垃圾邮件。 * $B$：邮件中包含单词 "发票"。 我们需要求 $P(A|B)$：当邮件包含“发票”时，它是垃圾邮件的概率。 1. $P(A)$：先验概率。根据历史数据，所有邮件中 20% 是垃圾邮件。 2. $P(B|A)$：垃圾邮件里包含“发票”的概率（比如 50%）。 3. $P(B)$：所有邮件里包含“发票”的概率（比如 15%）。 算出结果后，如果概率超过阈值（如 0.9），就将其扔进垃圾箱。 这是大数据智能决策的起点：**利用已知的先验知识，结合新的证据，动态更新对事实的判断。** ## 结语 概率论告诉程序员：**不要追求绝对的确定性，要学会管理风险和不确定性。** 从 RAID 备份到分布式系统的 CAP 定理，从哈希算法到 AI 模型，概率思维贯穿始终。