云南大学信息学院计算机科学与技术专业本科《算法设计与分析》专业：计算机科学与技术教师：岳昆老师姓名：**学号：***********2014年12月26 日1实验一算法计算时间复杂度和增长率 (4)1、实验目的 (4)2、基本思想 (4)3、设计与实现的关键技术和主要方法 (4)4、实验环境 (4)5、实验结果与结论 (4)5.1实验结果： (4)5.2结论： (5)实验二搜索算法的实现，时间复杂度分析与测试 (6)1、实验目的 (6)2、基本思想 (6)3、设计与实现的关键技术和主要方法 (6)4、实验环境 (6)5、实验结果与结论 (6)5.1实验结果 (6)5.2结论 (8)实验三分治算法的递归程序实现与时间复杂度测试 (9)1、实验目的 (9)2、基本思想 (9)3、设计与实现的关键技术和主要方法 (9)4、实验环境 (9)5、实验结果与结论 (9)5.1实验结果： (9)5.2结论 (10)实验四动态规划算法的实现与时间复杂度测试 (11)1、实验目的 (11)2、基本思想 (11)3、设计与实现的关键技术和主要方法 (11)4、实验环境 (11)5、实验结果与结论 (11)5.1实验结果： (11)5.2结论 (12)实验五动态规划算法的适应性测试 (12)1、实验目的 (13)2、基本思想 (13)3、设计与实现的关键技术和主要方法 (13)4、实验环境 (13)5、实验结果与结论 (13)5.1实验结果 (13)5.2结论 (14)实验六贪心算法的实现与时间复杂度测试 (14)1、实验目的 (15)2、基本思想 (15)23、设计与实现的关键技术和主要方法 (15)4、实验环境 (15)5、实验结果与结论 (15)5.1实验结果 (15)5.2结论 (16)附录： (17)1.公用数据类（Value.java） (17)2.背包类（Knapsack.java） (17)3.随机数工具类（RandomUtils.java） (18)4. 冒泡算法(BubbleSort.java) (19)5. 归并排序(MergeSort .java) (20)6. 折半查找（BinarySearch.java） (22)7. 线性查找（SequentialSearch.java） (23)8. 快速排序（QuickSort.java） (24)9. 0-1背包问题(KnapsackDP.java) (26)10. Fibonacci数列按递归和动态规划解决(Fibonacci .java) (27)11. 贪心算法背包问题(KnapsackGreedy.java) (29)3实验一算法计算时间复杂度和增长率1、实验目的通过算法的程序实现和执行时间测试、并与理论上的结论进行对比分析，深入理解算法时间复杂度分析中对于输入数据考虑其等价类的意义，理解算法时间复杂度渐进性态和和增长率的概念，为后续学习和实验奠定基础，同时也学习程序效率测试的基本思路。
2、基本思想(1) 算法的计算时间取决于算法中某些操作的执行次数，这些操作是算法时间复杂度分析的依据。
(2) 增长率反映了算法的计算时间复杂度，即随着算法输入规模的增加、算法计算时间增加的趋势。
(3) 算法的计算时间复杂度针对输入数据的等价类来分析或测试。
3、设计与实现的关键技术和主要方法（1）生成随机数（2）实现冒泡排序和归并排序（3）记录比较次数，根据作图分析4、实验环境硬件：处理器Intel Core i5,2.5GHz; RAM 4G软件：windows7，jdk1.6 ，origin8.05、实验结果与结论5.1实验结果：4表3：归并排序测试数据10 100 1000 2000 5000 10000 100000 实验数据个数（个）23 541 8719 19412 552281204971536591比较操作次数（次）图1：冒泡排序与归并排序比较5.2结论：1）由表1可得，对于冒泡算法在相同的输入规模下，由于输入数据之间的差异，可能会对比较的次数的大小造成一定的影响，这是由于对算法进行优化的缘故，对于已有序的数列不进行重复排序。
但是对比较次数的数量级没有影响。
2）冒泡排序的时间复杂度按理论上进行分析为O(n2)，归并排序的时间复杂度为O(nlog(n))。
通过实验中分析比较次数又图1中可以看到，对于输入规模的增大，冒泡排序比较次数的增长率始终大于归并排序。
故而，通过本次试验可以证明归并排序的时间效率优于冒泡排序。
5实验二搜索算法的实现，时间复杂度分析与测试1、实验目的编程实现顺序搜索和二分搜索算法，理解算法设计的基本思想。
通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。
2、基本思想搜索（或称查找）是在大量信息中寻找一个特定的信息元素，是计算机应用中常用的基本运算。
以顺序搜索和二分搜索算法为代表，测试、验证搜索算法的计算时间复杂度。
3、设计与实现的关键技术和主要方法（1）生成随机数（2）实现顺序搜索和二分搜索（3）记录比较次数，根据作图分析4、实验环境硬件：处理器Intel Core i5,2.5GHz; RAM 4G软件：windows7，jdk1.6 ，origin8.05、实验结果与结论5.1实验结果：6表3：含预处理二分搜索测试数据实验数10 100 1000 2000 5000 10000 100000 据个数（个）49 4822 4989541995696 1249184649980142704971552比较操作次数（次）图1：不含预处理图2：包含预处理78 5.2结论：1）由于实验中需要进行搜索的目标数由电脑随机生成，所以搜索失败（搜索目标不存在）的概率很大。
对于表1中即可看出，对于搜索均失败的情况下，线性搜索进行比较次数的数量级与输入的数量级O (n)相等。
2）进行二分搜索的前提是有序数列。
如果应用二分法对有序数列中目标数的搜索时，由表2可以看出比较的次数远远小于输入的数量级。
因此，对于有序数列进行二分搜索效率很高，与理论上O(log(n))大致接近。
3）对于无序数列进行二分搜索，需要首先进行数列的预处理，即通过排序算法（本实验采用冒泡算法）对数列进行排序。
由于排序算法的性能不同，对首次进行搜索的效率有影响。
如图2所示，对于冒泡排序处理之后的数列运行二分搜索首次搜索的效率小于线性搜索。
但之后再进行搜索，由于数列已经有序，如图1，二分搜索的效率又高于线性搜索。
4）所以，综合进行分析，如果需要对数列进行多次搜索，先采用某一排序算法进行排序后，采用二分搜索的效率高于线性搜索。
反之，采用线性搜索。
附：采用归并排序后二分搜索与线性搜索比较（包含预处理）10100100010000100000101001000100001000001000000比较次数 (次)输入个数 (个)如附图1所示，通过归并排序处理后的数列进行二分搜索，在首次进行搜索时，比较的次数与理论上的搜索效率为O （nlog(n)）大致吻合。
实验三分治算法的递归程序实现与时间复杂度测试1、实验目的编程实现合并排序和快速排序算法，理解分治算法设计的基本思想、递归程序实现的基本方法，加深对分治算法设计与分析思想的理解。
通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。
2、基本思想分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。
求出子问题的解，就可得到原问题的解。
3、设计与实现的关键技术和主要方法（1）生成随机数（2）实现快速排序和归并排序（3）记录比较次数，根据作图分析（4）对比随着测试数据增加算法增长率变化趋势（5）测试、验证、对比算法的时间复杂度。
4、实验环境硬件：处理器Intel Core i5,2.5GHz; RAM 4G软件：windows7，jdk1.6 ，origin8.05、实验结果与结论5.1实验结果：9图1：快速排序与归并排序5.2结论：1）归并排序的思想是将一个数列一分为二，然后继续细分，直到剩下两个元素时进行归并，直到最终能够完全有序。
遵循分治的思想，将大问题细分为小问题，再逐一解决，最终合并。
如表1所示，归并排序比较次数吻合理论上O(nlog(n))，并且由合并的过程可以得出该排序是一个稳定的排序。
2）快速排序的思想是找到一个枢纽点，将比枢纽点大的放到右边，小的放到左边，然后再对左右两边采取找枢纽点的方式进行进一步细分，直到完全有序。
比较的次数如表2所示，通过枢纽点划分的过程可以看出，在算法中需要进行大量的两个数交换，可能导致相同的数也进行了交换。
因此，快速排序不是一个稳定的算法，时间效率与理论上O(log(n))大致吻合。
3）归并排序对有序数列效果很好，对无序数列的排序最差情况下也可以达到O(nlog(n))。
但对于快速排序，如果是有序数列的话，根据枢纽点的划分可以得出时间复杂度达到O(n2)。
因此对于快速排序的改进，就是采用合适的方法（本次试验采用随机下标）找到尽可能靠近中位数的枢纽点，达到最佳的排序效率。
但是，快速排序对于无序数列的排序效率很高。
10实验四动态规划算法的实现与时间复杂度测试1、实验目的编程实现经典的动态规划算法，理解动态规划算法设计的基本思想、程序实现的相关技巧，加深对动态规划算法设计与分析思想的理解。
通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。
2、基本思想动态规划是一种在数学和计算机科学中使用的、用于求解包含重叠子问题的最优化问题的有效方法。
其基本思想是：将原问题分解为相似的子问题，在求解的过程中通过子问题的解描述并求出原问题的解。
动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域，在查找有很多重叠子问题的情况的最优解时有效。
它将问题重新组合成子问题，为了避免多次解决这些子问题，它们的结果都逐渐被计算并保存，从小规模的子问题直到整个问题都被解决。
因此，动态规划对每一子问题只做一次计算，具有较高的效率。
3、设计与实现的关键技术和主要方法（1）生成随机背包（2）实现0-1背包（3）根据问题规模增大记录执行时间（4）作图分析4、实验环境硬件：处理器Intel Core i5,2.5GHz; RAM 4G软件：windows7，jdk1.6 ，origin8.05、实验结果与结论5.1实验结果：图1：动态规划0-1背包5.2结论：1）0-1背包问题采用动态规划的思想进行解决，通过对二维数组的填充可以动态的求取最佳的解决方案。
这里的二维数组，横向表示背包的容量，纵向表示背包的个数。
2）在本次实验中二维数组横向采用的增量为1，要填充完整个二维数组，二维数组的大小为n*C（n表示背包个数，C表示背包容量），如图1所示，随背包个数和背包容量的增加，运行时间也相应增加。