算法实验报告-分治法性能分析

1、分治法算法分析作业吴迪2011-3-29本次是第一次算法作业，该部分内容包含3个题目的程序代码，分析文档，说明图片等内容目录引言1算法性能比较1.1问题分析1.2源程序代码1.3运行示例1.4数据分析（单次录入数据具有较大随机误差，只看增长趋势）2循环赛问题2.1问题描述2.2问题分析2.3源程序2.4运行示例3最大最小值问题 3.1问题描述与分析3.2源程序3.3运行示例999101112121314引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 易直接求解，解题所需的计算时间也越少。 计思想是，将一个难以直接解决的大问题，分而治之。但是不是所有问题都适合用分治法解决。 大

2、的问题时，使用蛮力策略效率一般得不到保证。别求解合并能有效提高计算效率。问题的规模越小，越容 设 以便各个击破， n且取值又相当 k个子问题分分治法是计算机科学中经常使用的一种算法。 分割成一些规模较小的相同问题， 当求解一个输入规模为 因此分治策略将问题划分成1算法性能比较1.1问题分析比较插入排序，合并排序和快速排序性能。 算法性能比较通常是从时间复杂度的角度进行的。数和元素交换或移动次数有关。因而在不同大小规模的问题中通过统计这两者之和来评判算 法的优劣。同时也可以证明各种算法的时间复杂度与问题规模排序算法的复杂度主要和算法中的比较次n之间的关系。特别说明：本程序中考虑到不同规模的乱序数

3、据输入过程比较复杂，编写了一个规模 整型数据随机排列函数，能够直接生成指定大小的1-n无序整数列。1.2源程序代码2011 年 3 月 19 日 0:20:02 /mai n test.c pp for test#in clude<iostream>#in clude<time.h>using n ames pace std;/全局标记比较次数和移动次数int coun t_co mp are=0;int count_move = 0;in t cou nt_all()return coun t_co mp are+co unt_move;void clear_co u

4、n t()coun t_co mp are=0;count_move = 0;/i nsert sort void in sert_eleme nt(i nt a,i nt size,i nt eleme nt) /size before in serti on int i=0;for(i=size-1;i>=0;i-) coun t_co mp are+;if(eleme nt<ai) ai+1=ai;co unt_m ove+; else break;ai+1=eleme nt;coun t_move+;void In sertSort(i nt a,i nt size)for

5、(i nt i=1;i<size;i+)in sert_eleme nt(a,i,ai);/merge sortvoid Merge(i nt c,i nt d, int l, i nt m, int r) int i = l, j = m+1, k = l;while(i <= m && j <= r)coun t_co mp are+; if(ci <= cj) dk+=ci+; coun t_move+;else dk+=cj+;co un t_move+;coun t_co mp are+; if(i > m)for(i nt q = j;

6、 q <= r; q +) dk+ = cq; count_m ove+;elsefor(i nt q = i; q <= m; q +)dk+ = cq;coun t_move+;void Co py(i nt a,i nt b,i nt l,i nt r)for(i nt i=l;i<=r;i+)ai=bi;coun t_move+;void MergeSort(i nt a,i nt left,i nt right, int size)if(left < right)coun t_co mp are+;int i = (right + left)/ 2;int p

7、=size; /this is imp orta nt,m ind the value!int *b=new in t p;MergeSort(a, left, i,size);MergeSort(a, i+1, right,size);Merge(a, b, left, i, right);Cop y(a,b,left,right);/quick sortvoid s a,i nt i,i nt j)int temp=ai;ai=aj;aj=te mp;count_m ove+=3;int p artiti on (i nt a,i nt p ,i nt r)int i=p,j=r+1;in

8、t x=a p;while(true)while(a+i<x&&i<r)coun t_co mp are+;while(a-j>x)coun t_co mp are+;coun t_co mp are+;if(i>=j) break;s);ap =aj;aj = x;count_m ove+; return j;void QuickSort(i nt a,i nt p ,int r)if (p < r)int q= p artiti on(a, p , r);QuickSort(a, p,q-1);QuickSort(a,q+1,r);coun t

