用随机算法求第k小项 - 图文

1， 问题描述

设A[1,n]是一个有n个数组成的无序数列，寻找其第k小元素就是将A按照非递减的顺序排列后，新序列中的第k个元素。

寻找第k小元素最直接的方法就是直接将A进行排序， 然后取出第k个元素，但是此类方法时间复杂度较高，至少需要Ω(nlogn)时间，因为基本所有已学的排序方法在最坏情况下都需要这么多时间。

在第三章中老师课上教导了利用分治法求第k小元素的算法，其时间复杂度为O（n）。其基本思想如下：在分治法递归调用的每一个划分步骤中都将舍弃一定比例的元素，而在剩余元素中寻找目标。故在我的理解中这种分治法的性能主要依赖于每次递归调用能舍去的元素的比例，以及为舍弃这些元素所花费的代价。在之后的学习中，我们又接触到了随机算法，不由思考，分治法中的划分可以不可以通过随机算法来随机选择一个位置，然后根据这个位置进行舍弃序列中的元素，有没有办法改进算法。

2， 随机选择算法

Algorithm: RandomSelect (A[low, high], k)

输入：数组A[low,...high]和整数k，1≤ k≤ high-low+1 输出：A[low…high]中的第k小元素

v ← random(low,high)

x ←A[v]

将A[low…high]分成三部分

A1＝{a|a < x} A2＝{a|a = x} A3={a|a > x} //Θ(n) case

| A1 |≥ k : return RandomSelect(A1[1, |A1|], k) | A1 |+| A2 |≥ k : return x

| A1 |+| A2 | < k: return RandomSelect(A3[1,|A3|], k-|A1|-|A2|)

end case

该部分算法ppt与书上已经提到，其时间复杂度的期望比较次数C(n)≤4n，此外每个元素与基准元素x至少比较一次。故C(n)≥n

及n≤C(n)≤4n,故时间复杂度为Θ（n） 这部分书上与ppt上已有证明就不过多论述了

3， 对以上随机算法的一种思考改进

分析以上算法不难发现，其先随机选择一个位置v，然后根据v进行对元素的舍弃，所以每次舍弃不同个元素的概率是相同的，我就思考可不可以让选中舍弃较多元素的位置的概率更大，让算法有更大几率舍弃掉较多的元素。

算法的想法如下：如果随机选择一个位置的元素进行比较，每个位置的可能性是均等的，取到的数值可能最大、最小，也可能中间，如果是最大最小的情况，每次舍弃的数值就只能有一个，只有尽可能的取大小排在中间的数值，才能舍去较大的元素，故我思考，不妨选择随机选择两个位置，v,j令x=(A[v]+A[j])/2,然后通过x进行分组，这样取到数值为中间大小的数比取到最大最小值的可能性更高，舍弃较多数

的几率更大。进而进行了优化。

理论上，选择的随机位置越多，平均后，舍弃掉较多数的可能越大，但是这就退化近似成取中值进行分治法求第k小元素的方法，丧失了随机算法的优点，将直接随机到最优解和较优解的可能性也降低了，所以我尝试取2个随机位置的方法进行优化。

并且当选择两个随机位置时，序列长度小于等于2个时，没有执行随机算法的必要

先从一个特例分析其取到各位置的理论概率大小，令n=8，其取到不同位置的概率如下表（为表示清晰，v,j位置为A进行排序后的位置）

由表格数据可以发现，此时数组划分数据x可能处于不同的位置的概率分为别为:

3/64,7/64,11/64,15/64,13/64,9/64,5/64,1/64 显然舍去较多数的几率更高。

改进的随机算法：

Algorithm: NewSelect (A[low, high], k)

输入：数组A[low,...high]和整数k，1≤ k≤ high-low+1

输出：A[low…high]中的第k小元素

If(high-low≤2)then

If(k==1) then return min(A[low],A[high]) Else return max(A[low],A[high]) End if else

v ← random(low,high) j ← random(low,high) x ←（A[v]+A[j]）/2

将A[low…high]分成三部分

A1＝{a|a < x} A2＝{a|a = x} A3={a|a > x} //Θ(n)

case

| A1 |≥ k : return NewSelect(A1[1, |A1|], k) | A1 |+| A2 |≥ k : return x

| A1 |+| A2 | < k: return NewSelect (A3[1,|A3|], k-|A1|-|A2|)

end case end if

该算法的最坏情况与最初算法是一致的，但是其舍弃较大数的可能性应该较大，下面进行时间复杂度的理论分析

4， 时间复杂度分析

仿照ppt上对原算法的证明方式，证明如下（因为个人对数学公式符号用电脑表示不熟悉，而且因为证明较繁琐故用手写证明拍照如下，往老师见谅。）

由证明可知，改进后的算法的时间复杂度也是Θ（n），虽然数量级相同，但是其前系数还是减小了。

模拟仿真：实际编程，比较实际情况中原算法与改进算法的执行次数，发现其是否有改进。为使数据明显，取n值较大，当n=5000时，不同k的执行次数如表

格:

当k不同时，进行数据拟合，结果如下

及O(k)=-2.1nlogn -469.2logn+26.80n+11010.2706

当n改变时，做出其一次关系式，改进后的算法时间复杂度绘图如下

O(n)= 2.579n

5， 总结

通过以上的分析证明，以及最后的数据拟合可以发现，改进后的算法在解决第k小元素的问题上，算法时间复杂度最小，故其对原算法进行了改进。明显可见，随机算法时间复杂度远好于确定型的算法的时间复杂度，改变随机算法随机出的情况的不同概率也可以进一步优化随机算法。

本文来源：https://www.bwwdw.com/article/nn5g.html