[算法导论][5][概率分析和随机算法]

1. 5.1 雇用问题
   1. 5.1.1 问题描述
   2. 5.1.2 最坏情形分析
   3. 5.1.3 概率分析
   4. 5.1.4 随机算法
2. 5.2 指示器随机变量

5.1 雇用问题

5.1.1 问题描述

• 问题

  • 假如你要找一个雇佣代理，帮你雇佣一个办公助理
  • 雇佣代理每天给你推荐一个应聘者。你面试这个人，然后决定是否雇佣他。
  • 你必须付给雇佣代理一小笔费用，以便面试应聘者。然而要真的雇佣一个应聘者需要花更多的钱，因为你必须辞掉目前的办公助理，还要付一大笔中介费给雇佣代理
  • 你承诺任何时候都要找最适合的人来担任这项职务，因此，你决定在面试完每个应聘者后，如果该应聘者比当前的办公助理更合适，就会辞掉当前的办公助理，然后聘用新的

• 伪代码

  HIRE-ASSISTANT(n)
  best = 0
  for i = 1 to n
      interview candidate i
      if candidate i is better than candidate best
          best = i
          hire condidate i

• 每次雇佣员工都会产生一笔费用，我们的任务是估算该费用会是多少

5.1.2 最坏情形分析

• 在最坏的情况下，我们实际上雇佣了每个面试的应聘者，总的费用是O(c_hn)

5.1.3 概率分析

• 大多数情况下我们采用概率分析来分析一个算法的平均运行时间

• 为了进行概率分析，我们必须使用或者假设关于输入的分布。分析该算法，计算出一个平均情形下的运行时间，其中我们对所有可能的输入分布取平均值

5.1.4 随机算法

• 当一个算法的行为不仅由输入决定，而且也由随机数生成器产生的数值决定，则称这个算法是随机的

• 当分析一个随机算法的运行时间时，我们以运行时间的期望值衡量，我们将一个随机算法的运行时间称为期望运行时间

• 一般而言，当概率分布是在算法的输入上时，我们讨论的是平均运行时间；当算法本身做出随机选择时，我们讨论其期望运行时间

---

5.2 指示器随机变量

• 指示器随机变量

  • 它为概率与期望之间的转换提供了一个便利的方法
  • 定义
    • 给定一个样本空间S和一个事件A，那么事件A对应的指示器随机变量I{A}定义为

      I(A) = 1 如果A发生
      I(A) = 0 如果A不发生

• 定理

  • E[IA] = P(A)