算法設(shè)計與分析線性時間選擇

1、福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院計算機算法設(shè)計與分析上機實驗報告（1）專業(yè)和班級姓名成績學(xué)號實驗名稱線性時間選擇實驗?zāi)康暮鸵?. 理解算法設(shè)計的基本步驟和各步的主要內(nèi)容，基本要求2. 加深對遞歸設(shè)計方法基本思想的理解實驗任務(wù)1.掌握線性時間選擇的基本算法及其應(yīng)用 2. 利用線性時間選擇算法找出數(shù)組的中位數(shù)3. 分析實驗結(jié)果，總結(jié)算法的時間和空間復(fù)雜度 實驗步驟1. 線性時間選擇的思想：如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的倍(0<<1),那么就可以在最壞情況下用O(n)

2、時間完成選擇任務(wù)。例如，當(dāng)=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)。  2. 算法正確性證明  (1)將所有的數(shù)n個以每5個劃分為一組共組，將不足5個的那組忽略，然后用任意一種排序算法，因為只對5個數(shù)進行排序，所以任取一種排序法就可以了。將每組中的元素排好序再分別取每組的中位數(shù)，得到個中位數(shù)。      (2)取這個中位數(shù)的中位數(shù)，如果是偶數(shù)，就找它的2個中位數(shù)中較大的一個作為劃分基準(zhǔn)。 

3、;     (3)將全部的數(shù)劃分為兩個部分，小于基準(zhǔn)的在左邊，大于等于基準(zhǔn)的放右邊。在這種情況下找出的基準(zhǔn)x至少比個元素大。因為在每一組中有2個元素小于本組的中位數(shù)，有個小于基準(zhǔn)，中位數(shù)處于，即個中位數(shù)中又有個小于基準(zhǔn)x。因此至少有個元素小于基準(zhǔn)x。同理基準(zhǔn)x也至少比個元素小。而當(dāng)n75時n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4。通過上述說明可以證明將原問題分解為兩個子問題進行求解能夠更加節(jié)省求解時間。3.查找中位數(shù)程序代碼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.     /初始化數(shù)組  23. &

7、#160;   int a200;  24.   25.     /必須放在循環(huán)體外面  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.     /重新排序，對比結(jié)果  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.         /如果這次遍歷沒有元素的交換,那么排序結(jié)束     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相當(dāng)于n-5  114.     for(int i=0; i<=(r-p-4)/5; i+)  115.      

26、 116.         /將元素每5個分成一組，分別排序，并將該組中位數(shù)與ap+i交換位置  117.         /使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進一步查找中位數(shù)的中位數(shù)  118.         BubbleSort(a,p+5*i,p+5*i+4);  119.         Swap(ap+5*i+2,ap+i);  120.       121.     /找中位數(shù)的中位數(shù)  122.     Type x = Select(a