《算法和算法分析》PPT课件.ppt

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

1、第1章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4算法和算法分析1.4.1算法一、算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。二、算法的5个重要特性：有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义，不存在二义性。且对于相同的输入只能得出相同的输出。1.4算法和算法分析可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执

2、行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4算法和算法分析1.4.2算法设计的要求正确性：算法应满足具体问题的需求。a）程序不含语法错误；b）程序对于一般输入数据的正确性；c）程序对于苛刻、刁难输入数据的正确性；d）程序对于一切合法输入数据的正确性。可读性：算法应该好读。以有利于人对程序的理解。1.4算法和算法分析健壮性：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率：算

3、法执行时间。存储量需求：算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4算法和算法分析1.4.3算法效率的度量一、算法执行时间的度量方法：1）事后统计的方法：收集此算法的执行时间和实际占用空间的统计资料。缺陷：a）必须先运行依据算法编制的程序；b）依赖于计算机的硬件、软件等环境因素。1.4算法和算法分析2）事前分析估算的方法：求出该算法的一个时间界限函数。算法运行所消耗的时间取决于：a）依据的算法选用何种策略；b）问题的规模；c）书写程序的语言；d）编译程序所产生的机器代码的质量；e）机器执行指令的速度。1

4、.4算法和算法分析二、算法的时间复杂度原操作：基本操作。算法的时间度量：原操作重复执行的次数。算法的渐近时间复杂度：原操作重复执行的次数是问题规模n的某个函数f(n)T(n)=O(f(n))频度：原操作重复执行的次数。1.4算法和算法分析常见的时间复杂度有：O(1)常量阶O(n)线性阶O(n2)平方阶O(n3)立方阶O(logn)对数阶O(2n)指数阶六种常用计算算法时间的多项式的关系为：O(1)

5、将++x看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)，即常量阶。例2for(i=1;i<=n;++i){++x;s+=x;}将++x看成是基本操作，语句频度为n，其时间复杂度为为O(n)，即时间复杂度为线性阶。1.4算法和算法分析例3for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}将++x看成是基本操作，语句频度为n2，其时间复杂度为O(n2)，即时间复杂度为平方阶。1.4算法和算法分析在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率或阶即可。例4for(i=2;

6、i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}将++x看成是基本操作，语句频度为(n-1)(n-1)/2，其时间复杂度可近似为O(n2)，即它关于n的增长率或阶。1.4算法和算法分析当基本操作执行次数随问题的输入数据集变化时，计算平均时间复杂度或最坏情况下的上界。例5起泡排序算法voidbubble_sort(inta[],intn){for(i=n-1,change=TRUE;i>=1&&change;--i){change=FALSE;for(j=0;ja

7、[j+1]){a[j]↔a[j+1];change=TRUE;}}}//bubble_sort1.4算法和算法分析分析：当a中初始序列为自小至大有序，基本操作的执行次数是0；当a中初始序列为自大至小有序，基本操作的执行次数是n(n-1)/2；分析最坏情况以估算算法执行时间的一个上界，即O(n2)。1.4算法和算法分析图1.7常见函数的增长率1.4算法和算法分析一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法，而避免使用指数阶的算法。1.4算法和算法分析1.4.4算法的存储空间

8、需求一、空间复杂度：所需存储空间是问题规模n的某个函数f(n)S(n)=O(f(n))二、算法执行过程中所需的最大空间估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间。本章内容复习有关数据结构的基本概念和术语抽象数据类型ADT的表示与实现