分治法算法分析作业吴迪2011-3-29本次是第一次算法作业，该部分容包含 3个题目的程序代码，分析文档，说明图片等容目录引言 31算法性能比较 31.1问题分析 31.2源程序代码 31.3运行示例 81.4数据分析 8（单次录入数据具有较大随机误差，只看增长趋势） 82循环赛问题 92.1问题描述 92.2问题分析 92.3源程序 102.4运行示例 113最大最小值问题 123.1问题描述与分析 123.2源程序 133.3运行示例 14引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。 分治法是计算机科学中经常使用的一种算法。设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破，分而治之。但是不是所有问题都适合用分治法解决。当求解一个输入规模为 n且取值又相当大的问题时，使用蛮力策略效率一般得不到保证。因此分治策略将问题划分成 k个子问题分别求解合并能有效提高计算效率。1算法性能比较1.1问题分析比较插入排序，合并排序和快速排序性能。算法性能比较通常是从时间复杂度的角度进行的。排序算法的复杂度主要和算法中的比较次数和元素交换或移动次数有关。因而在不同大小规模的问题过统计这两者之和来评判算法的优劣。同时也可以证明各种算法的时间复杂度与问题规模n之间的关系。特别说明：本程序中考虑到不同规模的乱序数据输入过程比较复杂，编写了一个规模n的整型数据随机排列函数，能够直接生成指定大小的1-n无序整数列。1.2源程序代码2011 年 3 月 19 日 0:20:02mai n test.cpp for test#in clude#in clude using n amespace std;/全局标记比较次数和移动次数int coun t_compare=0;int count_move = 0;in t cou nt_all()retur n coun t_compare+co unt_move;void clear_co un t()coun t_compare=0;count_move = 0;i nsert sortvoid 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_compare+;if(eleme ntai) ai+1=ai;co unt_m ove+;else break;ai+1=eleme nt;count_m ove+;void In sertSort(i nt a,i nt size)for(i nt i=1;isize;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_compare+;if(ci m)for(i nt q = j; q = r; q +)dk+ = cq;count_m ove+;elsefor(i nt q = i; q = m; q +)dk+ = cq;count_m ove+;void Copy(int a,int b,int l,int r)for(int i=l;i=r;i+)ai=bi;count_m ove+;void MergeSort(int a,int left,int right,int size)if(left right)coun t_compare+;int i = (right + left)/2;int p=size; /this is important,mind the value! int *b=new in tp;MergeSort(a, left, i,size);MergeSort(a, i+1, right,size);Merge(a, b, left, i, right);Copy(a,b,left,right);/quick sortvoid swap(i nt a,i nt i,i nt j)int temp=ai;ai=aj;aj=temp;count_m ove+=3;int partiti on (i nt a,i nt p,i nt r)int i=p,j=r+1;int x=ap;while(true)while(a+ix&ix) coun t_compare+;coun t_compare+;if(i=j) break;swap(a,i,j);ap =aj;aj = x;count_m ove+;return j;void QuickSort(int a,int p ,int r)if (P r)int q= partiti on(a, p , r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);coun t_compare+;/show显示一个数组的所有元素随机生成数组含n个元素，其元素各不相同void show_array(i nt a,i nt size) /for(i nt i=0;isize;i+)cout ai ;cout en dl;/ran dom arrayvoid Ran domArray(i nt a,i nt size) /sran d(time(NULL);for(i nt i=0;isize;i+) ai=0;for(i nt i=1;i=size;i+)int p=ra nd()%size;while(ap!=0) p=(+p)%size; ap=i;show_array(a,size);/copy arrayvoid CopyArray(i nt a,i nt b,i nt size) for(i nt i=0;i size;a=new in t size;temp_a = new in t size;Ran domArray(temp_a,size);CopyArray(temp_a,a,size);show_array(a,size);In sertSort(a,size);show_array(a,size);cout 插入排序比较次数为 coun t_compare endl;cout 插入排序移动次数为 coun t_move endl;cout 总规模为 count_all() endl;clear_co un t();CopyArray(temp_a,a,size);show_array(a,size);MergeSort(a,0,size-1,size);show_array(a,size);cout 合并排序比较次数为 coun t_compare endl;cout 合并排序移动次数为 coun t_move endl;cout 总规模为 count_all() endl;clear_co un t();CopyArray(temp_a,a,size);show_array(a,size);QuickSort(a,0,size-1);show_array(a,size);cout 快速排序比较次数为 coun t_compare endl;cout 快速排序移动次数为 coun t_move endl;cout 总规模为 count_all() endl; show_array(a,size);system(pause);return 0;1.3运行示例蒙序问题的规模旅佃14 53769 10 281插人擀序后该序列为匕123456789 1 肪入排庄城次数为阳 后入啡序移动次数为初 总规57合并排序后该序列为:：12345678? 10 帶库匕就 次数为37 耀J捋窈茨数为砸 =71105快速:排序后该序列为： 1234S6789 1fel 怵速排序I：审次数为砧 毎速;蜕移动次教为15- V - J- - r人入规逝话总1.4数据分析（单次录入数据具有较大随机误差，只看增长趋势）问题规模（n）排序总复杂度规模（T（ n）插入排序合并排序快速排序10571055020221280122303674612384094666037150139487943280326115708561004694206410642002291247182447500130133136687368100050425430309170031000043898103401968225489根据列表分析，插入算法平均复杂度为区,合并算法平均复杂度为 厂m谜/町，快速排序算法平均复杂度为Q ;伽砒,但是排序算法最坏情况下复杂度仍为匸园I,为了验证这一点，取 n=1000的已排好数组，快排总规模变为503497，取n=10000的已排好数组，快排总规模变为 50034997。说明快排算法对已经基本排好的数组反而耗时间更多。2循环赛问题2.1问题描述设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程