1.2 算法和算法分析

《1.2 算法和算法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二、算法和算法分析•“算法+数据结构=程序”•算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。•算法具有下列5个重要特性：I.输入：描述问题的数据，作为算法的输入。II.输出：算法执行后产生的输出结果，代表问题答案。III.确定性：算法的每一个步骤都必须有明确的语义，无二义性。IV.有限性：算法的每一条执行路径都必须能够在有限的步骤之内完成，而且在可预期和可接受的时间内。V.可行性：算法描述中的每一个操作都是可以通过有限次可以实现的基本运算来完成的。1•算法描述算法不局限于具体的程序设计语言，它强调的是计算机解决

2、问题的思想方法、步骤，用某种方法来描述，用于人们之间的交流。I.自然语言II.程序流程图III.伪代码描述我们主要采用类C语言描述2•例1.6插入排序算法•//插入排序算法，完成n个元素数组的递增排序•1voidInsertSort(ElemTypeA[],intn)•2{for(i=1;i<n;++i){•3x=A[i];•4j=i-1;•5while(j>=0&&x<A[j]){•6A[j+1]=A[j];•7--j;•8}•9A[j+1]=x;•10}•11}3•

3、2.1算法的性能分析与度量一个问题可以有不同的算法。主要从下述方面评价算法：基本要求：I.正确性II.健壮性III.可读性效率指标：I.时间复杂度II.空间复杂度4•时间复杂度（timecomplexity）是根据算法实现的程序在计算机上执行时花费的CPU时间的度量。•空间复杂度（spacecomplexity）是根据算法实现的程序在计算机上执行时需要使用的存储空间的度量。对算法的性能评估，可以采用两种方法：(1)预先评估，即根据算法描述，从理论上去计算一个算法的时间复杂度和空间复杂度，这种方法称为“性能分析”；(2)事后测试，即用程序实现算

4、法，利用某些工具统计程序执行的时间和空间开销，这种方法称为“性能度量”。5精确估算出执行实现算法的程序所需要花费的时间既很困难，也无必要l忽略算法中不同基本操作执行一次所需要花费的时间差异，只需要统计这些基本操作的执行次数之和；l对算法执行时间影响最大的，或是完成算法中核心的基本操作，是关键基本操作，只需统计关键基本操作所执行的次数，忽略对算法执行时间影响很小的操作。基本操作执行的次数可以看作是问题规模n的一个函数，记作f(n)。只需关注f(n)中阶数最高项，忽略项系数以及其它低阶项。算法的时间复杂度T(n)是问题规模n的函数，记作：T(n)

5、=O(f(n))6例1.6插入排序算法时间复杂度分析，关键基本操作是元素比较和移动：•最坏情况下，原数组内元素递减排列时，n个元素插入排序所需元素比较和移动次数都为1+2+3+...+n-1，插入排序的算法时间复杂度为；•在最好情况下，原数组内元素递增排列