概率分析和随机算法

2024-06-06 12:28
文章标签 算法 随机 概率分析

本文主要是介绍概率分析和随机算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

雇佣问题

概率分析

随机算法 

生日悖论

随机算法

 概率分析

球与箱子

总结


雇佣问题

有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.


总结

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

这篇关于概率分析和随机算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1036103

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第