线性时间选择-分治算法

问题描述给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。在线性时间内O（n）？k=1;最小元素O(n)k=n;最大元素O(n)k=(n+1)/2:中位数O(n)?算法思想线性时间选择问题的分治法：模仿快速排序算法，找第k小元素。思想:对输入数组递归划分，但仅对划分出的子数组之一进行递归处理。主要算法template<class Type&

迷雾总会解

4003人浏览 · 2020-06-30 22:30:02

迷雾总会解 · 2020-06-30 22:30:02 发布

问题描述

给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。在线性时间内O（n）？

k=1; 最小元素 O(n)
k=n; 最大元素 O(n)
k=(n+1)/2: 中位数 O(n)?

算法思想

线性时间选择问题的分治法：模仿快速排序算法，找第k小元素。

思想:对输入数组递归划分，但仅对划分出的子数组之一进行递归处理。

主要算法

template<class Type>
Type RandomizedSelect(Type a[ ], int p, int r, int k)
{
     if (p==r) return a[p];
 	 //一次快速排序，随机选择基准元素，划分数组
     int i=RandomizedPartition(a,p,r), 
     j=i-p+1;        // j为a[p,i]中元素个数
     if (k<=j) return RandomizedSelect(a,p,i,k);
  	  //返回第k-j小元素
      else return RandomizedSelect(a,i+1,r,k-j);
}

小例子

有一个数组:{ 4, 2, 5, 7, 4, 9, 6, 21 }
在这里插入图片描述

复杂度分析

平均时间复杂度

在这里插入图片描述

可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素

最坏时间复杂度

在最坏情况下（找最小，但总在最大处划分），算法randomizedSelect需要O(n²)计算时间。
在这里插入图片描述

在这里插入图片描述

完整算法

//2d9-1 随机划分线性时间选择
#include "stdafx.h"
#include <iostream> 
#include <ctime>
using namespace std; 

int a[] = {5,7,3,4,8,6,9,1,2};

template <class Type>
    void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
    int Partition(Type a[],int p,int r);

template<class Type>
    int RandomizedPartition(Type a[],int p,int r);

template <class Type>
    Type RandomizedSelect(Type a[],int p,int r,int k);

int main()
{
    for(int i=0; i<9; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    cout<<RandomizedSelect(a,0,8,3)<<endl;
}

template <class Type>
    void Swap(Type &x,Type &y)
{
    Type temp = x;
    x = y;
    y = temp;
}

inline int Random(int x, int y)
{
    srand((unsigned)time(0));
    int ran_num = rand() % (y - x) + x;
    return ran_num;
}

template <class Type>
    int Partition(Type a[],int p,int r)
{
    int i = p,j = r + 1;
    Type x = a[p];

    while(true)
    {
        while(a[++i]<x && i<r);
        while(a[--j]>x);
        if(i>=j)
        {
            break;
        }
        Swap(a[i],a[j]);
    }
    a[p] = a[j];
    a[j] = x;
    return j;
}

template<class Type>
    int RandomizedPartition(Type a[],int p,int r)
{
    int i = Random(p,r);
    Swap(a[i],a[p]);
    return Partition(a,p,r);
}

template <class Type>
    Type RandomizedSelect(Type a[],int p,int r,int k)
{
    if(p == r)
    {
        return a[p];
    }
    int i = RandomizedPartition(a,p,r);
    int j = i - p + 1;
    if(k <= j)
    {
        return RandomizedSelect(a,p,i,k);
    }
    else
    {
        //由于已知道子数组a[p:i]中的元素均小于要找的第k小元素
        //因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
        return RandomizedSelect(a,i+1,r,k-j);
    }
}

别急！这个算法有很大的缺陷，接下来我们来解决一下最坏时间复杂度的问题
在这里插入图片描述

最坏时间复杂度的问题思考

若能在O(n)内找到一个划分基准，使得所划分的2个子数组长度，都至少为原数组长度的ε倍(0<ε <1 )，则在最坏情况下用O(n)时间完成选择任务。
在这里插入图片描述

例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式：
T(n)≤T(9n/10)+O(n)

由此可得T(n)=O(n)

是不是一下子就把最坏时间复杂度从O(n²)变成了O(n)。接下来的问题就是如何寻找划分基准?

寻找划分基准-O(n)算法

基本思想

定义查找第k小元素算法为 Select(Type a[], int p, int r, int k)
将n个输入元素划分成 $\lceil n/5 \rceil$ 个组，每组5个元素，只可能有一个组不是5个元素。
用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共 $\lceil n/5 \rceil$ 个。
递归调用算法select来对 $\lceil n/5 \rceil$ 个组按照中位数排序，同时，找出这 $\lceil n/5 \rceil$ 个中位数元素的中位数。
如果 $\lceil n/5 \rceil$ 是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。

将中位数的中位数x，作为基准元素

在这里插入图片描述

简单划分案列
在这里插入图片描述

计算大于和小于基准X的元素数目

组中除了中位数，小于基准x的元素个数有：
在这里插入图片描述

中位数中小于基准x的个数为：
在这里插入图片描述

因此，小于基准x的元素个数至少为：
在这里插入图片描述

同理，大于基准x的元素个数至少为：
在这里插入图片描述

在这里插入图片描述

红框表示的是一定小于基准X的元素
蓝框表示的是一定大于基准X的元素
两者的值理论上是相等的

要注意一下n≥75的情况

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

主要算法

Type Select(Type a[], int p, int r, int k)
{   
    if (r-p<75) {
        //用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
    };
    for ( int i = 0;  i<=(r-p-4)/5;  i++ ) // i代表组数
    {
        //将元素每5个分成一组，分别排序
        BubbleSort(a, p+5*i, p+5*i+4); 
        //将该组中位数与a[p+i]交换位置,即： 将a[p+5*i] 至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
        Swap(a[p+5*i+2], a[p+i]); 
    }  //  O(n)
    //找中位数的中位数
    Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10); // T(n/5)
    int i=Partition(a, p, r,  x), //  O(n)
    j=i-p+1;
    if (k<=j) return Select(a, p, i, k);
    else return Select(a,i+1,r,k-j);     
}

