《数据结构(C语言描述)第1章-绪论07课件》由会员分享，可在线阅读，更多相关《数据结构(C语言描述)第1章-绪论07课件（32页珍藏版）》请在金锄头文库上搜索。
1、 数据结构（数据结构（数据结构（数据结构（C C C C语言版）语言版）语言版）语言版）二零零七年二零零七年& 简简 介介q数据结构数据结构是计算机专业的一门专业基础课，在计算机是计算机专业的一门专业基础课，在计算机学科中起着承上启下的作用，在计算机技术的各个领域也有学科中起着承上启下的作用，在计算机技术的各个领域也有着广泛的应用。学习这门课需要程序设计语言作为其基础，着广泛的应用。学习这门课需要程序设计语言作为其基础，学习前要有比较扎实的程序设计基本功（这部分内容本课程学习前要有比较扎实的程序设计基本功（这部分内容本课程中将不予涉及），同时又为后续的数据库等一系列课程提供中将不予涉及），同时
2、又为后续的数据库等一系列课程提供知识基础。知识基础。q数据结构数据结构这门课程涉及数据的组织、存储以及运算的这门课程涉及数据的组织、存储以及运算的一般方法。希望通过这门课的学习，掌握数据结构的基本概一般方法。希望通过这门课的学习，掌握数据结构的基本概念，掌握求解问题的思路与方法，具备数据抽象的能力。念，掌握求解问题的思路与方法，具备数据抽象的能力。 & 数值问题和非数值问题的比较数值问题和非数值问题的比较q 数值问题数值问题v 对象：对象：len，wide，area 用数值表示用数值表示v 对象之间的关系：对象之间的关系： area=len wide，可用方，可用方程或函数表示。程或函数表示。
3、v 数据存储：数据存储：可用程序设计可用程序设计语言中的实型变量存储数据。语言中的实型变量存储数据。q 非数值问题非数值问题v 对象：对象：课程课程 用课程名表示用课程名表示v 对象之间的关系：对象之间的关系：课程间课程间有有“次序次序”关系（不能用方关系（不能用方程或函数表示，可用图来表程或函数表示，可用图来表示）示）v 数据存储：数据存储：数据及数据之数据及数据之间的关系存储。间的关系存储。第一章第一章第一章第一章 绪论绪论绪论绪论n n学习要点学习要点学习要点学习要点 n n熟悉数据、数据对象、数据元素、数据类型、熟悉数据、数据对象、数据元素、数据类型、熟悉数据、数据对象、数据元素、数据
4、类型、熟悉数据、数据对象、数据元素、数据类型、数据结构等基本概念，特别是数据的逻辑结数据结构等基本概念，特别是数据的逻辑结数据结构等基本概念，特别是数据的逻辑结数据结构等基本概念，特别是数据的逻辑结构与物理结构概念及其关系。构与物理结构概念及其关系。构与物理结构概念及其关系。构与物理结构概念及其关系。 n n了解算法的定义、算法的特性、算法的时间了解算法的定义、算法的特性、算法的时间了解算法的定义、算法的特性、算法的时间了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。代价、算法的空间代价。代价、算法的空间代价。代价、算法的空间代价。n n掌握计算语句频度和估算算法时间复杂度的掌握计
5、算语句频度和估算算法时间复杂度的掌握计算语句频度和估算算法时间复杂度的掌握计算语句频度和估算算法时间复杂度的方法。方法。方法。方法。1.1 概述概述1.2 数据结构的基本概念数据结构的基本概念1.3 数据类型和抽象数据类型数据类型和抽象数据类型1.4 算法算法第一章第一章第一章第一章 绪论绪论绪论绪论1.1 1.1 概述概述概述概述n n计算机解题步骤计算机解题步骤计算机解题步骤计算机解题步骤具体问题具体问题数学模型数学模型算法算法编程、调试编程、调试n数据处理的种类和能力数据处理的种类和能力n数数 ( (整数整数, ,实数实数) )n字符、字符串、文字、图形、图象、声音字符、字符串、文字、图
6、形、图象、声音数值数据数值数据非数值数据非数值数据1.2 1.2 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念n n数据数据数据数据：是对客观事物的符号表示。：是对客观事物的符号表示。：是对客观事物的符号表示。：是对客观事物的符号表示。学号学号姓名姓名语文语文数学数学C C语言语言62010016201001张三张三85855454929262010026201002李四李四92928484646462010036201003王五王五87877474737362010046201004.例：张三的例：张三的C C语言考试成绩为语言考试成绩为9292分，分，9292就
7、是该同就是该同学的成绩数据。学的成绩数据。n n数据元素数据元素数据元素数据元素是数据的基本单位。在计算机程序中是数据的基本单位。在计算机程序中是数据的基本单位。在计算机程序中是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。通常作为一个整体考虑和处理。通常作为一个整体考虑和处理。通常作为一个整体考虑和处理。n n数据项数据项数据项数据项是数据不可分割的最小单位是数据不可分割的最小单位是数据不可分割的最小单位是数据不可分割的最小单位。n n数据对象数据对象数据对象数据对象是性质相同的数据元素的集合。是性质相同的数据元素的集合。是性质相同的数据元素的集合。是性质相同的数据元素的集合。一
8、个数据项一个数据项一个数据元素一个数据元素学号学号姓名姓名语文语文数学数学C C语言语言62010016201001张三张三85855454929262010026201002李四李四92928484646462010036201003王五王五87877474737362010046201004.整个表的记录是学生成绩数据整个表的记录是学生成绩数据n n数据结构数据结构数据结构数据结构是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系的数据元素之间的集合。的数据元素之间的集合。的数据元素之间的集合。的数据元素之间的集
9、合。n n数据结构的分类数据结构的分类数据结构的分类数据结构的分类n线性结构线性结构 : :元素间为严格的一对一关系。元素间为严格的一对一关系。 如上面的成绩表中各元素如上面的成绩表中各元素 n集合集合: :元素间为松散的关系。元素间为松散的关系。 n树形结构：元素间为严格的一对多关系树形结构：元素间为严格的一对多关系 n图状结构图状结构( (网状结构网状结构):):元素间为多对多关系元素间为多对多关系 n n数据结构的形式定义为：数据结构是一个二元数据结构的形式定义为：数据结构是一个二元数据结构的形式定义为：数据结构是一个二元数据结构的形式定义为：数据结构是一个二元组：组：组：组：Data-
10、Structure=（D，R）有限个数据元素的集合有限个数据元素的集合有限个节点间关系的集合有限个节点间关系的集合例例4 为毕业设计小组设计一个数据结构。假设每为毕业设计小组设计一个数据结构。假设每个小组的关系由一名教师指导一到十名学生。个小组的关系由一名教师指导一到十名学生。则数据结构的二元组表示如下：则数据结构的二元组表示如下：Group=(P,R)其中：其中：PT,G1,Gn 1n10 R| 1in, 1n10 n n逻辑结构逻辑结构逻辑结构逻辑结构：“ “数据结构数据结构数据结构数据结构” ”定义中的定义中的定义中的定义中的“ “关系关系关系关系” ”指指指指数据间的逻辑关系，故也称数
11、据结构为逻辑结数据间的逻辑关系，故也称数据结构为逻辑结数据间的逻辑关系，故也称数据结构为逻辑结数据间的逻辑关系，故也称数据结构为逻辑结构。构。构。构。n n物理结构物理结构物理结构物理结构：数据结构在计算机中的表示称为物：数据结构在计算机中的表示称为物：数据结构在计算机中的表示称为物：数据结构在计算机中的表示称为物理结构。又称存储结构。理结构。又称存储结构。理结构。又称存储结构。理结构。又称存储结构。计算机中存储信息的最小单位：计算机中存储信息的最小单位：计算机中存储信息的最小单位：计算机中存储信息的最小单位：位位位位，8 8位为位为位为位为一字节，两个字节为一字，字节、字或更多一字节，两个字
12、节为一字，字节、字或更多一字节，两个字节为一字，字节、字或更多一字节，两个字节为一字，字节、字或更多的二进制位可称为的二进制位可称为的二进制位可称为的二进制位可称为位串。位串。位串。位串。n n顺序结构顺序结构顺序结构顺序结构 （元素在存储器中的相对位置）（元素在存储器中的相对位置）（元素在存储器中的相对位置）（元素在存储器中的相对位置）n n链式结构链式结构链式结构链式结构 （元素地址的指针）（元素地址的指针）（元素地址的指针）（元素地址的指针）n n元素元素元素元素n n.n n元素元素元素元素i i.n n元素元素元素元素2 2n n元素元素元素元素1 1LoLo+mLo+(i-1)*m
13、Lo+（n-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+（i-1)*m顺顺序序存存储储每个元素所占用每个元素所占用的存储单元个数的存储单元个数所有元素存放在一所有元素存放在一片连续的存贮单元片连续的存贮单元中，逻辑上相邻的中，逻辑上相邻的元素存放到计算机元素存放到计算机内存仍然相邻。内存仍然相邻。15361536n n元素元素元素元素2 214001400n n元素元素元素元素1 113461346n n元素元素元素元素3 3n n n n元素元素元素元素4 413451345h链式存储链式存储 每个节点都由两部分组成：每个节点都由两部分组成：数据域数据域和和指针域指针域。数据
14、域数据域存放元素本身的数据，存放元素本身的数据，指针域指针域存放指针。存放指针。数据元素之间逻辑上的联系由指针来体现。数据元素之间逻辑上的联系由指针来体现。所所有有元元素素存存放放在在可可以以不不连连续续的的存存贮贮单单元元中中，但但元元素素之之间间的的关关系系可可以以通通过过地地址址确确定定，逻逻辑辑上上相相邻邻的的元元素素存存放到计算机内存后不一定是相邻的。放到计算机内存后不一定是相邻的。n n数据类型数据类型数据类型数据类型：是一个：是一个：是一个：是一个值的集合值的集合值的集合值的集合和定义在这个值集和定义在这个值集和定义在这个值集和定义在这个值集上上上上一组操作一组操作一组操作一组操
15、作总称。总称。总称。总称。例如，例如，例如，例如，C C语言中的整形变量语言中的整形变量语言中的整形变量语言中的整形变量: :其值为某个区间上的整数，定义在其上的操其值为某个区间上的整数，定义在其上的操其值为某个区间上的整数，定义在其上的操其值为某个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。作为：加、减、乘、除和取模等算术运算。作为：加、减、乘、除和取模等算术运算。作为：加、减、乘、除和取模等算术运算。n n分类：分类：分类：分类：( (按值的不同特性按值的不同特性按值的不同特性按值的不同特性) )n原子类型原子类型 ：每一个对象仅由单值构成的类型：每一个对象仅由单值构
16、成的类型 ；n结构类型结构类型 ：每一个对象可由若干成分按某种：每一个对象可由若干成分按某种结构构成的类型。结构构成的类型。 1.3 1.3 数据类型和抽象数据类型数据类型和抽象数据类型数据类型和抽象数据类型数据类型和抽象数据类型 n n抽象数据类型抽象数据类型抽象数据类型抽象数据类型（ADTADT）n n作用：抽象数据类型可以使我们更容易描述实作用：抽象数据类型可以使我们更容易描述实作用：抽象数据类型可以使我们更容易描述实作用：抽象数据类型可以使我们更容易描述实际问题。际问题。际问题。际问题。例：用线性表描述学生成绩表，用树或图描述例：用线性表描述学生成绩表，用树或图描述例：用线性表描述学生
17、成绩表，用树或图描述例：用线性表描述学生成绩表，用树或图描述遗传关系。遗传关系。遗传关系。遗传关系。n n定义定义定义定义：一个数学模型以及定义在该模型上的一：一个数学模型以及定义在该模型上的一：一个数学模型以及定义在该模型上的一：一个数学模型以及定义在该模型上的一组操作。组操作。组操作。组操作。n n好处：可提高软件的复用程度。好处：可提高软件的复用程度。好处：可提高软件的复用程度。好处：可提高软件的复用程度。 使用它的人可以只关心它的逻辑特征，不需使用它的人可以只关心它的逻辑特征，不需使用它的人可以只关心它的逻辑特征，不需使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人
18、同样不必要要了解它的存储方式。定义它的人同样不必要要了解它的存储方式。定义它的人同样不必要要了解它的存储方式。定义它的人同样不必要关心它如何存储。关心它如何存储。关心它如何存储。关心它如何存储。n n例：线性表这样的抽象数据类型，其数学模型是：例：线性表这样的抽象数据类型，其数学模型是：例：线性表这样的抽象数据类型，其数学模型是：例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：数据元素的集合，该集合内的元素有这样的关系：数据元素的集合，该集合内的元素有这样的关系：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋除第一
19、个和最后一个外，每个元素有唯一的前趋除第一个和最后一个外，每个元素有唯一的前趋除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个和唯一的后继。可以有这样一些操作：插入一个和唯一的后继。可以有这样一些操作：插入一个和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。元素、删除一个元素等。元素、删除一个元素等。元素、删除一个元素等。原子类型原子类型值不可分解，如值不可分解，如intint固定聚合固定聚合类型类型值由确定数目的成分按某种结构值由确定数目的成分按某种结构组成，如复数组成，如复数可变聚合可变聚合类型类型值的成分数目不确定，如学生基值的成分数目
20、不确定，如学生基本情况本情况抽象数据类型分类抽象数据类型分类n n抽象数据类型表示法抽象数据类型表示法抽象数据类型表示法抽象数据类型表示法：一、一、一、一、三元组表示三元组表示三元组表示三元组表示：（：（：（：（D D，S S，P P）其中其中其中其中D D是数据对象，是数据对象，是数据对象，是数据对象，S S是是是是D D上的关系集，上的关系集，上的关系集，上的关系集，P P是是是是对对对对D D的基本操作集。的基本操作集。的基本操作集。的基本操作集。二、二、二、二、抽象数据类型的定义格式抽象数据类型的定义格式抽象数据类型的定义格式抽象数据类型的定义格式：ADT ADT 抽象数据类型名抽象数
21、据类型名抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象：数据对象： 数据关系：数据关系：数据关系：数据关系： 基本操作：基本操作：基本操作：基本操作： ADT ADT 抽象数据类型名抽象数据类型名抽象数据类型名抽象数据类型名n nn抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型的表示与实现v 抽象数据类型可以通过固有的数据类型（如整型、抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。实型、字符型等）来表示和实现。注注 1 ：它有些类似它有些类似C语言中的结构（语言中的结构
22、（struct）类型，）类型，但增加了相关的服务。但增加了相关的服务。注注 2 ：教材中用的是类教材中用的是类C语言（介于伪码和语言（介于伪码和C语言之语言之间）作为描述工具。其描述语法见间）作为描述工具。其描述语法见P10-11。n n算法的定义算法的定义算法的定义算法的定义ispass(intispass(int num44) num44) int int i,j; i,j; for(i=0;i4;i+)for(i=0;i4;i+)for(j=0;j4;j+) for(j=0;j4;j+) if(numij!=i*4+j+1)if(numij!=i*4+j+1)return 0; retu
23、rn 0; return 1; return 1; /*/*类似华容道游戏中判断游戏是否结束的算法类似华容道游戏中判断游戏是否结束的算法类似华容道游戏中判断游戏是否结束的算法类似华容道游戏中判断游戏是否结束的算法*/ */定义：算法是对特定问题求解步骤的一种描述，定义：算法是对特定问题求解步骤的一种描述，定义：算法是对特定问题求解步骤的一种描述，定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多是指令的有限序列，其中每条指令表示一个或多是指令的有限序列，其中每条指令表示一个或多是指令的有限序列，其中每条指令表示一个或多个操作。个操作。个操作。个操作。 1.4
24、算法算法n n算法的特性算法的特性算法的特性算法的特性n n有穷性：算法必须在有限步内结束；有穷性：算法必须在有限步内结束；有穷性：算法必须在有限步内结束；有穷性：算法必须在有限步内结束；n n确定性：组成算法的操作必须清晰无二义性。确定性：组成算法的操作必须清晰无二义性。确定性：组成算法的操作必须清晰无二义性。确定性：组成算法的操作必须清晰无二义性。n n可行性：组成算法的操作必须能够在计算机上实现。可行性：组成算法的操作必须能够在计算机上实现。可行性：组成算法的操作必须能够在计算机上实现。可行性：组成算法的操作必须能够在计算机上实现。n n输入：输入：输入：输入：0 0 0 0个或多个输入
25、；个或多个输入；个或多个输入；个或多个输入；n n输出：输出：输出：输出：1 1 1 1个或多个输出；个或多个输出；个或多个输出；个或多个输出；有穷性有穷性haha()/*only a joke,do nothing.*/ main()printf(请稍等请稍等.您将知道世界的未您将知道世界的未日日.);while(1)haha(); 确定性确定性float average(int *a,int num)int i;long sum=0;for(i=0;inum;i+)sum+=*(a+);return sum/num;main()int score10=1,2,3,4,5,6,7,8,9,0
26、;printf(%f,average(score,10); 输出输出getsum(int num)int i,sum=0;for(i=1;ib)if(ac) return c;else return a; 程序对于几程序对于几组输入数据组输入数据能够得出满能够得出满足规格说明足规格说明要求的结果。要求的结果。max(int a,int b,int c)if (ab)if(ac) return a;else return c; /* 8,6,7 */ /* 9,3,2 */程序对于精程序对于精心选择的典心选择的典型、苛刻的型、苛刻的输入数据能输入数据能够得出满足够得出满足规格说明要规格说明要求的
27、结果。求的结果。max(int a,int b,int c)if (ab) if(ac) return a; else return c; else if(bc) return b; else return c; 程序对于一切合法的输入数据都能产生满足程序对于一切合法的输入数据都能产生满足规格说明要求的结果。规格说明要求的结果。n算法设计的要求算法设计的要求n算法效率的度量算法效率的度量v 算法效率算法效率 用依据该算法编制的程序在计算用依据该算法编制的程序在计算机上执行所消耗的时间来度量。通常用事后统计和机上执行所消耗的时间来度量。通常用事后统计和事前分析估计这种方法。但同一个算法用不同的语
28、事前分析估计这种方法。但同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效言、不同的编译程序、在不同的计算机上运行，效率均不同，所以使用绝对时间单位衡量算法效率不率均不同，所以使用绝对时间单位衡量算法效率不合适。合适。在三个整在三个整在三个整在三个整数中求最数中求最数中求最数中求最大者大者大者大者max(intmax(int a,int a,int b,int b,int c)c)if (ab)if (ab)if(ac) return a;if(ac) return a;else return c;else return c; elseelseif(bc) return b;if
29、(bc) return b;else return c; else return c; /* /*无需额外存储空间，无需额外存储空间，无需额外存储空间，无需额外存储空间，只需两次比较只需两次比较只需两次比较只需两次比较*/ */max(intmax(int a a3 3) )intint c,int c,int i; i;c=a0; c=a0; for(i=1;ifor(i=1;ic) c=ai;if (aic) c=ai;return c;return c; /* /*需要两个额外的存需要两个额外的存需要两个额外的存需要两个额外的存储空间，两次比较，储空间，两次比较，储空间，两次比较，储空间
30、，两次比较，至少一次赋值至少一次赋值至少一次赋值至少一次赋值*/ */* /*共需共需共需共需5 5个整型数空间个整型数空间个整型数空间个整型数空间*/ */ 100100个整个整个整个整数数数数同上的算法难写难同上的算法难写难同上的算法难写难同上的算法难写难读读读读/* /*共需共需共需共需102102个整型数空个整型数空个整型数空个整型数空间间间间*/ */ n n算法效率的度量算法效率的度量算法效率的度量算法效率的度量n n事后统计的方法；事后统计的方法；事后统计的方法；事后统计的方法；n n事前分析估算的方法；事前分析估算的方法；事前分析估算的方法；事前分析估算的方法；事前估算法要考虑
31、以下的因素：事前估算法要考虑以下的因素：事前估算法要考虑以下的因素：事前估算法要考虑以下的因素： n n问题的规模；问题的规模；问题的规模；问题的规模；n n编写程序时所用的程序设计语言；编写程序时所用的程序设计语言；编写程序时所用的程序设计语言；编写程序时所用的程序设计语言； n n机器的速度；机器的速度；机器的速度；机器的速度； n n算法所用的策略。算法所用的策略。算法所用的策略。算法所用的策略。撇开这些与机器软硬件有关的因素，可以认为撇开这些与机器软硬件有关的因素，可以认为一个特定算法一个特定算法“运行工作量运行工作量”的大小只依赖与的大小只依赖与问题的规模，或者说只是问题规模的函数。
32、问题的规模，或者说只是问题规模的函数。例例例例 两个两个两个两个n*nn*n矩阵相乘的算法。矩阵相乘的算法。矩阵相乘的算法。矩阵相乘的算法。forfor（i=1i=1；i=ni=n；+i+i）forfor（j=1j=1；j=nj=n；+j+j） cij=0cij=0；forfor（k=1k=1；k=nk=n；+k+k）cij+=aik*bkjcij+=aik*bkj； 语句语句语句语句到语句到语句到语句到语句执行的次数依次是（执行的次数依次是（执行的次数依次是（执行的次数依次是（n+1n+1），），），）， n n（n+1n+1），），），）， n n2 2，（，（，（，（n+1n+1）n n
33、2 2 ， n n3 3。它们之和就是该算。它们之和就是该算。它们之和就是该算。它们之和就是该算法的时间开销法的时间开销法的时间开销法的时间开销T T（n n）=2n=2n3 3+3n+3n2 2+2n+1+2n+1当当当当n n充分大的时候，充分大的时候，充分大的时候，充分大的时候，T T（n n）与）与）与）与f f（n n）=n=n3 3的数量级相同。的数量级相同。的数量级相同。的数量级相同。于是，该算法的时间复杂度为：于是，该算法的时间复杂度为：于是，该算法的时间复杂度为：于是，该算法的时间复杂度为：T T（n n）=O=O（n n3 3），其），其），其），其原语句是语句原语句是语句
34、原语句是语句原语句是语句。 频度频度：是指该语句重复执行的次数：是指该语句重复执行的次数n n算法的时间复杂度算法的时间复杂度算法的时间复杂度算法的时间复杂度( (Time Complexity)Time Complexity)一般来说，设算法中所有语句的一般来说，设算法中所有语句的一般来说，设算法中所有语句的一般来说，设算法中所有语句的频度之和频度之和频度之和频度之和记作记作记作记作T(n)T(n)，它是问题规模，它是问题规模，它是问题规模，它是问题规模n n的某个函数的某个函数的某个函数的某个函数f(n)f(n)，记作：，记作：，记作：，记作： T(n) = O(f(n) T(n) = O
35、(f(n) 它表示随问题规模它表示随问题规模它表示随问题规模它表示随问题规模n n的增大，算法执行时间的的增大，算法执行时间的的增大，算法执行时间的的增大，算法执行时间的增长率与增长率与增长率与增长率与f(n) f(n) 的增长率相同，称做算法的的增长率相同，称做算法的的增长率相同，称做算法的的增长率相同，称做算法的渐近渐近渐近渐近时间复杂度时间复杂度时间复杂度时间复杂度，简称，简称，简称，简称时间复杂度时间复杂度时间复杂度时间复杂度。语句在算法中被重复执行的语句在算法中被重复执行的次数次数(Frequency Count)1.+x; s=0; 2.for( j=1; j=n; +j )for
36、 ( k=1; k=n; +k) +x; s+=x;3.for (i=1; i=n; +i) +x; s+=x;T(n)=O(1)T(n)=O(n2)T(n)=O(n)例例 求下面程序段的时间复杂度求下面程序段的时间复杂度4. for (i=2;i=n;+i)for (j=2;k=1&change;-i)for(i=n-1,change=TRUE;i=1&change;-i) change=FALSE; change=FALSE; for(j=0;ji;+j) for(j=0;jaj+1)if(ajaj+1) ajaj+1;ajaj+1;change=TRUE;change=TRUE; 冒泡排
37、序的时间复杂度为冒泡排序的时间复杂度为冒泡排序的时间复杂度为冒泡排序的时间复杂度为? ?1. O(1) 常量阶，与常量阶，与n无关无关 2. O(log2 n) 对数阶对数阶3. O(n) 线性阶线性阶 4. O(n log2 n) n log2 n阶阶5. O(n2) 平方阶平方阶 6. O(n3) 立方阶立方阶7. O(2n) 指数阶指数阶注：注：v 增长率从增长率从17由慢到快；由慢到快；v 尽量少用指数阶的算法；尽量少用指数阶的算法；v 有时算法中基本操作重复执行的次数还随问题的输入数据有时算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。除特别指明外，均指最坏情况下的时间复
38、杂集不同而不同。除特别指明外，均指最坏情况下的时间复杂度。度。时间复杂度通常具有的形式时间复杂度通常具有的形式n n算法的空间复杂度算法的空间复杂度算法的空间复杂度算法的空间复杂度( (Time Complexity)Time Complexity)类似于算法的时间复杂度，空间复杂度可以作类似于算法的时间复杂度，空间复杂度可以作类似于算法的时间复杂度，空间复杂度可以作类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。为算法所需存储空间的量度。为算法所需存储空间的量度。为算法所需存储空间的量度。记作：记作：记作：记作：S(n)=O(f(n)S(n)=O(f(n)其中其中其中其中n n为问题规模的大小。为问题规模的大小。为问题规模的大小。为问题规模的大小。主要包括三个部分：主要包括三个部分：主要包括三个部分：主要包括三个部分：（1 1）输入数据所占用的空间。）输入数据所占用的空间。）输入数据所占用的空间。）输入数据所占用的空间。（2 2）程序本身所占用的空间。）程序本身所占用的空间。）程序本身所占用的空间。）程序本身所占用的空间。（3 3）辅助变量所占用的空间。）辅助变量所占用的空间。）辅助变量所占用的空间。）辅助变量所占用的空间。