9、_co mp are+;/showvoid show_array(int a,int size)/ 显示一个数组的所有元素for(i nt i=0;i<size;i+)cout << ai << ""cout << en dl;/ran dom arrayvoid RandomArray(int a,int size) /随机生成数组含 n个元素，其元素各不相同 sran d(time(NULL);for(i nt i=0;i<size;i+) ai=0;for(i nt i=1;i<=size;i+)int p=ran

10、 d()%size;while(a p !=0)p=(+p)%size;ap =i； show_array(a,size);/copy arrayvoid Copy Array(i nt a,i nt b,i nt size) for(i nt i=0;i<size;i+) bi=ai;int mai n()in t*a;i nt *temp_a;int size=4;cin> >size; a=new in t size; temp_a = new in t size;Ran domArray(te mp _a,size); Copy Array(te mp _a,a,si

11、ze); show_array(a,size);In sertSort(a,size); show_array(a,size);cout << "插入排序比较次数为 cout << "插入排序移动次数为"<< coun t_co mpare << en dl;"<< count_move << en dl;cout << "总规模为"<< count_all() << endl; clear_co un t();Copy Arr

12、ay(te mp _a,a,size); show_array(a,size); MergeSort(a,0,size-1,size); show_array(a,size);cout << "合并排序比较次数为 cout << "合并排序移动次数为"<< coun t_co mpare << en dl;"<< count_move << en dl;cout << "总规模为"<< count_all() << endl;

13、clear_co un t();Copy Array(te mp _a,a,size); show_array(a,size); QuickSort(a,0,size-1); show_array(a,size);cout << "快速排序比较次数为 cout << "快速排序移动次数为"<< coun t_co mpare << en dl;"<< count_move << en dl;cout << "总规模为"<< count_al

14、l() << endl; show_array(a,size);system(" pause"); return 0;1.3运行示例霁避冋题的规5453769 10 251插人排序后该序列为：123456789 10活入bff比枚次数为2?涵入4序務动次数湖0总规SS7合并排序后该序列为：123 45678? 10 合荊琏比技次数为3?暂;黯移动次数为快速J1E序后该序列为：123456789 10 吏速b庄比R次数为砧 齧萼藝移动次薮血合合总Jv+l 已士丄-金CCCCIIr丿 J kLj*LA.TvJt/.Z； J-t-u t 1 序移动次数为呂?16627

15、请按任意犍继续.-1.4数据分析（单次录入数据具有较大随机误差，只看增长趋势）问题规模（n）排序总复杂度规模（T（ n）插入排序合并排序快速排序105710550202212801223036746123840946660371586106422447507368130917003125489根据列表分析，插入算法平均复杂度为0 站,合并算法平均复杂度为|f）（nlogi门|,快速排序算法平均复杂度为I51隅11） I，但是排序算法最坏情况下复杂度仍为m（），为了验证这一点，取n=1000的已排好数组，快排总规模变为503497，取n=10000的已排好数组,快排总规模变为50034997。说

16、明快排算法对已经基本排好的数组反而耗时间更多。2循环赛问题2.1问题描述设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程表: 每个选手必须与其他 n-1个选手各赛一次；每个选手一天只能赛一次；当n是偶数时，循环赛进行 n-1天。n天。当n是奇数时，循环赛进行2.2问题分析当n= （ k=1、2、3、4,n=2、4、8、16,）时，此时问题比较简单。按照分治的 策略，可将所有参赛的选手分为两部分，n =个选手的比赛日程表就可以通过为n/2=个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。再逐步合

17、并子问题的解即可得到原问题的解。推广当n为任意整数时：当n小于或等于1时，没有比赛。n-1轮比赛.n轮比赛，这时每轮将会有一支球队轮空。当n是偶数时，至少举行 当n是奇数时,至少举行 因此应对策略如下：n=情形类似，可用分治法求解。（1）当n/2为偶数时，与n/2轮比赛中让轮(2)当n/2为奇数时，递归返回的轮空的比赛要作进一步处理。可以在前 空选手与下一个未参赛选手进行比赛。2.3源程序#in clude<iostream>using n ames pace std;int a100100;int b100;bool odd(int n)/ 判断 n 奇偶性return n&am

18、p;1;/n为奇数，返回1，n为偶数，返回0/ n/ 2为奇数时的合并算法void copy odd(i nt n)int m=n /2;for(i nt i=0;i<m;i+)bi=m+i;bm+i=bi;for(i nt i=0;i<m;i+)/由左上角小块的值算出相应的左下角小块的值for(i nt j=0;j<m+1;j+)if(aij>=m)aij=bi; am+ij=(bi+m)% n;else am+ij=aij+m; /由左上角小块的值算出相应的右上角和右下角小块的值for(i nt j=1;j<m;j+)aim+j=bi+j;abi+jm+j=i

19、;void cop y(i nt n)int m=n /2;for(i nt i=0;i<m;i+) for(i nt j=0;j<m;j+) /由左上角小块的值算出对应的右上角小块的值 aij+m=aij+m;/由右上角小块的值算出对应的左下角小块的值 ai+mj=aij+m;/由左上角小块的值算出对应的右下角小块的值 ai+mj+m=aij;/合并算法llnl 2为奇数时void makec op y(i nt n)if(n/2)>1 &&odd(nl 2) copyodd(n); else copy(n);void tour na(i nt n)if(n

20、=1)a00=0;return; if(odd( n) )to urna(n+1);retur n; tourna( nl 2);makec opy(n);int mai n()int n;cout << "请输入参数队数:"<<endl; cin>>n;/改进的分治赛算法lln为奇数，分治lln为偶数，分治ll合并tourna( n);cout << "参数日程表为:"<<endl; for(i nt i=0;i< n;i+)for(i nt j=0;j< n;j+)cout &l

21、t;< aij << ""cout << en dl;system(" pause");return 0;2.4运行示例请输入参数队数匕7参数日程表为：&74523a0123456Q33547239163 42 51 60 77 0547610312移数日程表为=i7 6 10 8 il 9 3 11no1-L0 911-7 11 6 8当n是2的幕时，即对于某个正整数k,n空k,有1011 6 a 7 3 47 11 5 8 4 39 18 7 & 5 2910 911 8洁按任恿犍继续-3最大最小值问题3

22、.1问题描述与分析在含有n个不同元素的集合中同时找出它的最大和最小元素算法思想：先相邻两个两个比较，较大的放入数组 max,较小的放入数组 min,然后从max 数组求出最大，min数组求出最小即可。从算法描述中可以看出， 占据算法的主要执行次数的是比较过程，因此算法的复杂性主要跟比较次数相关TCn) =,TCIn/2ll) + Tan/21) + 2T(n )=2T( n/2)+2 =2(2T( n/4)+2)+2=2*2T( n/4)+2*2+2=*巴2*2=3n/2-2这是最优情况，平均则比直接比较少25%3.2源程序/find max and min #in clude <iostream>using n ames pace std;void Max_Mi n(int a,i nt n)int m = (n+1)/2;int maxm;int mi n m;int k = 0, j = 0;if(n/2 != 0) maxm-1 = min m-1 = a n-1;for (int i=0; i < n-1; i = i+2)if (ai >= ai+1)maxj+ = ai; min k+ = ai+1; elsemaxj+ = ai