转载

「随机化快排」期望运行时间证明

快速排序

快速排序是比较排序的一种，其最坏运行时间 $/theta (n^2)$，期望运行时间为 $/theta(nlgn)$。并且能够原址排序。实际中的很多排序都由此优化而来。

本文主要不对算法的程序实现进行讨论，主要关注其随机化，及背后的数学证明。

在《算法导论》上，快速排序用 Python 表示大致如下：

   def quickSort(arr,start,end):   pivot = end   i = partition(arr,pivot,start)   if (i > start + 1):    quickSort(arr,start,i - 1)   if (i < end - 1):    quickSort(arr,i + 1,end)   def partition(arr,pivot,start):   x = arr[pivot]   i = start - 1   for index in range(start,pivot):    if (arr[index] <= x):     i = i + 1     swap(arr,i,index)   swap(arr,i + 1,pivot)   return i + 1  def swap(arr,i,j):   tem = arr[i]   arr[i] = arr[j]   arr[j] = tem

需要注意的是关键的子程序 partition：即选定主元（pivot），对「部分」数组进行重整，将比主元小的元素置于其前，比主元大的置于其后。

随机化

如上的快速排序并不能保证较好的最坏运行时间。设想当数组倒序时，如上程序的运行时间就到 $n^2$ 这个数量级了。

为了能够尽量地获得期望的运行时间 $/theta(nlgn)$，应当在算法中引入随机性，减少最坏情况发生的概率。而引入随机性的位置正是子程序 partition。可以看到在上述的快速排序中，partition 过程中是比较暴力地把 pivot 定为子数组的最后一个元素。

那么只要我们加入类似这样的步骤：

         i = randomSelect(arr,pivot,start)     swap(arr,i,pivot)

就能保证作为主元的元素是理论上随机的了。

在保证其随机性之后，就到了本文的重点：如何证明快排的期望运行时间为 $/theta(nlgn)$。

猜出这个值倒是并不难。毕竟接触排序问题的时候分治思想是那么普遍，式子里不带个对数都觉得不自在吧（逃

期望运行时间的数学证明

这一部分有抄书之嫌，有《算法导论》在手的童鞋当然可以自己去看啦~

在整个快速排序的过程中，耗时的部分大致有二：

循环内 partition 中主元和其它元素的比较操作
循环外的常数级操作

存在变数的是第一部分，因为一次 partition 选择的主元是由上一次决定的。而上一次 partition 后所在数组的位置无法确定（主元的选择本身就是随机的嘛）。在最坏的情况下，主元依旧会落在数组的头部或尾部，如果一直都这么「倒霉」，那么每次迭代无非是对 $n - 1$ 个元素重复上次操作，并最终导向 $n^2$ 的数量级。

算法导论的证明方法是整体性，而不局限于单次的 partition 过程。书中的证明出发点是：

1.每次 partition 过程中，只有主元有和其它元素比较的机会，并且主元在此次过程后，就不会再和任何其它元素比较了（迭代时主元被排除在外了）。2.一旦某次 partition 后两个元素被主元分开成两个部分，那么也不会再发生比较了。

假设研究的对象是数组 $A$ ，并且将 $A$ 中的每个元素定义为 $z_1,z_2,z_3 ... z_n$。这里的 $z_i$ 表示为 A 中第 $i$ 小的元素。接着我们定义一个集合

$$Z_{ij}=//lbrace z_i,z_{i+1},z_{i+2},...,z_j/rbrace $$

为 zi 和 zj 之间的元素集合。

需要格外注意的是，定义$Z_{ij}$并不意味着将整个数组 $A$ 按顺序排列了。集合$Z_{ij}$中位于$zi$和$zj$之间的元素可以分布于数组的任何一个位置。

此外，定义元素$i$和元素$j$发生比较的指示器随机变量为：

$$X_{i,j} = I/lbrace z_i 和z_j发生比较 /rbrace$$

那么总的比较次数 X 可表示为：

$$X = /sum_{i=1}^{n-1} /sum_{j={i+1}}^{n}X_{ij}$$ $$

基于以上两点，在整个迭代过程里，$Z_i$和 $Z_j$ 发生比较的可能性只存在于，对于集合 $Z_ij$ 中所有的元素，在某次 partition 操作中，$Z_i$ 和 $Z_j$ 中的任意一个被「第一个」选择为主元，除此之外，这两个元素都将被主元一分为二，不再有比较的机会。所以对于 $Z_i$ 和 $Z_j$ ，其发生（一次）比较的概率可表示为：

$$Pr/lbrace Z_i 为 Z_{ij} 中第一个被选出的主元/rbrace + Pr/lbrace Z_j 为 Z_{ij} 中第一个被选出的主元 /rbrace$$

比较容易得出，$z_i$ 和 $z_j$ 被选为主元的概率同是

$$/frac{1}{j-i+1}$$

那么考虑期望 $E(X)$ 就可以表示为：

$$X = /sum_{i=1}^{n-1} /sum_{j={i+1}}^{n}/frac{2}{j-i+1}$$

令 $K = j - i$，上式可以转化为：

$$X = /sum_{i=1}^{n-1} /sum_{k=1}^{n-i}/frac{2}{k+1}$$

而

$$X = /sum_{i=1}^{n-1} /sum_{k=1}^{n-i}/frac{2}{k+1} < X = /sum_{i=1}^{n-1} /sum_{k=1}^{n-i}/frac{2}{k}$$

这里可以利用数学上调和级数的相关证明：

调和级数本身是发散的，但是其与$lgn$的差所构成的通项：

$$x_n=1+/frac{1}{2}+/frac{1}{3}+...+/frac{1}{n}-lnn$$