RT

目录

  1. 招聘问题
  2. 随机算法

招聘问题

我想看我博客的还是学生人群偏多吧,本身很快就要去面试了,在这篇博客的问题中,我们就把自己当作Boss过把瘾。

某天,你想雇用一名算法工程师。当然,不可能让你这个Boss亲自去到处练习应聘者,而是选择了中介。雇用中介每天都会给你推荐一个应聘者(PS:还是让自己轻松点,一天只应聘一个人哈)。是个地球人都知道,你必须要给中介付一小笔钱。然后如果你雇用了一个应聘者则需要更多的钱,一来你要解雇现有的算法工程师,更重要的是你要付给中介一大笔钱。在这个问题中还有一个关键的问题,虽然有些不合情理——只要遇到更好的算法工程师,你都会把之前的给解雇掉(忽略合同等等哦)。

相信大家一看这个问题就知道重点是什么了,钱,钱,钱,还是钱。你希望费用是最低的。

那么解决这个问题的逻辑呢,当然就是:

1)从1到n个应聘者中不断地面试
2)如果当前应聘者比上一个更好,则雇用当前应聘者并解雇上一个雇用者

问题是如何将实际问题转换成伪代码,伪代码才是最重要的,有了它你便可以将其改成任何语言的描述。

1
2
3
4
5
6
7
HIRE-ALGORITHM-ENGINEER(n)
1 employee=0
2 for i=1 to n
3 interview candidate i
4 if candidate i is better than employee
5 employee = i
6 hire candidate i

相比大家都看过该系列的前两篇算法博文呢吧?这一篇和前面两篇的区别在于问题的角度不同了,以前我们考虑执行时间,现在我们考虑雇用所花的费用。

大家想想这和前面用到的归并排序有哪些相似点呢?

不管是执行时间,还是花费费用,在算法之中都是由一些操作来执行的,所以终究还是逃离不了算法的分析。

如前所述,假定总共有n个人需要面试,有m个人最终被雇用。面试一个应聘者时需要给中介的费用是小的,设为$c_s$;而在你面试通过了这个应聘者后给中介的费用才是大的,设为$c_b$。

所以这个算法总共要花费的费用为$O(c_sn+c_bm)$。大家应该有很清晰的理解这个问题吧?为什么最终由m个人被雇用而不是1个人被雇用呢。原因是这样的:比如说你现在面试了一个应聘者,你觉得他蛮优秀的,但是在10天你又遇到了一个更加优秀的,于是你便辞退了先前的雇员,聘请了最新看中的应聘者。

所以说,无论如何我们都会面试n个人,总费用$c_sn$也是固定的,真正对算法有着深远(波动)影响的应该是这雇用的m个人。

这个是时候,我们就按情况的不同作具体分析了。

很显然,如果这些应聘者按优秀程度(仅仅是举个例子)来递增顺序进行面试,最优秀的最先面试,那么你在应聘这个方面所花费的价钱就仅仅是$c_s*1$了。

相反,如果是按照递减顺序进行面试,那优秀的最后面试,那么这下麻烦可大了,你所花费的价钱就是$c_s*n$,如果n特别大那就更加糟糕了。

这个例子也许不够让大家印象深刻,那就再来一个例子。就比如说学校、公司、电视台等的各种晚会,为了更加吸引观众更多的关注当然要最好的节目留在最后了,这也是传说中的压轴。如果最后的节目一开始就结束了,后面的节目也许就没多人人想看了,这个问题就是前面的雇用问题有着相同的思想,当然了,情况是相反的。说到压轴,也许举高考的例子更加合适吧?如果把压轴题放在一开始,或者随意放置……那岂不是一片混乱?为了考生考虑都统一把压轴题放到了最后。

如果大家理解了上面的描述,那就相当于理解了最坏情况分析

在这个算法中,我们显然不可能每次都去强制控制它的输入,因此便有了随机算法这么一说。

所谓的随机算法,就是使用排列的顺序随意。选取一个主元,输入的顺序便不重要了。无论所提供的输入是递增排序还是递减排序,亦或是没有排序,都对算法没有影响,因为输入是什么根本就不重要了。我们都会将其打乱,让它们随机分布。

既然选择了这个算法,自然有它的优点:

1)它的运行时间不依赖于输入序列的顺序
2)无需对输入序列的发布做任何假设
3)无论是怎样的输入都不会引发最差的运行情况
4)而最差的情况却是由随机数产生器决定的

那么什么样的算法是随机的呢?

其行为不仅由输入决定,而且也有随机数生成器产生的数值决定,这种算法就是随机的。

话说回来什么叫做随机数生成器呢?

随机数生成器RANDOM,通过调用RANDOM(a,b)而返回a到b之间的整数且每个整数都以等概率出现。

然而许多编程环境/语言都会提供一个伪随机数生成器(比如说C#里面的Random),它其实是一个确定性算法,只不过其结果在统计上看上去是随机的。

在分析随机算法时,和前面的就有区别了。我们开始以运行时间的期望值来衡量,而输入值也通过随机数来生成。所以随机算法的运行时间也叫做期望运行时间,因为这一切都是不确定的,所以我们只能期望,期望,期望。

如果一个算法的输入是概率分布的,那么就分析其平均情况运行时间;当算法本身对于输入可以通过随机过程来选择,那么就分析其期望运行时间。

随机算法

我们不是假设输入的一个分布,而是设定一个发布。也就是说在这个算法开始前,先随机化它的输入,让这些输入拥有等可能的出现概率。

每次运行这个算法时,执行都依赖于随机选择,所以执行很和前面的不同。因此变有了前面”无论是怎样的输入都不会引发最差的运行情况“的优点。

所以对于前面的伪代码唯一需要改变的只是增加”随机化应聘者序列“这一段。

1
2
3
4
5
6
7
8
RANDOMIZED-HIRE-ALGORITHM-ENGINEER(n)
1 randomly permute the list of candidates
2 employee=0
3 for i=1 to n
4 interview candidate i
5 if candidate i is better than employee
6 employee = i
7 hire candidate i

那么问题来了,伪代码中的第1行该如何实现呢?还记得键值对么,这是我一开始觉得比较牛叉的概念,后来发现也不过如此。这里我们就可以用到这个理念。

我们给数组中的每个元素赋一个优先级,优先级和数组中的元素都是数字。以往我们给数组中的元素排序都是直接按元素的大小进行比较、排序的,这里则跑开了元素本身,通过元素对应的优先级来比较,优先级优先的数即更小,我们也可以将其排在后面。

1
2
3
4
5
6
Sort-By-Priority(A)
1 n=A.length
2 let P[1...n] be a new random array
3 for i=1 to n
4 P[i]=RAMDOM(1,n^2)
5 sort A, using P as sort keys

这里我们将优先级是范围设为了1到$n^2$,其实只是为了扩大它的范围以不至于优先级重叠,你当然也可以设置为n的三次方,或是4次方。


本站地址:http://nomasp.com/

欢迎交流,转载请联系本人,多谢🙏