Randomized Algorithm¶

概率论¶

面试一个人后立即决定是否录用。

面试费用 $C_{i}$ ，雇佣费用 $C_{h}$ 。 $N$ 个人，雇佣 $M$ 个人。

每次如果当前面试的人比之前所有的人都好，则雇佣。

设 $X$ 为雇佣的人数， $X_{i}$ 为第 $i$ 个人是否被雇佣。

X_{i} = {\begin{cases} 1, & candidate is hired \\ 0, & candidate is not hired \end{cases}

每个人被雇佣独立，所以

E (X) = E (\sum_{i = 1}^{N} X_{i}) = \sum_{i = 1}^{N} E (X_{i}) = \sum_{i = 1}^{N} \Pr (X_{i} = 1) = \sum_{i = 1}^{N} \frac{1}{i} = \ln N + O (1)

面试的时候需要立即决定是否雇佣，且只能雇佣一次。

先面试 $K$ 个人，找到最好的，但是不进行雇佣。然后面试后面的人，如果比之前的人好，则雇佣，结束面试。

Decide $K$

$S_{i}$ 表示第 $i$ 个人是最好的。 $S_{i}$ 为真，如果事件 $A$ （第 $i$ 个人是最好的）发生，且事件 $B$ （第 $K + 1$ 到第 $i - 1$ 个人都不被雇佣）发生。

\Pr (S_{i}) = \Pr (A \cap B) = \Pr (A) \cdot \Pr (B) = \frac{1}{N} \cdot \frac{K}{i - 1} = \frac{K}{N (i - 1)}

得到雇佣到最好的人的概率为

\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}

令 $K = ⌈ N / e ⌉$ ， $\Pr (S) = 1 / e$ 。

如果随机选取的 pivot 导致一侧元素个数小于 $n / 4$ ，那么重新选取 pivot。选出合适 pivot 的期望次数是两次。

将子问题分为几类：

Type $j$ ：子问题 $S$ 满足 $N {(\frac{3}{4})}^{j + 1} \leq | S | < N {(\frac{3}{4})}^{j}$

最多有 ${(\frac{4}{3})}^{j + 1}$ 个 Type $j$ 的子问题。

时间开销 $E (T_{Type j}) = O (N \cdot {(\frac{4}{3})}^{j + 1}) \times {(\frac{3}{4})}^{j + 1} = O (N)$ 。

不同 type 个数 $\log_{4 / 3} N = O (\log N)$ 。

所以期望时间复杂度为 $O (N \log N)$ 。