5.附录：概率论在计算机中的运用-灵析社区

5.1算法分析

算法的概率分析

算法分析中常见的方法有概率分析、摊销分析、竞争分析等等。

其中概率分析主要是用概率手段对算法进行平均情况分析。

如果是确定性算法，只需要考虑所有输入分布即可，而如果是随机算法，处理考虑输入分布以外，算法的随机步骤也需要考虑。

下面以一个例子来看一下概率分析的过程。

问题: 梦幻情人的代价

我去婚介所寻求对象，婚介所一次性给我 n 个人的资料，那么我需要一种算法从中选出最好的人。

每个人的资料只能访问一次，但是访问顺序可以自己定，初始顺序就是婚介所给我这 n 个人时排列好的顺序。

确定性算法: 见好就变

这里我直接给出一种算法: 见好就变算法，具体如下

用一个变量 best 记录当前的最佳对象。依次枚举 n 位候选人，每枚举一位需要支付介绍费用 C_i ，如果当前枚举到的候选人 i 比当前最佳对象 best 优秀，那么就把 i 作为当前最佳对象，首先要支付 c_s分手费，然后支付介绍成功费 C_i，并且要支付与新最佳对象的相处费 C_d。

问，这个见好就变的恋爱算法需要支付多大成本。

分析

step1: 伪代码和各行成本

首先我们将算法写成伪代码，并在每一行后面标注该行对应的成本

best = 0
for i = 1..n do                                 // 介绍费 Cj
    if 候选人 i 比当前最佳对象 best 优秀 then   // 分手费 Cs
        best = i                                // 介绍成功费 Cj
        约会新最佳对象 i                        // 相处费 Cd

step2: 最好与最坏情况

首先通过伪代码和每一行的成本，我们可以直接写出大 O 分析结果 O(nCi+mCd+mCj+(m−1)Cs)

为了方便，记 C=Cd+Cj+Cs于是问题变为了分析 mC。其中 m 是 if 判定成功的次数。

最坏情况是 m = n，也就是严格按照从坏到好的顺序介绍，此时结果为 O(nCi+nC)，由生活经验，C>>C_i，结果可以写为 O(nC)

最好情况是 m = 1，也就是一上来就介绍了最好的，后面的顺序不重要。此时结果为 (O(nCi+1C) 这里能否写为 O(nCi)就要看 C>>nC_i是否满足了。

step3: 输入分布随机时的平均情况

平均情况是需要用到概率分析的地方。想当然的认为结果是 O(nCi+2nC)是错的。

下面进行概率分析。

记 rank(1) 是第一个候选人的排名，取值 1 ~ n。

<rank(1), rank(2), ..., rank(n)> 是数列 <1, 2, ..., n> 的一个排列。

现在有一个针对算法输入的重要假设: 候选人出现的顺序随机。

记随机变量 X_i表示第 i 个人是否被我看中，若看中则为 1 否则为 0。

于是我的总恋爱次数为随机变量和X=X1+X2+...+Xn。

我们概率分析的目标是求 E[X]

由于候选人出现顺序随机，因此 i 被我看中（也就是 i 比前面的 i - 1 个人都强）的概率是 1/i，，于是 E[X_i]= 1/i

所以

因此平均情况的结果为O(Cln(n))

step4: 对输入分布的先验知识

注意前面针对输入的假设不一定成立，也就是候选人出现的顺序不一定随机，例如婚介所就是从坏到好给我介绍。那么平均情况的结果不会是前面推导的 O(Cln(n))，而是最坏情况的结果。这也是前面为什么说概率分析需要考虑输入分布的原因。

而婚介所因为要多挣钱，所以它基本上会按照最坏情况的顺序该我，这就是我们对输入分布的先验知识。

那么对于这种情况，我们该怎么办呢，大致有以下三种方案。

搞情况候选人介绍顺序到底是什么分布，但这基本不现实，因为对方一般不会提前告知数据分布。
承认婚介所会按从坏到好的顺序介绍，我就做最坏打算，但这也不现实，因为我不接受。
既然对方给我的顺序是按最坏情况来的（先验知识），那我自己做随机化好了。

也就是在执行见好就变算法前，我自己把 n 个候选人的顺序随机排列一下，然后再依次访问各个候选人资料。

其中随机排列算法如下：

for i = 1..n do
    swap A[i] A[Random(i, n)]  // 成本 O(1)

按以上算法，随机排列的成本为 O(n)，总成本就变为 O(n+Cln(n))，这比最坏情况的 O(nC) 要好。

5.2概率数据结构

如果大家刷过一些面经的话，会发现经常见到一些大数据算法的问题，比如上来给你 400 亿个数/字符串，然后完成某种需求。

大数据算法涵盖的面比较广，随机算法，近似算法，外存算法，并行算法，分布式算法等都可以算是大数据算法。

其中随机算法是很重要的一种算法，而随机算法的实现需要用到一些概率数据结构，也就是应用了概率知识的数据结构。

这种概率数据结构有一些经典场景，比如哈希、相似性、排名、频率、成员关系、元素种类数等等。每个场景下有几个经典数据结构，具体可以看下图，其中有红旗标志的是 Redis 里有的，可以参考一下。

5.3随机算法

随机算法就是在算法中引入随机因素，即通过随机数选择算法的下一步操作。

随机算法是一种算法，它采用了一定程度的随机性作为其逻辑的一部分。

该算法通常使用均匀随机数作为辅助输入来指导自己的行为，在力扣上有 10 道与随机算法相关的题目，主要涉及下面这些知识点，这里把知识点与题目列出来了，感兴趣的同学可以研究一下。

洗牌

384. 打乱数组

拒绝采样

478. 在圆内随机生成点

470. 用 Rand7() 实现 Rand10()

蓄水池抽样

398. 随机数索引

382. 链表随机节点

加权蓄水池抽样

528. 按权重随机选择

黑名单映射

710. 黑名单中的随机数

519. 随机翻转矩阵

加权随机事件二分

528. 按权重随机选择

497. 非重叠矩形中的随机点