在这里插入图片描述

复杂度分析

设找第K小元素的算法的时间复杂性是: T(n)

找中位数的中位数: T(n/5)

调用快速排序partition函数对每个数组进行排序: O(n):

按照上述方法所选的基准x进行划分，得到的两个子数组分别至多有3n/4个元素：T(3n/4)

在这里插入图片描述

算法

//中位数线性时间选择
#include <ctime>
#include<stdlib.h>
#include <iostream>
#include<algorithm>
using namespace std;

template <class Type>
void Swap(Type &x,Type &y);

inline int Random(int x, int y);

template <class Type>
void BubbleSort(Type a[],int p,int r);

template <class Type>
int Partition(Type a[],int p,int r,Type x);

template <class Type>
Type Select(Type a[],int p,int r,int k);

int main()
{
	//初始化数组
	int a[100];

	//数字索引
	int k;

	//必须放在循环体外面
	srand((unsigned)time(0));

	for(int i=0; i<100; i++)
	{
		a[i] = Random(0,500);
		cout<<"a["<<i<<"]:"<<a[i]<<" ";
	}
	cout<<endl;


	cout<<"请输入您要获取的数字索引(从1开始)：";
	cin>>k;


	cout<<"第"<<k<<"个元素是"<<Select(a,0,100,k)<<endl;



	//重新排序，对比结果
	BubbleSort(a,0,100);

	for(int i=0; i<100; i++)
	{
		cout<<"a["<<i<<"]:"<<a[i]<<" ";
	}
	cout<<endl;
}

template <class Type>
void Swap(Type &x,Type &y)
{
	Type temp = x;
	x = y;
	y = temp;
}

inline int Random(int x, int y)
{
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}

//冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
	 //记录一次遍历中是否有元素的交换
     bool exchange;
     for(int i=p; i<r-1;i++)
     {
		exchange = false ;
        for(int j=0; j<r-1-i; j++)
        {
			if(a[j]>a[j+1])
            {
                Swap(a[j],a[j+1]);
                exchange = true;
            }
        }
        //如果这次遍历没有元素的交换,那么排序结束
        if(false == exchange)
		{
             break ;
		}
	 }

}

template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
	int i = p-1,j = r ;

	while(true)
	{
		while(a[++i]<x && i<r);
		while(a[--j]>x);
		if(i>=j)
		{
			break;
		}
		Swap(a[i],a[j]);
	}
	return j;
}


