05 概率问题和随机算法

#概率

1 背景

Pasted image 20241017204718.png

 HIRE-ASSISTANT(n)  
 best ← 0           候选人0是最不合格的虚拟候选人  
 for i ← 1 to n   
     interview candidate i  
     if candidate i is better than candidate best   
         best ← i  
         hire candidate i.
  • 这段伪代码的意思是遍历n个候选人，从里面找到最好的。如果下一个比上一个好，就 炒掉上一个，雇佣下一个。
  • 我们关心的不是面试时间，而是产生的费用。但总的来说，研究的还是程序的执行次数。
  1. ：面试费用
  2. ：雇佣费用
  3. ：总费用是已经雇佣的人数，且面试的费用永远是，我们只专注于分析，这个量在算法的每次执行过程中都会改变。
  4. 最坏情况：应试者以能力递增的次序面试，我们雇佣了次，总的雇佣费用是。
  5. 最好情况：第一个面试者就是能力最强者。

2 指示器随机变量

  1. 给定一个样本空间S和一个事件A，那么时间A对应的指示器随机变量I{A}定义为：

    如果发生如果不发生

  2. 以一个例子简要说明如何应用指示器随机变量，并引出一个定理

    1. 确定在抛一枚均匀硬币时正面朝上的次数，样本空间为S={H,T}
    2. H为正面朝上，T为反面朝上
    4. 定义指示器随机变量X_H ,这个变量计算抛硬币时正面朝上的次数，正面朝上值为1，否则为0
      如果发生如果发生
      则假设抛一枚硬币时，正面朝上的期望次数为

  3. 引理：给定一个样本空间S和S中的一个事件A，设，那么。

  4. 用指示器随机变量分析雇佣问题 Pasted image 20241017204733.png

  5. 引理：假设应聘者以随机次序出现，算法HIRE-ASSISTANT总的雇佣费用平均情形下为。

3 随机算法

 RANDOMIZED-HIRE-ASSISTANT(n)  
 randomly permute the list of candidates  
 best = 0  
 for i=1 to n  
     intervie candidate i  
     if candidate i is better than candidate best  
         best = i  
         hire candidate i
  1. 引理：过程RANDOMIZED-HIRE-ASSISTANT的雇佣费用期望是￥
  2. 随机排列数组
    1. 法1：维数组的每个元素A[i]赋一个随机的优先级P[i]，然后依据优先级对数组A中的元素进行排序 
       PERMUTE-BY-SORTING(A)  
 n = A.length  
 let P[1..n]be a new array  
 for i = 1 to n  
     p[i] = RANDOM(1, n^3)  
 sort A, using P as sort keys
      引理：假设所有优先级都不同，则过程PERMUTE-BY-SORTING产生输入的均匀随机排列
    2. 法2：原址排列给定数组。 
      RANDOMIZE-IN-PLACE(A)  
  n = A.length  
  for i = 1 to n  
      swap A[i] with A[RANDOM(i, n)]

        引理：过程RANDOMIZE-IN-PLACE可计算出一个均匀随机排列
Built with MDFriday ❤️