文档介绍：计算机算法设计与分析
题目: 线性时间选择问题
院(系): 数学与计算机学院
年级专业: 信息与计算科学
姓名: 杨松
学号: 201210802023
指导教师: 鄢莉
二〇一四年十一月十九日
攀枝花学院教务处制
一、实验目的:
熟悉掌握分治算法设计技术
二、实验内容:
给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。
对于线性序列集合中元素个数比较少的情况,可以先排序,再选择这n个元素中第k小的元素。但排序的时间复杂度最好是O(nlogn)。
如果能在线性时间内找到一个划分基准,使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数),那么就可以在最坏情况下用O(n)时间完成选择任务。
实验要求:
1、按教材所授内容要求,完成“线性时间选择问题”算法。得到一个完整正确的程序。
2、问题规模:不少于2000
3、输出最终结果。
实验设备:
Windows 7系统、Visual C++
算法分析:
将n个输入元素划分成én/5ù个组,每组5个元素,只可能有一个组不是5个元素。用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共én/5ù个。
递归调用select( )来找出这én/5ù个元素的中位数。如果én/5ù是偶数,就找它的2个中位数中较大的一个。以这个元素作为划分基准。
设所有元素互不相同。在这种情况下,找出的基准x至少比3(n-5)/10个元素大,因为在每一组中有2个元素小于本组的中位数,而n/5个中位数中又有(n-5)/10个小于基准x。同理,基准x也至少比3(n-5)/10个元素小。而当n≥75时,3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。
按照此法计算所花费时间为:T(n)=O(n)
程序源码:
#include <iostream>
#include <ctime>
using namespace std;
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()
{
void SelectionSort(int a[]);
int s;
int a[2000];
int b[2000];
for(int i=0; i<2000; i++)
{
a[i]=b[i]=rand()%10000;
cout<<a[i]<<" ";
}
cout<<endl;
SelectionSort(b);
for