template <class Type>
Type Select(Type a[],int p,int r,int k)
{
	if(r-p<75)
	{

		//BubbleSort(a,p,r);
        sort(a + p, a + r);
		return a[p+k-1];
	}


	for(int i=0; i<=(r-p-4)/5; i++)
	{
		//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置
		//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数
		//BubbleSort(a,p+5*i,p+5*i+4);
		sort(a+p+i*5,a+p+5*i+4);
		Swap(a[p+5*i+2],a[p+i]);
	}


	//找中位数的中位数
	Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);




     int i = Partition(a,p,r,x);


	int j = i-p+1;



	if(k<=j)
	{
		return Select(a,p,i,k);
	}
	else
	{
		return Select(a,i+1,r,k-j);
	}

}

该代码还是有一些小bug，输出的值有时候有一些偏差，并且用冒泡算法代替sort()也有一些小问题。暂时不想去改了，以后有时间再看吧。

测试用例

随机产生的100个数据
a[0]:402 a[1]:436 a[2]:336 a[3]:309 a[4]:130 a[5]:154 a[6]:348 a[7]:96 a[8]:141 a[9]:168 a[10]:375 a[11]:159 a[12]:253 a[13]:269 a[14]:137 a[15]:228 a[16]:254 a[17]:385 a[18]:301 a[19]:185 a[20]:169 a[21]:48 a[22]:472 a[23]:131 a[24]:353 a[25]:457 a[26]:360 a[27]:315 a[28]:211 a[29]:278 a[30]:395 a[31]:430 a[32]:489 a[33]:296 a[34]:108 a[35]:489 a[36]:255 a[37]:78 a[38]:433 a[39]:320 a[40]:370 a[41]:213 a[42]:53 a[43]:319 a[44]:469 a[45]:294 a[46]:444 a[47]:63 a[48]:101 a[49]:351 a[50]:89 a[51]:270 a[52]:151 a[53]:306 a[54]:171 a[55]:5 a[56]:159 a[57]:164 a[58]:215 a[59]:472 a[60]:103 a[61]:78 a[62]:405 a[63]:499 a[64]:297 a[65]:314 a[66]:129 a[67]:296 a[68]:262 a[69]:27 a[70]:32 a[71]:386 a[72]:175 a[73]:136 a[74]:479 a[75]:424 a[76]:234 a[77]:434 a[78]:159 a[79]:100 a[80]:485 a[81]:397 a[82]:341 a[83]:82 a[84]:348 a[85]:234 a[86]:12 a[87]:351 a[88]:277 a[89]:486 a[90]:365 a[91]:303 a[92]:151 a[93]:381 a[94]:291 a[95]:115 a[96]:243 a[97]:324 a[98]:279 a[99]:319

输入
请输入您要获取的数字索引(从1开始)：25

输出
第25个元素是151

排序好的数组
a[0]:5 a[1]:12 a[2]:27 a[3]:32 a[4]:48 a[5]:53 a[6]:63 a[7]:78 a[8]:78 a[9]:82 a[10]:89 a[11]:96 a[12]:100 a[13]:101 a[14]:103 a[15]:108 a[16]:115 a[17]:129 a[18]:130 a[19]:131 a[20]:136 a[21]:137 a[22]:141 a[23]:151 a[24]:151 a[25]:154 a[26]:159 a[27]:159 a[28]:159 a[29]:164 a[30]:168 a[31]:169 a[32]:171 a[33]:175 a[34]:185 a[35]:211 a[36]:213 a[37]:215 a[38]:228 a[39]:234 a[40]:234 a[41]:243 a[42]:253 a[43]:254 a[44]:255 a[45]:262 a[46]:269 a[47]:270 a[48]:277 a[49]:278 a[50]:279 a[51]:291 a[52]:294 a[53]:296 a[54]:296 a[55]:297 a[56]:301 a[57]:303 a[58]:306 a[59]:309 a[60]:314 a[61]:315 a[62]:319 a[63]:319 a[64]:320 a[65]:324 a[66]:336 a[67]:341 a[68]:348 a[69]:348 a[70]:351 a[71]:351 a[72]:353 a[73]:360 a[74]:365 a[75]:370 a[76]:375 a[77]:381 a[78]:385 a[79]:386 a[80]:395 a[81]:397 a[82]:402 a[83]:405 a[84]:424 a[85]:430 a[86]:433 a[87]:434 a[88]:436 a[89]:444 a[90]:457 a[91]:469 a[92]:472 a[93]:472 a[94]:479 a[95]:485 a[96]:486 a[97]:489 a[98]:489 a[99]:499

在这里插入图片描述