Random Quicksort
在排序算法中，最常见的就是快排了，此处我们将介绍快排算法的随机版本，并且对其进行算法分析。
首先，随机版本的快排描述如下:
如果|S|>1：
- 均匀地从S中选取一个x作为中心点
- 将S分成两个子集S1,S2，其中S1中的元素都要比x小，而S2中的元素都要比x大.
- 递归地对S1,S2进行排序
排序算法的复杂度是用比较次数来进行衡量的，因此我们接下来就是要分析在随机版的快排算法中，元素比较次数的期望是多少。
Random Recurrence
现在我们来看另外一个问题，在一个给定的集合S中，选取第k小的元素(1≤k≤n).这个问题，我们之前已经讨论过了，有确定性的算法也有随机化的算法,受到快排算法的启发，我们可以设计另外的算法，来解决这个问题，该算法称为RandomQS.算法描述如下:
RandomQS(S,k)
-
如果|S|=1，返回S; 否则从S中随机选择一个x,构建两个子集S1={y∈S|y≤x},S2={y∈S|y>x}
-
如果|S1|≥k，返回RandomQS(S1,k);如果|S1|<k,返回RandomQS(S2,k-|S1|).
这是一个递归的过程，我们不禁要问，要经过多少次递归才能得到结果？
如果用T(n)表示递归调用次数的话，那么显然T(n)是一个随机变量，且其满足如下的式子:
其中，X(n)也是一个随机变量，用来表示在每一次的递归调用中，被抛弃的元素的数目。具体来说，如果当|S1|≥k时，X(n)=|S2|;当|S1|<k时，X(n)=|S1|.我们想要寻找E[T(n)]的上界。
Token Game
其实上述递归中抛弃元素的过程，可以建立一种Token Game的模型：
- 初始化的时候我们有n个Token
- 在每一轮的运行中，我们独立的选取0≤X(m)≤m,而X(m)只依赖于当前的Token数目m，选取X(m)之后抛弃X(m)个元素。
- 当没有Token剩下时，游戏结束。
一共进行的轮数用随机变量T(n)表示.
这样的模型其实在实际应用中就很常见，比如随机化的数据结构Skip List,优惠券搜集问题(Coupon Collector)和几何分布。
Karp-Upfal-Wigderson bound
对于Token Game来说，存在如下的定理来帮助我们确定T(n)的上界:
Theorem
假设存在如下的递归过程:
T(n)={1+T(n−X(n))n>c0n=c其中c是一个常量
如果存在一个非递减的正函数μ(x)对所有n满足E[X(n)]≥μ(n),则
E[T(n)]≤∫nc1μ(x)dx
应用
根据上述对RandomQS算法的描述，我们可以知道，RandomQS满足如下的递归过程:
其中，X(n)可以表示为:
可以看到，无论k取什么值，X(n)都满足X(n)≥min(m,n−m),其中m是从{0,1,⋯,n−1}中按均匀分布取出的。
很显然我们可以得到E[X(n)]≥n4,根据Karp-Upfal-Wigderson bound,可以得到:
分析
分析的基本思路是，任意两个元素发生比较的概率，然后利用期望的线性可加性来估计整个排序过程的比较次数。
假设输入的待排序的序列为S，令ai表示序列中第i小的元素，令Xij∈{0,1}来指示ai和aj是否发生比较。根据上述的算法描述，我们可以知道，只有当ai或aj被选为中心点时，它们才会发生比较。对于这样的情况，我们有如下的观测:
观察1: 任意一对的ai和aj最多只会比较一次。这是因为第一次比较之后，他们就会被分到不同的子集中了，而不同子集中的元素是绝不会再次比较的。正因为这样，对Xij进行累加，我们就能够得到整体比较的次数。而比较次数的期望就是
,而根据期望的线性可加性，我们只需要分析
就行了。
观察2: ai和aj会发生比较当且仅当{ai,aj}仍然属于同一个子集，且其中之一被选为中心点.
观察3: 如果ai和aj仍然属于同一个子集，那么所有的
都在同一个子集中。
观察4: 在每一次的排序中，如果要使得ai和aj分开在两个不同的子集中，那么中心点一定是在
之中的。
观察5: {ai,ai+1,⋯,aj−1,aj}中的任意一个元素都是以等概率选取的，这是因为在选取中心点的时候，是均匀的。
根据上述的观察，我们能够得到:
所以E[Xij]=1⋅Pr[ai和aj发生比较]≤2j−i+1
利用期望的线性可加性:
其中H(n)是第n个Harmonic number,它满足:
因此，对于任意长度为n的输入来说，随机版的快排算法的比较次数的期望是O(nlogn)