算法分析线性时间选择复杂度分析
第二组：袁瑾(计科1304：201308010410)，
欧阳玉峰（计科1304:201308080216），
程帆瑾（物联1302:201378010206）。

一、问题描述：
给一个线性序列，要求在一个平均时间线性的情况下进行第k小元素的选择。

二、方法一：
模仿快速排序的方法对输入序列进行递归划分，但只对划分出的子数组之一进行递归处理。

代码如下：
RandomizedSelect(a, p, r, k):
if p==r :
return a[p]
i = RandomizedPartition(a,p,r)
j = i-p+1
if k<=j :
return RandomizedSelect(a,p,i,k)
return RandomizedSelect(a,i+1,r,k-j)
三、方法一时间复杂度：
先从上边的函数说起。

其实质是模拟一个快速排序的过程。

快速排序是随机选择一个轴值，然后比轴值小的排在左边，比轴值大的排在右边。

上边的函数四个参数a,p,r,k。

a是数组的参数，p是数组开始元素的下标，r的数组结束的下标。

k是找第k小的元素。

每次划分所需要的时间是O(n),此时每个元素需要和轴值进行比较一次。

所以最好的情况是选完轴值一次快排后，左边刚好有k-1个元素，则此时轴值则是第k小元素。

而一般情况是，轴值左边有m个元素，m<k时，在右边找第k-m小的元素，m>k时，在左边找第k小的元素。

平均复杂度是O(n)。

最坏的情况是轴值每次选的都是刚好最大的元素或者最小的元素，此时时间复杂度是O(n*k)。

四.方法二：
能在线性时间内找到一个划分基准，使得按照这个基准所划分出的两个子数组长度都至少为元数组长度的 m 倍：
Select(a, p, r, k):
if r-p<MG :
sort(a[p:r])
return a[p+k-1]
for i in 0...(r-p-4)/5 :
将a[p+5*i]...a[p+5*i+4]的第3小元素与a[p+i]交换
x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10)
i=Partition(a,p,r,x)
j=i-p+1
if k<=j :
return Select(a,p,i,k)
return Select(a,i+1,r,k-j)
五、算法及其复杂度分析：⌊3(n-5)/10⌋⌈n/5⌉
<1> 将所有的数n个以每5个划分为一组共⌈n/5⌉组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。

将每组中的元素排好序再分别取每组的中位数，得到个⌈n/5⌉中位数。

<2> 取这⌈n/5⌉个中位数的中位数，如果是偶数，就找它的2个中位数中较大的一个作为划分基准。

<3> 将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。

在这种情况下找出的基准x至少比⌊3(n-5)/10⌋个元素大。

因为在每一组中有2个元素小于本组的中位数，有个⌊n/5-1⌋小于基准，中位数处于1/2*⌊(n/5-1⌋，即⌊n/5⌋个中位数中又有⌊n/5-10⌋个小于基准x。

因此至少有3(⌊n-5⌋/10)个元素小于基准x。

同理基准x也至少比⌊3(n-5)/ 10⌋个元素小。

而当n≧75时⌊3(n-5)/10⌋≧n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

在线性时间内找到一个划分基准，使得按照这个基准所划分出的两个子数组长度都至少为元数组长度的 m 倍（0 < m < 1），那么在最坏情况下用O（n）时间就可以完成选择任务。

例如，m=9/10 ，算法递归调用所产生的子数组长度至少缩短1/10。

所以，在最坏情况下，算法所需的时间为T（n）满足递归式T(n) ≦ T(9n/10)+O(n)。

由此可得T（n）=O（n）。