程序设计综合实践-算法和算法分析

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,算法和算法分析,“算法+数据结构=程序”,算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。,算法具有下列5个重要特性：,输入：描述问题的数据，作为算法的输入。,输出：算法执行后产生的输出结果，代表问题答案。,确定性：算法的每一个步骤都必须有明确的语义，无二义性。,有限性：算法的每一条执行路径都必须能够在有限的步骤之内完成，而且在可预期和可接受的时间内。,可行性：算法描述中的每一个操作都是可以通过有限次可以实现的基本运算来完成的。,1,算法描述,算法不局限于具体的程序设计语言，它强调的是计算机解决问题的思想方法、步骤，用某种方法来描述，用于人们之间的交流。,自然语言,程序流程图,伪代码描述,我们主要采用类,C,语言描述,2,例1.6 插入排序算法,/插入排序算法，完成n个元素数组的递增排序,1 void InsertSort(ElemType A,int n),2 for(i=1;i=0&x Aj),6 A j+1=A j;,7 -j;,8 ,9 A j+1=x;,10 ,11 ,3

2、,2.,1算法的性能分析与度量,一个问题可以有不同的算法。主要从下述方面评价算法：,基本要求：,正确性,健壮性,可读性,效率指标：,时间复杂度,空间复杂度,4,时间复杂度（time complexity）是根据算法实现的程序在计算机上执行时花费的CPU时间的度量。,空间复杂度（space complexity）是根据算法实现的程序在计算机上执行时需要使用的存储空间的度量。,对算法的性能评估，可以采用两种方法：,(1)预先评估，即根据算法描述，从理论上去计算一个算法的时间复杂度和空间复杂度，这种方法称为“性能分析”；,(2)事后测试，即用程序实现算法，利用某些工具统计程序执行的时间和空间开销，这种方法称为“性能度量”。,5,精确估算出执行实现算法的程序所需要花费的时间既很困难，也无必要,忽略算法中不同基本操作执行一次所需要花费的时间差异，只需要统计这些基本操作的执行次数之和；,对算法执行时间影响最大的，或是完成算法中核心的基本操作，是关键基本操作，只需统计关键基本操作所执行的次数，忽略对算法执行时间影响很小的操作。,基本操作执行的次数可以看作是,问题规模,n的一个函数，记作f(n)。只需

3、关注f(n)中阶数最高项，忽略项系数以及其它低阶项。,算法的时间复杂度T(n)是问题规模n的函数，记作：,T(n)=O(f(n),6,例1.6插入排序算法时间复杂度分析，关键基本操作是,元素比较和移动,：,最坏情况下，原数组内元素递减排列时，n个元素插入排序所需元素比较和移动次数都为1+2+3+.+n-1，插入排序的算法时间复杂度为 ；,在最好情况下，原数组内元素递增排列时，n个元素插入排序所需元素比较和移动次数分别为n-1和0，即最好情况下，插入排序的算法时间复杂度为O(n)；,平均情况下，假设新元素插入在每个位置的概率相同，则平均比较次数为：1+3/2+4/2+.n/2，平均移动次数为：0+1/2+2/2+.n/2，因此，平均情况下，插入排序的算法时间复杂度为 。,7,常见的算法时间复杂度有O(1)、O(log2n)、O(n)、O(n2)和O(2n)，分别称为常量阶、对数阶、线性阶、平方阶和指数阶。,表1.1 常见函数的增长率,8,n,log,2,n,n,log,2,n,n,2,2,n,1,0,0,1,2,10,3.3,33.2,100,1024,100,6.6,664.4,10000,1.27E30,1000,10.0,9.97E3,1E6,1.07E301,10000,13.3,1.33E5,1E8,inf,100000,16.6,1.66E6,1E10,inf,1000000,19.9,1.99E7,1E12,inf,算法的空间复杂度,着重考查算法所必须的附加数据存储空间大小,用,f,(n)表示，也只需关注,f,(n)中阶数最高项，忽略项系数以及其它低阶项。记作,S(n)=O(f(n),有些情况下，S(n)是常量阶的，这意味着无论问题规模n的大小如何，算法所需要的附加存储空间是固定的，对数据操作利用的是输入数据所占用的空间和少部分固定数量的临时工作空间，我们称此算法是“原地工作”。,例1.6插入排序就是“原地工作”算法。,9,

《程序设计综合实践-算法和算法分析》由会员第***分享，可在线阅读，更多相关《程序设计综合实践-算法和算法分析》请在金锄头文库上搜索。