量化机会与随机性

在进入本节之前，我想提醒读者：本节以及下一节的内容极不可能出现在你的编程面试中。这些内容面向对理论感兴趣或希望进一步了解复杂性理论的爱好者。如果你的主要目标是面试准备，那么前面的章节会更有帮助。当然，欢迎你继续阅读，毕竟掌握更多知识总没有坏处 :)

概率

本节是对概率的简要介绍，旨在让读者快速掌握理解随机算法和概率分析所必需的基础知识。概率的定义是某件事发生的可能性。概率的数学研究描述了如何量化一个事件发生的可能性。

我们从教科书中的经典例子——抛硬币开始。当我们抛一枚硬币时，它可能正面朝上，也可能反面朝上。假设这枚硬币是公平的，正反面朝上的可能性相等。如果我们想知道硬币正面朝上的概率，只需统计导致正面朝上的结果数量，并将其除以所有可能结果的总数。在这个场景中，只可能存在两种结果：一次抛掷要么是正面，要么是反面。所有可能结果的集合称为样本空间，记作 S。

$S = { H, T }$

样本空间S包含了我们所关注实验的所有可能结果。注意，样本空间中的事件是互斥的，也就是说，如果抛掷结果是正面，就不可能同时是反面；如果今天是星期五，就不可能同时是星期日。一周中的每一天就是互斥的。

另外需要注意的是，样本空间中至少有一个事件必然会发生，即其总概率为：

$P(S) = 1$

例如，当你抛一枚硬币时，结果必然是正面或反面之一。