“算法与数据结构”-基本概念

1、数 据 结 构主讲人：李志芳主讲单位：软件技术教研室时间：20082009第二学期第一章 绪论 知 识 点 数据结构中常用的基本概念和术语 算法描述和分析方法 难 点 算法复杂性的分析方法 要 求 了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系 掌握算法复杂性的概念及分析方法 基本概念数据结构 用计算机解决一个具体问题时，大致需要经过下列几个步骤：抽象数学模型设计数学模型编程测试、调整最终解决方法分析过程实施过程基本概念 数据结构可以应用于问题的整个解决过程即分析过程和实施过程。 首先分析过程中有一个步骤：数据的分析与设计，为了更好地对问题的数据进行组织和处

2、理，常常要借助于数据结构的思想来完成。 例：汽车的故障诊断系统 餐饮管理系统 人机对弈问题 其次在具体的实施过程当中，经常需要对数据进行处理，在数据结构课程当中，给出了各种数据的各种处理方法。 基本概念 数据(Data)：一切能够由计算机接受和处理的对象 数据元素(Data element)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。一个数据元素可由若干个数据项组成。 数据项(Data item)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。 字段（域）：字段是对元素详细地描述，是指元素的具体信息。 基本概念 数据结构(Data structure)：数据之间的

3、相互关系，即数据的组织形式。 数据结构根据数据元素之间关系的不同特征，通常有下列4类基本结构：集合、线性结构、树形结构、图或网状结构，通常这几类结构称为逻辑结构。 研究数据结构，是指研究数据的逻辑结构和物理结构 数据的逻辑结构：数据元素之间的逻辑关系。 数据的物理结构：数据元素在计算机存储器中是如何存储的，所以又叫做存储结构。 运算：解决问题的算法。基本概念 由此可见，对一种数据结构，需要涉及到其逻辑结构、存储结构和运算三个方面，也就是说，对每种结构都要注意三方面的联系。 由于不同的存储形式对算法的时间性能、空间性能等的影响比较大，即是具有相同的存储结构，也可能会存在不同的算法实现，所以需要对

4、算法进行分析。基本概念 算法(Algorithm)：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特征：1）有穷性 2）确定性 3）可行性 4）输入 5）输出 算法是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。 由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。 算法的评价原则一个好的算法应考虑达到以下目标：正确性：算法应能正确地实现处理要求 。易读性：有助于对算法的理解，便于纠正和扩充 。简单性：使证明其正确性比较容易，对算法进行修改也比较方便。健壮性：算法应该具有纠错的能力，当输入非法

5、数据时，算法应适当做出反应或进行处理。高效率：达到所需的时、空性能。 算法效率的度量算法的复杂性包括时间复杂性（所需运算时间）和空间复杂性（所占存储空间），重点是时间复杂性 。 一个算法所需的运算时间通常与所解决问题的规模大小、书写程序的语言等有关。 算法的时间的度量是以问题当中的原操作的重复执行的次数来计算的。 用n 表示问题规模的量 ，算法中基本操作执行的次数是问题规模的某个函数f(n)，算法的时间度量记作： T( n ) = O( f( n ) ) 表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度。 (a) +x;s=0 (b) for(i=1;i

6、=n,+i) +x; s+=x; (c) for(j=1;j=n;+j) for(k=1;k=n;+k) +x; s+=x;以上三个程序段含操作“x增1”的语句的执行次数分别为1、n、n2则这3个程序段的时间复杂度分别为 O(1)、O(n)、 O(n2) ，分别称为常量阶、线性阶和平方阶。 算法的时间复杂度考虑的只是对于问题规模n的增长率，在难以精确计算基本操作次数的情况下，只需要求出他关于n的增长率即可。 for(I=2;I=n;+i) for(j=2;j=i-1;+j) +x; aij=x T(n)=O(n2)算法效率的度量当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。

7、一般地，对于足够大的n，常用的时间复杂性存在以下顺序： O(1) O(logn) O(n) O(n*logn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)为常数数量级,即算法的时间复杂性与输入规模n无关。算法效率的度量算法的运行时间往往还与具体输入的数据有关，通常用以下两种方法来确定一个算法的运算时间：1. 平均时间复杂性：研究同样的n值时各种可能的输入，取它们运算时间的平均值。2. 最坏时间复杂性：研究各种输入中运算最慢的一种情况下的运算时间。 算法效率的度量算法的描述 本书将采用类C语言描述算法 类C语言是标准C语言的简化 ，与标准C语言的主要区别如下：1. 所有

8、算法都以如下所示的函数形式表示： 函数类型 函数名（参数表） 语句序列 类C语言的形参书写比标准C语言简单，如，int fun(int a,int b,int c)可以简单写成int fun(int a,b,c)算法的描述2. 局部量的说明可以省略，必要时对其作用给予注释 。3. 不含go to语句，增加一个出错处理语句error(字符串)，其功能是终止算法的执行并给出表示出错信息的字符串。4. 输入/输出语句有： 输入语句 scanf(格式串),变量1，变量N）； 输出语句 printf(格式串),变量1，变量N）； 通常省略格式串 。 例题计算下面交换i和j内容程序段的时间复杂性。 tem

9、p=i; i=j; j=temp; 解：以上三条单个语句均执行1次，因此算法的时间复杂度为常数阶,记作T(n)=O(1).计算下面求累加和程序段的时间复杂性 （1） sum=0； （一次） （2） for(i=1;i=n;i+) （n次 ） （3） for(j=1;j=n;j+) （n2次 ） （4） sum+； （n2次 ） 解：T(n)=2n2+n+1 =O(n2) 分析下列算法的时间复杂性: 1sum=0; for (i=1;i=n;i+) sum=sum+i; 2i=1; while(i=n) i=i*10;3sum=0; for(i=0;in;i+) for(j=0;jn;j+) sum=sum+Arrayij; 作业