13:Randomized Algorithms

随机化算法(Randomized Algorithms)在实际场景中应用广泛，这一讲将用两个例子来详细解析随机化算法。

事实上，在此之前我们已经了解了很多确定性的算法，该确定性体现在两个方面。其一，对于同样的数据规模，算法的时间复杂度是确定的；其二，对于同样的输入，算法的输出是确定的。据此，我们会把随机化算法分成如下两类：

在较高概率下得到正确解的高效算法（时间确定，但是解不确定）
在期望时间内得到正确解的算法（时间不确定，但是解确定正确）

接下来我们通过两个问题来介绍随机化算法。

Samples¶

Hire Assistant¶

问题描述

你需要招聘员工，在 \(n\) 天内每天面试一个员工（有个人素质 \(q_i\)），并且可以选择是否雇佣。面试的花销是 \(c_i\)，雇佣的花销是 \(c\)，有 \(c>>c_i\)。如何在尽可能降低成本的情况下雇佣到尽可能好的员工。

在考虑这个问题的时候需要时刻注意我们是无法预知员工的素质高低的，一旦错过了就无法重来了。换言之，我们假定此处我们起始的时候对员工素质未知，并且我们对每个员工至多访问一次。

Naive Solution¶

一个非常简单的做法就是一旦遇到一个员工比此前所有的都优秀，就录取。但是这个做法存在非常差的反例，如果所有员工素质递增，则会录取所有员工，使得开销大大增加。

Randomized Algorithm¶

接下来我们假定我们只是能知道这 \(n\) 个人，但是并不知道它们的到达顺序，或者说，我们可以主动去决定它们的到达顺序。据此，我们可以对读入进行一次随机化排列(random shuffle)，这样大大降低了前文所述的高开销的情况的概率。这里的问题变成了，如何高效地进行随机化排列。cy 的课件中给出一种很奇怪的做法。它随机地为每个数产生了一个不超过 \(n^3\) 的键值，然后按该键值排序整个序列。整个过程达到了 \(O(n\log n)\)，因为我们需要排序。

void PermuteBySorting(ElemType A[],int N)
{
    for (i=1;i<=N;i++)
        A[i].P=1+rand()%(N*N*N);
    Sort A, using P as the sort keys;
}

但是我们事实上知道一种更高效的，并且也能等概率地产生所有随机序列的方法。参考插入排序，我们对于一个 \(i\)，随机地选择下标为 \([1,i]\) 内的数与之交换。

void random_shuffle(ElemType A[],int N)
{
    for(i=N;i>=1;i--)
    {
        j=random(1,i);
        swap(a[i],a[j]);
    }
}

据此，我们可以计算这种随机的情况下，最终的期望开销是多少。

期望开销

我们定义 \(X_i\) 表示第 \(i\) 个人是否被雇佣，若是则为 \(1\)。那么在随机分布的情况下，第 \(i\) 个人是前 \(i\) 个中最大的概率为 \(Pr[X_i]=E[X_i]=\dfrac{1}{i}\)。

那么期望的开销就是：

\[ n\times c_i+\sum_{i=1}^nE[X_i]\times c \]

在 \(n\) 较大时可以通过级数来逼近到 \(O(nc_i+c\ln n)\)。

Online Hiring Algorithm¶

在前面的算法中，我们允许招聘多名员工，最后再这些员工中选择最好的。但是实际上我们没法读取所有的员工素质，所以我们提出在线(Online)的做法，在整个过程中我们只能招聘一个员工，并且在招聘之后就不再继续面试。（注意，这里的在线与我们平常所说的在线概念有所不同）

那么我们应该采取怎样的策略来招聘尽可能好的员工呢？这个问题在毕导的视频中有详细的解答。此处我们简略给出思路。

简要说明

在我们的随机算法中，我们先面试前 \(k\) 个人，并取其中最大的，在后 \(n-k\) 个人中遇到第一个比这个最大值要大的就选取。那么如何决定 \(k\)？

我们令 \(S_i\) 表示第 \(i\) 个人是最好的，并且被选中，那么它的条件是 \(i\) 是最好的，并且在 \(k+1\) 到 \(i-1\) 之间没有人比前 \(k\) 人大。换言之，\(Pr[S_i]=\dfrac{1}{n}\times \dfrac{i-1}{k}\)。我们将所有的 \(S_i\) 概率相加后，不难得到：

\[ Pr[S]=\dfrac{k}{n}\sum_{i=k+1}^n\dfrac{1}{i} \]

该值下界可以用 \(\dfrac{k}{n}\ln\dfrac{n}{k}\) 来确定（上界形式差不多，不影响后面的求最值），通过求导不难发现我们取 \(k=\dfrac{N}{e}\) 可以得到最大的招聘到最好员工的概率。

Quicksort¶

回想一下在 fds 中学习的快速排序，我们每次选取一个 pivot 然后将所有数按值分治。当时我们说若输入数据随机，那么我们能够保证快排的平均复杂度是 \(O(n\log n)\) 的。但是如果输入数据并不是均匀随机的排列，而是针对我们选取 pivot 的策略而刻意给出的最差数据呢？我们仍然可以通过随机化的方式来达到期望 \(O(n\log n)\)。

首先我们介绍几个定义：

definitions

Central splitter: 我们说一个 pivot 的选取是中心分割，当且仅当分割后两边的大小都至少为 \(\dfrac{n}{4}\)。
Type j: 我们说一个问题 \(S\) 是 Type j 的，当且仅当它的问题规模满足 \(n(\dfrac{3}{4})^{j+1}\leq |S|\leq n(\dfrac{3}{4})^{j+1}\)

据此，我们如果希望在选取 pivot 的时候随机选取，那么显然，当我们选取两次的时候，它选中 Central splitter 的期望为 1。而在这种情况下，分割出来的两个子问题都会是 Type j 问题。对于同一个 \(j\)，Type j 问题的个数至多为 \((\dfrac{4}{3})^{j+1}\) 个，每个问题至多可能需要 \(O(n(\dfrac{3}{4})^{j+1})\) 的时间处理，所以对于 Type j，处理所有问题的时间为 \(O(n)\)。\(j\) 可能的取值不多，最多是 \(O(\log n)\) 的。因此总的复杂度为 \(O(n\log n)\)。