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

《算法实验报告-分治法性能分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分治法算法分析作业吴迪2011-3-29本次是第一次算法作业，该部分内容包含3个题目的程序代码，分析文档，说明图片等内容目录弓I言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引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。分治法是计算机科

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

3、间复杂度与问题规模n之间的关系。特别说明：本程序中考虑到不同规模的乱序数据输入过程比较复杂，编写了一个规模n的整型数据随机排列函数，能够直接生成指定大小的1-n无序整数列。//2011年3月19FI0:20:02//maintest.cppfortest#include#includevtime.h〉usingnamespacestd;〃全局标记比较次数和移动次数intcount_compare=0;intcount_move=0;intcount_all(){returncount_compare+count_move;}voidc

4、lear_count()count_compare=0;countmove=0:}//insertsortvoidinsert_element(inta[],intsize,intelement)//sizebeforeinsertioninti=0;for(i=size-l;i>=0;i-){count_compare++;if(element

5、r(inti=l;im){for(intq=j;q<=r;q++){d[k++]=c

6、[q];count_move++;}}elsefor(intq=i;q<=m;q++){d[k++]=c[q];count_move++;}}voidCopy(inta[],intb[]zintl,intr){for(inti=l;i<=r;i++){a[i]=b[i];count_move++;}}voidMergeSort(inta[],intleft,intright,intsize){if(left

7、dthevalue!int*b=newint[p];MergeSort(a,left,i,size);MergeSort(a,i+1,right,size);Merge(a,b,left,i,right);Copy(a,b,left,right);}}//quicksortvoidswap(inta[],inti,intj){inttemp=a[i);a[i]=a[j];a[j]=temp;count_move+=3;}intpartition(inta[],intpjntr){inti=p,j=r+l;intx=a[p];while(true){whi

8、le(a[++i]