算法和算法分析.ppt
第1章 绪论,1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析,1.4 算法和算法分析,算法一、算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。二、算法的5个重要特性：有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间 内完成。确定性：算法中每一条指令必须有确切的含义，不 存在二义性。且对于相同的输入只能得出相同的输 出。,1.4 算法和算法分析,可行性：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,1.4 算法和算法分析,算法设计的要求正确性：算法应满足具体问题的需求。a）程序不含语法错误；b）程序对于一般输入数据的正确性；c）程序对于苛刻、刁难输入数据的正确性；d）程序对于一切合法输入数据的正确性。可读性：算法应该好读。以有利于人对程序的理解。,1.4 算法和算法分析,健壮性：算法应具有容错处理。当输入非 法数据时，算法应对其作出反应，而不是 产生莫名其妙的输出结果。效率：算法执行时间。存储量需求：算法执行过程中所需要的最 大存储空间。一般，这两者与问题的规模有关。,1.4 算法和算法分析,算法效率的度量一、算法执行时间的度量方法：1）事后统计的方法：收集此算法的执行时间和实际占用空间的统计资料。缺陷：a）必须先运行依据算法编制的程序；b）依赖于计算机的硬件、软件等环境因素。,1.4 算法和算法分析,2）事前分析估算的方法：求出该算法的一个时 间界限函数。算法运行所消耗的时间取决于：a）依据的算法选用何种策略；b）问题的规模；c）书写程序的语言；d）编译程序所产生的机器代码的质量；e）机器执行指令的速度。,1.4 算法和算法分析,二、算法的时间复杂度原操作：基本操作。算法的时间度量：原操作重复执行的次数。算法的渐近时间复杂度：原操作重复执行的次数是问题规模n的某个函数f(n)T(n)=O(f(n)频度：原操作重复执行的次数。,1.4 算法和算法分析,常见的时间复杂度有：O(1)常量阶 O(n)线性阶 O(n2)平方阶 O(n3)立方阶 O(log n)对数阶 O(2n)指数阶六种常用计算算法时间的多项式的关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3),1.4 算法和算法分析,三、求算法时间复杂度举例例1+x;s=0;将+x看成是基本操作，则语句频度为，即时间复杂度为(1)，即常量阶。例2 for(i=1;i=n;+i)+x;s+=x;将+x看成是基本操作，语句频度为n，其时间复杂度为为O(n)，即时间复杂度为线性阶。,1.4 算法和算法分析,例3 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;将+x看成是基本操作，语句频度为n2，其时间复杂度为O(n2)，即时间复杂度为平方阶。,1.4 算法和算法分析,在难以精确计算基本操作执行次数的情况 下，只需求出它关于n的增长率或阶即可。例4 for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;aij=x;将+x看成是基本操作，语句频度为(n-1)(n-1)/2，其时间复杂度可近似为O(n2)，即它关于n的增长率或阶。,1.4 算法和算法分析,当基本操作执行次数随问题的输入数据集变化时，计算平均时间复杂度或最坏情况下的上界。例5 起泡排序算法 void bubble_sort(int a,int n)for(i=n-1,change=TRUE;i=1/bubble_sort,1.4 算法和算法分析,分析：当a中初始序列为自小至大有序，基本操作的执行次数是0；当a中初始序列为自大至小有序，基本操作的执行次数是 n(n-1)/2；分析最坏情况以估算算法执行时间的一个上界，即O(n2)。,1.4 算法和算法分析,图1.7 常见函数的增长率,1.4 算法和算法分析,一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法，而避免使用指数阶的算法。,1.4 算法和算法分析,算法的存储空间需求一、空间复杂度：所需存储空间是问题规模n的某个函数f(n)S(n)=O(f(n)二、算法执行过程中所需的最大空间估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间。,本章内容复习,有关数据结构的基本概念和术语抽象数据类型ADT的表示与实现类C语言的书写规范算法五个要素的确切含义掌握估算时间复杂度的方法，了解空间复杂度的度量方法。,习题,1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。3简述逻辑结构的四种基本关系并画出它们的关系图。4存储结构由哪两种基本的存储方法实现？,习题,5选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A存储结构 B存储实现C逻辑结构 D运算实现,习题,（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应 数据项的类型要一致C每个数据元素都一样D数据元素所包含的数据项的个数要相等（4）以下与数据的存储结构无关的术语是（）。A顺序队列 B.链表 C.有序表 D.链栈,习题,（5）以下说法正确的是（）。A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构（6）以下数据结构中，（）是非线性数据结构A树 B字符串 C队 D栈（1）C（2）C（3）B（4）C（5）D（6）A,习题,6试分析下面各程序段的时间复杂度。（1）x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;因为x+共执行了n-1+n-2+1=n(n-1)/2，所以执行时间为O（n2）,习题,（2）for(i=0;in;i+)for(j=0;jm;j+)aij=0;O（m*n）,习题,（3）s=0;for i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;O（n2）,习题,（4）i=1;while(i=n)i=i*3;O（log3n）,
