跳转至

13 Randomized Algorithms

文本统计：约 1249 个字 • 37 行代码

随机的概念：随机在算法一般有两种含义，一种是指输入在指定的集合内是随机生成的，另一种是指算法的行为具有随机性（相同输入，相同步骤时，下一步操作可能不同）。随机算法一般指的是第二种。

总是得出正确答案的高效确定性算法是以下算法的特殊情况——

  • 用非常高的概率（不一定必须）来给出正确的答案的高效随机算法；
  • 总是正确的，并且在期望中运行高效的随机算法；

13.1 The Hiring Problem

我们要找到一个人招聘，我们依次面试 \(N\) 个人，每个人面试完必须马上告知是否录用，如果录用，那么需要代价 \(C_h\)，每次面试的代价是 \(C_i\)，但是 \(C_i\) 远小于 \(C_h\)。要制定策略，代价比较小并且找到最好的那个人的概率最大。

int Hiring ( EventType C[ ], int N )
{   /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;
    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }
    return Best;
}

这种算法遇到的最差情况是面试者按照质量从低到高依次面试，这样每个人都要付签字费，开销为 \(O(NC_h)\)

于是我们稍微改变一下顺序，我们让来的人的顺序是随机的，那么我们录用的人数 \(X\) 的期望是多少呢？

我们将随机变量 \(X\) 分为 \(N\) 个随机变量 \(X_i\)，定义为

\[ X_i=\left\{ \begin{aligned} 1,\quad& 第i个面试者被录用\\ 0,\quad& 第i个面试者未被录用 \end{aligned} \right. \]

那么

\[ E[X]=E[\sum_{i=1}^NX_i]=\sum_{i=1}^NE[X_i]=\sum_{i=1}^N1/i=lnN+O(1) \]

那么期望的开销为 \(O(C_hlnN+NC_i)\)

On-line Hiring Algorithm

当我们只能录用一次。

我们的算法是先面试前k个都不录取，在后面的N-K个人中选出第一个比前K个最高分要高的，如果没有，那么只能选择最后一个人。

int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = - infty ;
    for ( i=1; i<=k; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ )   BestQ = Qi;
    }
    for ( i=k+1; i<=N; i++ ) {
        Qi = interview( i );
        if ( Qi > BestQ ) {
            Best = i;
            break;
        }
    }
    return Best;
}

What is the probability we hire the best qualified candidate for a given k?

What is the best value of k to maximize above probability?

事件 \(S\) ：雇佣的那个人是最好的，那么 \(P(S)=?\)

我们定义随机变量 \(S_i\)

\[ S_i=\left\{ \begin{aligned} 1,\quad& 在第 i 个位置雇佣的人是最好的\\ 0,\quad& 其他 \end{aligned} \right. \]

那么要使事件 \(S_i\) 发生，需要满足最大的值在第 \(i\) 个位置，同时对于前 \(i-1\) 个值中的最大值在前 \(k\) 个 （否则会在第 \(i\) 个面试者来之前就已经录用了一个人），从而

\[ P(S_i)=\frac1N\times\frac{k}{i-1}=\frac{k}{N(i-1)} \]
\[ P(S)=\sum_{i=k+1}^NP(S_i)=\sum_{i=k+1}^N\frac{k}{N(i-1)}=\frac{k}{N}\sum_{i=k}^{N-1}\frac1i \]

根据积分的定义，我们很容易得到下列不等式

\[ \int_k^N\frac1xdx\le\sum_{i=k}^{N-1}\frac1i\le\int_{k-1}^{N-1}\frac1xdx \]

从而得到

\[ \frac kN\ln(\frac Nk)\le P(S)\le\frac kN\ln(\frac{N-1}{k-1}) \]

对下界求导得到 \(k\) 取 \(N/e\) 时，下界最大，使得 \(P(S)\) 最大

13.2 Quick-sort

RandQuicksort(A, p, r)
IF p<r THEN
    q=RandPartition(A, p, r)
    RandQuicksort(A, p, q − 1)
    RandQuicksort(A, q + 1, r)
FI

首先，我们知道Partition函数被调用了\(n\)次，并且该函数用于将数组\(A\)中的每个元素与枢轴进行比较。因此，时间成本主要取决于比较的次数。

然后，回到两个数 \(Z_i\) 和 \(Z_j\) 的情况，我们需要了解它们被比较的可能性（假设每对比较都是独立的)。我们设定序列\(Z\)是升序排列的，并且知道\(Z_i\)和\(Z_j\)只有在其中一个作为枢轴时才会被比较；如果存在一个位于\(Z_i\)和\(Z_j\)之间的枢轴，那么\(Z_i\)和\(Z_j\)将会分开。

因此，它们被比较的概率为：\(P = \frac{2}{j-i+1}\)

期望值 \(E(X)\)可以表示为：\(E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^n \frac{2}{j-i+1}\)

考虑到 \(\sum_{j=i+1}^n \frac{2}{j-i+1}\) 近似于 \(\log n\)，而 \(\sum_{i=1}^{n-1} = n\)，所以总的时间复杂度大约为 \(n\log n\)。

这样我们就得到了快速排序算法中比较操作的平均时间复杂度估计。

我们对上述算法稍微做一些改进，希望这个 pivot 更靠中间一点

Central splitter: the pivot that divides the set so that each side contains at least \(n/4\)

我们随机选取pivot，然后验证这个是不是central splitter，失败就再选一个，期望的查找次数为2

\[ E(\# \text{find})=\sum_{i=1}^{+\infty}\frac{i}{2^i}=2 \]

算法时间复杂度分析：

法一：我们定义 Type j 为规模在 \(N(\frac34)^{j+1}\) 到 \(N(\frac34)^j\) 之间的子问题。

那么 Type j 的子问题个数最多有 \((\frac43)^{j+1}\) 个，因为总共的规模为 \(N\)，而处理每个子问题，我们需要做的是将这个与另一部分合并，以及寻找下一个pivot的工作（期望是2轮）这两个都是线性时间的

\[ E[T_{type~j}]=O(N(\frac34)^j)\times (\frac43)^j=O(N) \]

一共有 \(\log_{\frac43}N=O(\log N)\) 类，所以整个算法的时间复杂度是 \(O(N\log N)\)

法二：利用递推公式

\[ f(N)=f(N/4)+f(3N/4)+O(N) \]

评论区

对你有帮助的话请给我个赞和 star => GitHub stars
欢迎跟我探讨！！！