分治法算法实现_19845.docVIP

计算机与通信工程学院 实 验 报 告 实验项目名称 分治法算法实现 所属课程名称 算法设计与分析 实 验 类 型 验证型 实 验 日 期 2013.3.7 班 级 软件1101班 学 号 201155080120 姓 名 谭政 成 绩 一、实验概述： 【实验目的】 通过比较快速排序和归并排序法的时间复杂度， 分析算法的好坏情况。 通过该实验熟悉和掌握递归和分治策略的思想 【实验原理】 将一个难以解决的大问题分割成一个个规模较小的子问题， 解决小的问题从而化解大的问题。 【实验环境】 Win7系统， VC++6.0 二、实验内容： 【实验方案】 编写程序采用分治法算法的思想，利用递归的算法结构，层层递进。 将两种排序分别测试一定量的数据，并记录下所用的时间 【实验过程】（实验步骤、记录、数据、分析） 本实验利用系统函数计算算法运算时间，程序中采用宏定义K值来控制测试的数据量，依次改变K的大小，记录下显示的时间的变化和比较两种算法的运算的时间差异，分析数值的变化，从而来判定算法的优劣。 【实验结论（结果） 归并排序算法的计算时间：0.110 s 随机取100000个数排序，程序函数计算时间结果如下： 归并排序100000个数排序时间0.047s. 测试200000个数据，快速排序算法时间：0.062 s 测试100000个数据，运行时间0.031； 从以上可以得出，在同样多的数据量情况下，快速排序明显要快于归并排序。 【实验小结结论 1．实验名称实验目的目的要明确，要抓住重点， 4．实验环境实验用的软硬件环境。实验（步骤和方法）这是实验报告极其重要的内容。写明依据何种原理、操作方法进行实验，要写明经过哪个步骤。还应该画出流程图再配以相应的文字说明。 6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。 7．实验结论（结果）根据实验过程中得的，出结论。 小结本次实验体会、思考和建议。　 4