算法设计与分析线性时间选择

1、福州大学数学与计算机科学学院计算机算法设计与分析上机实验报告（1）专业和班级姓名成绩学号实验名称线性时间选择实验目的和要求1. 理解算法设计的基本步骤和各步的主要内容，基本要求2. 加深对递归设计方法基本思想的理解实验任务1.掌握线性时间选择的基本算法及其应用 2. 利用线性时间选择算法找出数组的中位数3. 分析实验结果，总结算法的时间和空间复杂度 实验步骤1. 线性时间选择的思想：如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(0<<1),那么就可以在最坏情况下用O(n)

2、时间完成选择任务。例如，当=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)。  2. 算法正确性证明  (1)将所有的数n个以每5个划分为一组共组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。将每组中的元素排好序再分别取每组的中位数，得到个中位数。      (2)取这个中位数的中位数，如果是偶数，就找它的2个中位数中较大的一个作为划分基准。 

3、;     (3)将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。在这种情况下找出的基准x至少比个元素大。因为在每一组中有2个元素小于本组的中位数，有个小于基准，中位数处于，即个中位数中又有个小于基准x。因此至少有个元素小于基准x。同理基准x也至少比个元素小。而当n75时n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。通过上述说明可以证明将原问题分解为两个子问题进行求解能够更加节省求解时间。3.查找中位数程序代码1. #include "stdafx.h"  2. #include 

4、<ctime>  3. #include <iostream>   4. using namespace std;   5.   6. template <class Type>  7. void Swap(Type &x,Type &y);  8.   9. inline int Ra

5、ndom(int x, int y);  10.   11. template <class Type>  12. void BubbleSort(Type a,int p,int r);  13.   14. template <class Type>  15. int Partition(Type a,int 

6、p,int r,Type x);  16.   17. template <class Type>  18. Type Select(Type a,int p,int r,int k);  19.   20. int main()  21.   22.     /初始化数组  23. &

7、#160;   int a200;  24.   25.     /必须放在循环体外面  26.     srand(unsigned)time(0);  27.   28.     for(int i=0; i<200; i+)  29.    

8、60;  30.         ai = Random(0,500);  31.         cout<<"a"<<i<<":"<<ai<<" "  32.      

9、60;33.     cout<<endl;  34.   35.     cout<<"第100小的元素是"<<Select(a,0,199,100)<<endl;  36.   37.     /重新排序，对比结果  38.     BubbleSort(a,0,19

10、9);  39.   40.     for(int i=0; i<200; i+)  41.       42.         cout<<"a"<<i<<":"<<ai<<" " 

11、; 43.       44.     cout<<endl;  45.   46.   47. template <class Type>  48. void Swap(Type &x,Type &y)  49.   50.     Ty

12、pe temp = x;  51.     x = y;  52.     y = temp;  53.   54.   55. inline int Random(int x, int y)  56.   57.    

13、0; int ran_num = rand() % (y - x) + x;  58.      return ran_num;  59.   60.   61. /冒泡排序  62. template <class Type>  63. void BubbleSort(Typ

14、e a,int p,int r)  64.   65.      /记录一次遍历中是否有元素的交换     66.      bool exchange;    67.      for(int i=p; i<=r-1;i+)  &#

15、160; 68.          69.         exchange = false     70.         for(int j=i+1; j<=r; j+)    71. &#

16、160;           72.             if(aj<aj-1)    73.                 74.   

17、              Swap(aj,aj-1);   75.                 exchange = true;    76.      

18、            77.              78.         /如果这次遍历没有元素的交换,那么排序结束     79.       

19、60; if(false = exchange)    80.           81.              break     82.         

20、0; 83.        84.   85.   86. template <class Type>  87. int Partition(Type a,int p,int r,Type x)  88.   89.     int i = p-1,j =&

21、#160;r + 1;  90.   91.     while(true)  92.       93.         while(a+i<x && i<r);  94.         

22、while(a-j>x);  95.         if(i>=j)  96.           97.             break;  98.       

23、;    99.         Swap(ai,aj);  100.          101.     return j;  102.   103.   104.   105. template <class 

24、Type>  106. Type Select(Type a,int p,int r,int k)  107.   108.     if(r-p<75)  109.       110.         BubbleSort(a,p,r);  111. &

25、#160;       return ap+k-1;  112.       113.     /(r-p-4)/5相当于n-5  114.     for(int i=0; i<=(r-p-4)/5; i+)  115.      

26、 116.         /将元素每5个分成一组，分别排序，并将该组中位数与ap+i交换位置  117.         /使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数  118.         BubbleSort(a,p+5*i,p+5*i+4);  119.         Swap(ap+5*i+2,ap+i);  120.       121.     /找中位数的中位数  122.     Type x = Select(a