随机算法

雇佣问题：

假设你要雇佣一个新的办公室助理，雇佣代理每天想你推荐一个应聘者（连续推荐n个），你面试这个人，如果这个应聘者比目前的办公室助理更优秀，你就会辞掉当前的办公室助理，然后聘用这个新的。面试一个人需付给雇佣代理一笔费用，聘用办公助理也需要费用。

假设面试费用为$C_{i}$，雇佣的费用为$C_{h}$，假设整个过程中雇佣了m次，于是总的费用是 $nC_{i}+mC_{h}$。由于n是固定值，总费用的变化取决于m值。

这个场景用来当做一般计算范式的模型，通常情况下我们需要检查队列中的每个成员，并且维护一个目前的获胜者，来找出序列中的最大或最小值。雇佣问题是对哪一个成员当前获胜的更新频繁程度建立模型。

伪代码：假设应聘办公助理的候选人编号为1到n，该过程假设你能在面试完应聘者i后，决定应聘者是否是你目前见过的最佳人选。

最坏情况分析：
当应聘者质量按出现的次序严格递增时，实际上就雇佣了每个面试的应聘者，此时雇佣了n次，总费用是$O(nC_{h})$。

平均情况分析：
采用概率分析，前提是有一个合理的输入分布。在雇佣问题中，我们假设应聘者以随机顺序出现。
假定可以对任何两个应聘者进行比较，并决定哪一个更有资格；也就是说，所有应聘者存在一个全序关系，

关系：集合A与B上的二元关系R是笛卡尔积$A\times B$的子集。$(a,b)\in R$写作$a R b$。称R是集合A上的一个二元关系，意味着R是$A\times A$的子集。
称集合A上的关系R是一个全关系，需满足对于所有$a,b\in A$，有$a R b$或者$b R a$。

因此可以使用从1到n的唯一号码来标志应聘者的优秀程度。用rank(i)来表示应聘者i的名次。这个有序序 列<rank(1),rank(2)，..., rank(n)>是序列<1,2,...,n>的一个排列。说应聘者以随机的顺序出现，就等于说这个排名列表是1到n的n！中排列中的 任何一个，每种都以相等的概率出现。

随机算法

在许多情况下，我们对输入分布知识知之甚少；即使知道关于输入分布的某些信息，也无法对这种分布建立模型。然而通过使一个算法中的某些部分的行为随机化，就常常可以利用概率和随机性作为算法设计和分析的工具。
比如在雇佣问题中，如果雇佣代理给我们一份应聘者的名单，每天我们随机地挑选一个应聘者进行面试，从而确保了应聘序列的随机性。
更一般地，如果一个算法的行为不只有输入决定，同时也由随机数生成器所产生的数值决定，则称这个算法是随机的。

由以上描述可知概率分析和随机算法的区别：
概率分析是对输入做假设，假设输入服从某种分布（例如假设输入是随机的），然后根据假设的概率前提来分析期望情况。
而随机算法是通过一个算法来重新排列输入，使得输入变的随机化。

相关问题1：

1）Describe an implementation of the procedure RANDOM(a,b) that only makes calls to RANDOM(0,1). What is the expected running time of your procedure as a function of a and b?
解答：这个题目相当于在能随机生成0,1的前提下，要求生成[0, 1, ...,n-1]范围内的一个整数
1 求出最小的 m，使2^m >= n-1
2 通过random(0,1)，产生一个m比特的整数，这样能随机产生[0, 2^m-1]内的整数，若产生的整数位于[0, n-1]内，则取这个数作为结果。如果这个数在[0,n-1]外，则丢弃它，再次运行算法重新生成一个。
a) 证明上述算法可以产生 [0, n-1]范围内的随机数
在范围[0,1, ..., n-1, n, ..., 2^m-1]范围内，总共有p = 2^m个数，其中合法的数是[0, 1, ..., n-1]共n个，非法的数为
[n, ..., 2^m-1]共q = 2^m-n个，则有 n + q = p
算法最后会产生一个合法的随机数，假设得到数i的概率为Pi，0 <= i <= n-1， 则

所以上述方法可以产生随机数。
b) 求算法运行的期望时间
设Pi表示产生随机数时运行了i次算法的概率，那么前i-1次产生的都是非法的数，第i次产生的是合法的数，所以

 

---

输入的分布有助于分析一个算法的平均情况行为，许多时候，我们无法得知输入分布的信息，因而阻碍了平均情况分析。

对于诸如雇佣问题之类的问题，其中假设输入的所有排列等可能出现往往有益，通过概率分析可以指导设计一个随机算法。我们不是假设输入的一个分布，而是设定一个分布。特别地，在算法运行前，先随机的排列应聘者，以加强所有排列都是等可能出现的性质。

引理：过程RANDOMIZED-HIRED-ASSISTANT的雇佣费用期望是$O(c_{h}lnn$。

随机排列数组

假设给定一个数组A，包含元素1到n，构造这个数组的一个随机排列。

1）为数组的每个元素A[i]赋予一个随机的优先级P[i]，然后根据优先级对数组A中的元素进行排序。

例如，初始数组A=<1,2,3,4>，随机选择的优先级P=<36,3,62,19>，则将产生一个数组B=<2,4,1,3>。称这个过程为PERMUTE-BY-SORTING。

注：第四步，使用范围$1~n^{3}$是为了让P中所有优先级尽可能唯一，所有元素 都唯一的概率至少是$1-1/n$。

这个过程中耗时的步骤是排序。如果使用比较排序，排序将花费$\Omega(nlgn)$。我们可以达到这个下界，归并排序时间代价为$\Theta(nlgn)$。

需要证明这个过程能产生一个均匀随机排列，即该过程等可能地产生数字1~n的每一种排列。

Stupid Algorithm，不再深究。

2）原址排列给定数组。RANDOMIZE-IN-PLACE在O(n)时间内完成。在第i次迭代时，元素A[i]是从元素A[i]到A[n]中随机选取的。第i次迭代以后，A[i]不再改变。

一个具有n个元素的k排列是包含这n个元素中的k个元素的序列，并且不重复。一共有\(n!/(n-k)\)种可能的排列。