Skip to content

约 389 个字 47 行代码 5 张图片 预计阅读时间 3 分钟

Chap 13 | “Randomized Algorithms”

章节启示录

摆烂了。……

1.概述

2.[Example] The Hiring Problem

  1. 从猎头公司聘请办公室助理
  2. 每天面试不同的申请人，持续 N 天
  3. 面试成本 = CiC_i << 招聘成本 = ChC_h
  4. 分析面试和招聘成本，而不是运行时间

假设雇用了 MM 人。 总成本：O(NCi+MCh)O(NC_i+MC_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;
}
Worst case:候选人的质量越来越高

  • 假设候选人以随机顺序到达

    随机性假设：到目前为止，前 ii 名候选人中的任何一个都同样可能最有资格

int RandomizedHiring ( EventType C[ ], int N )
{   /* candidate 0 is a least-qualified dummy candidate */
    int Best = 0;
    int BestQ = the quality of candidate 0;

    randomly permute the list of candidates;

    for ( i=1; i<=N; i++ ) {
        Qi = interview( i ); /* Ci */
        if ( Qi > BestQ ) {
            BestQ = Qi;
            Best = i;
            hire( i );  /* Ch */
        }
    }
}

Online Hiring Algorithm – hire only once

int OnlineHiring ( EventType C[ ], int N, int k )
{
    int Best = N;
    int BestQ = -  ;
    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;
}
Si:=S_i:= 第 ii 个申请人是最好的
当且仅当：{ A:= the best one is at position i } ∩\cap { B:= no one at positions k+1 ~ i–1 are hired }

Pr[Si]=Pr[A∩B]=Pr[A]∗Pr[B]=(1/N)∗(k/(i−1))=kN(i−1) Pr[S_i]=Pr[A\cap B] = Pr[A]*Pr[B]=(1/N)*(k/(i-1))=\frac{k}{N(i-1)}

其中，

Pr[B]=1−Pr[B‾]=1−((i−1)−(k+1)+1i−1)=ki−1 Pr[B] = 1-Pr[\overline{B}]=1-(\frac{(i-1)-(k+1)+1}{i-1})=\frac{k}{i-1}
Pr[S]=∑i=k+1NPr[Si]=∑i=k+1NkN(i−1)=kN∑i=kN−11i Pr[S] = \sum_{i=k+1}^{N}Pr[S_i]=\sum_{i=k+1}^{N}\frac{k}{N(i-1)}=\frac{k}{N}\sum_{i=k}^{N-1}\frac{1}{i}

3.[Example] Quicksort

  • Central splitter := the pivot that divides the set so that each side contains at least n/4
    小的部分要超过四分之一（大的部分不超过四分之三）

  • Modified Quicksort := always select a central splitter before recursions
    每次需要先找到Central splitter再继续，若找的不是Central splitter，则需重新寻找。

  • 结论1：在我们找到Central splitter之前，所需的预期迭代次数最多为 2 次。

证明

其实用抽屉原理就可以证明。最坏情况时，选的不满足Central splitter的数量最多是 n/2 个。

  • Type j : the subproblem S is of type j if N(34)j+1≤∣S∣≤N(34)jN(\frac{3}{4})^{j+1}≤|S|≤N(\frac{3}{4})^{j}

  • 结论2：声明：最多存在 (43)j+1(\frac{4}{3})^{j+1} 个 jj 类型的子问题。

E[Ttypej]=O(N(34)j)×(43)j+1=O(N) E[T_{type_j}]=O(N(\frac{3}{4})^j)×(\frac{4}{3})^{j+1}=O(N)

4.附录[Skip List]

跳表的相关定义与实现

Comments