第2章递归与分治策略实验指导

《第2章递归与分治策略实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第2章递归与分治策略实验2分治算法的递归程序实现与时间复杂度测试1.实验目的编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的吋间复杂度结论进行对比、分析和验证。2.原理解析■分治算法的基本思想分治算法的基木思想是将一个规模为n的问题分解为k个规模较小的子问题，这些了问题和互独立且与原问题性质和同。求出了问题的解，就可得到原问题的解。分治算法设计的一般步骤包扌4(1)分解，将要解决的问题划分成若干规模较小的同类问题；(2

2、)求解，当子问题划分得足够小时，用较简单的方法解决；(3)合并，按原问题的耍求，将子问题的解逐层合并构成原问题的解。分治法的基本设计范式如下：DivideAndConquer(dan,solution)if(n^SizeLimit)thenDirectSolution(datA,n,solution)elseDividelnput(datA,n,smallerSets,smallerSizes,numberSmaIler)fori=ltonumberSmaIlerdoDivideAndConquer(smallerSets[i

3、]zsmallerSizes[i],smallerSolution[i])endforCombineSolutions(smallerSolution,nurnberSmaller,solution)endif■测试算法不同问题的分治算法在分解与合并步骤可能有所不同，例如合并排序和快速排序这两个有代表性的分治算法中，合并排序算法没有分解、只有合并，快速排序算法没有合并、只冇分解;这两个算法的计算时间分别取决于合并与分解步骤。这两个算法分别如1>MergeSort(list,first,last)iffirslastthenmi

4、ddle=(first)/2MergeSort(list,firsmiddle)MergeSort(list,middle+1flast)MergeLists(list,first,middle,middle+1zlast)endifMergeLists(list,startl,endl,start2zend2)while(startl^endl)and(start2^end2)doiflist[start1]

5、elseresult[indexC]=list[start2]start2=start2+lendifindexC=indexC+lendwhileifstartlWendlthenfori=startltoendldoresult[indexC]=list[i]indexC=indexC+lendforelsefori=stoend2doresult[indexC]=list[i]indexC=indexC+lendforindexC=lfori=finalStarttofinalEnddolist[i]=result[in

6、dexC]indexC=indexC+lendfor2、Quicksort(list,first,last)iffirslastthenpivot=PivotList(list,first,last)Quicksort(list,firsttpivot-l)Quicksort(list,pivot+1zlast)endifPivotList(list,first,last)PivotValue=list[first]PivotPoint=firstforindex=first+1tolastdoiflist[index]

7、votValuethenPivotPoint=PivotPoint+1Swap(list[PivotPoint],list[index])endifendforSwap(list[first]rlist[PivotPoint]returnPivotPoint以上两个算法具有OGlogn)的时间复杂度。3・实验内容(1)编程实现以上两个用于排序的分治算法，使用生成的随机数作为测试数据。对每个算法，记录随着测试数据增加算法基本操作执行次数，分析并以图形方式展现增长率；对于两个理论上均为最优的排序算法，对比随着测试数拯增加算法增长率

8、变化趋势；测试、验证、对比算法的时间复杂度。4.实验步骤和要求(1)“比较”是以上两个排序算法的基本操作，在算法中设置比较操作执行的全局计数器，编程实现算法(输出最终的计数值)。设置记录每次递归调用时描述问题规模的变量，程序结束时输出其值。通过测试保证程序正确无误。注意递归程