概率分析和随机算法

目录

雇佣问题

概率分析

随机算法 

生日悖论

随机算法

 概率分析

球与箱子

总结

---

雇佣问题

有n个候选人面试，如果面试者比目前雇佣者的分数高，评价更好，那么就辞掉当前雇佣者，而去聘用面试者，否则继续面试新的候选人。面试完n个人结束。

  best为到i个候选人中最佳面试者， a数组时候选人名单。

起始条件：best= a[0]; 聘用第一个面试者。

保持：if(best < a[i]) best = a[i]; 聘用面试者。

终止条件：当i == n 时，迭代终止。

代码：

#include "stdio.h"void main() {int best = 0;int n = 10;int a[10] = {0};for (size_t i = 0; i < n; i++){scanf("%d", &a[i]);if(best < a[i]) {best = a[i];}}}

 算法分析：

	代码	代价
面试	scanf("%d", &a[i]);	C1
雇佣	best = a[i];	C2

假如面试过程中有m个人被雇佣，则总的代价=O(c1*n + c2*m).(0<m<=n)

最坏情况分析：

m=n时，总的代价最大，此时为O(c1*n + c2*n). 由于c1远小于c2,因此总代价为O(c2*n).

平均情况分析：

求平均情况就是求m=1~n的所有可能的均值。在数学中求平均值可以转化为求一个参量的期望。那如何求这个期望值呢？

概率分析

一个面试者是否面试通过服从二项分布。

m个雇佣者的被雇佣的概率

Xi	0	第1个	第2个	第n个
P	0	1	1/2	1/n

E[X] = E[X1] + E[X2] + … +E[Xn] = 1+1/2+…+1/n = lnx + O(1).

随机算法 

代码：

#include "stdio.h"
#include "math.h"
#include <time.h>void permute_by_sorting(int p[10], int a[10]);
void swap(int *a, int *b);
void main() {int best = 0;int rank = 0;int n = 10;int a[10] = {5,2,3,1,4,9,8,10,7,6};int p[10] = {0};permute_by_sorting(p, a);for (size_t i = 0; i < n; i++){if(best < a[i]) {best = a[i];rank = i;}}printf("\nThe best hired man is %dth %d", rank, best);}void permute_by_sorting(int p[10], int a[10]) {int count = 10;srand(time(0));for (size_t i = 0; i < count; i++){p[i] = rand()%1000;printf("%d, ", p[i]);}printf("\n");for (size_t i = 0; i < count; i++){for (size_t j = i; j < count; j++){if(p[i] > p[j]) {swap(&p[i], &p[j]);swap(&a[i], &a[j]);}}printf("%d ", a[i]);}}void swap(int *a, int *b) {int temp;temp = *a;*a = *b;*b = temp;
}

输出结果：

随机排列数列：

可以从输出结果看出，每次出现的优先级的数列不一样，是随机的。样本空间为n!种排列方式，也就是全排列方式，这样就形成了随机算法了，可以使用概率分析算法的性能，每次出现的排列的概率都是1/n!。

以下两行代码能够执行到的次数m的期望E(X)= O(lnx).

            best = a[i];rank = i;

生日悖论

问题描述：一个屋子里，必须要有多少人以上，才可以至少有生日相同的两个人？

随机算法

代码

#include "stdio.h"
#include "math.h"
#include <time.h>#define PERSON_NUM 40
void permute_by_sorting(int p[10]);void main() {int same_birthday_p1 = -1;int same_birthday_p2 = -1;int n = PERSON_NUM;int p[PERSON_NUM] = {0};permute_by_sorting(p);for (size_t i = 0; i < n; i++){for (size_t j = i+1; j < n; j++){if(p[j] == p[i]) {same_birthday_p1 = i;same_birthday_p2 = j;break;}}}printf("\nThe best hired man is %d and %d", same_birthday_p1, same_birthday_p2);}void permute_by_sorting(int p[PERSON_NUM]) {int count = PERSON_NUM;srand(time(0));for (size_t i = 0; i < count; i++){p[i] = rand()%365;printf("%d, ", p[i]);}}

PERSON_NUM设为10和40的输出结果： 

 概率分析

i人和j人两个生日相等且在r日的概率 P[r]= 1/365*1/365. 令n=365. P[r]=1/n*n.

而i人和j人生日相等的情况有1，2，3…,365种，所以P = P[r]*n = 1/n.

以下的代码中，最后执行了判断语句中的语句时，有X个人相同的期望值为E[X].

E[X]= k(k-1)/(2*n)  (PERSON_NUM = k, n = 365).

if(p[j] == p[i]) {same_birthday_p1 = i;same_birthday_p2 = j;break;
}

我在代码中将PERSON_NUM设为10和40的输出结果

PERSON_NUM	E(X)	结果
10	0.1232876712328767	没有相同生日的人
40	0.4931506849315068	有相同生日的人

房间中人数为40人时，出现生日相同的期望为1/2，而10人时期望仅为1/10.我输入两次得出生日的结果也与概率模型预期匹配。

球与箱子

问题描述：有b个箱子，往一个指定的箱子中投入球的概率为1/b，投出n个相同的求，指定箱子中有k个球，求k值的期望值。

k正好符合二项分布，b(n,1/b);  所以k的期望值E(K) = n/b.

---

总结

本文以雇佣问题，生日悖论和球与箱子问题入手，着重讲述如何使用概率方法分析随机算法。