数据结构清华大学殷人昆ppt课件.ppt

《数据结构清华大学殷人昆ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构清华大学殷人昆ppt课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1清华大学计算机系清华大学计算机系 殷人昆殷人昆数据结构课件数据结构课件38-2数据结构在计算机教育中的地位数据结构在计算机教育中的地位n计算机教育是一个大的系统工程，有计划、有设计算机教育是一个大的系统工程，有计划、有设计、有实施、有检验，最后要有成果。计、有实施、有检验，最后要有成果。n数据结构在计算机教育中是一门核心课程，是程数据结构在计算机教育中是一门核心课程，是程序设计系列课程中重要的一环。序设计系列课程中重要的一环。n数据结构与算法与程序设计课程一脉相承。程序数据结构与算法与程序设计课程一脉相承。程序设计训练学生分析问题、解决问题的技能，数据设计训练学生分析问题、解决问题的技能，数

2、据结构与算法则训练学生在问题解决过程中如何组结构与算法则训练学生在问题解决过程中如何组织数据，如何运用合理的数据结构辅助实现高效织数据，如何运用合理的数据结构辅助实现高效的算法。的算法。38-3数据结构在计算机教育中的地位（必修）数据结构在计算机教育中的地位（必修）计算机组织计算机组织与系统结构与系统结构 程序设计与程序设计与问题解决问题解决数据结构基础数据结构基础数学数学 1数学数学 2计算机科学基础计算机科学基础计算机系统计算机系统原理与汇编原理与汇编算法与数算法与数据结构据结构程序设计语言基础程序设计语言基础操作系统操作系统有穷自动机有穷自动机38-4数据结构在计算机教育中的地位（选修）

3、数据结构在计算机教育中的地位（选修）数据结构基础数据结构基础计算机科学基础计算机科学基础算法与数算法与数据结构据结构文件处理文件处理(数据库数据库)算法设计与分析算法设计与分析软件工程软件工程图形学图形学系统模拟系统模拟5第一章第一章 基本概念基本概念清华大学计算机系清华大学计算机系 殷人昆殷人昆数据结构课件数据结构课件第第38-6数据结构的基本概念数据结构的基本概念抽象数据类型抽象数据类型算法定义算法定义性能分析与度量性能分析与度量第一章 数据结构的概念38-7数据（数据（data）n数据是信息的载体，是描述客观事物的数、数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，

4、被计算字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。机程序识别和处理的符号的集合。n数据的分类数据的分类r数值性数据、非数值性数据数值性数据、非数值性数据r输入数据、输出数据、存储数据输入数据、输出数据、存储数据n计算机软件计算机软件 = 程序程序+文档文档+数据数据r数据是指计算机程序执行所用的数据数据是指计算机程序执行所用的数据38-8数据元素数据元素 (data element)n数据的基本单位。在计算机程序中常作为一个数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。整体进行考虑和处理。n有时一个数据元素可以由若干数据项有时一个数据元素可以由若干数据项（

5、Data Item）组成。数据项是具有独立含义的最小标组成。数据项是具有独立含义的最小标识单位。识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。n数据元素的集合是针对某种特定的应用，相同数据元素的集合是针对某种特定的应用，相同数据类型的数据元素的一个聚集。如学生组成数据类型的数据元素的一个聚集。如学生组成班级，学生是数据元素，班级是一学生集合。班级，学生是数据元素，班级是一学生集合。38-9数据在系统开发中的视图数据在系统开发中的视图n数据在系统开发中的讨论范畴分为数据在系统开发中的讨论范畴分为数据结构数据结构 + + 数据内容数据内容 + + 数据流数据流n数据结构

6、指某一数据元素集合中数据元素之间数据结构指某一数据元素集合中数据元素之间的关系。的关系。n数据内容指这些数据元素的具体涵义和内容。数据内容指这些数据元素的具体涵义和内容。n数据流指这些数据元素在系统处理过程中是如数据流指这些数据元素在系统处理过程中是如何传递和变换的。何传递和变换的。r因此，讨论数据结构时因此，讨论数据结构时, ,主要不是讨论数据主要不是讨论数据元素的内容和如何处理。元素的内容和如何处理。38-10数据结构（数据结构（Data Structures）某一数据元素集合中的所有数据成员之间的某一数据元素集合中的所有数据成员之间的关系。完整的定义为：关系。完整的定义为： Data_S

7、tructure = D, R, M n其中，其中，rD 是某一数据元素的集合；是某一数据元素的集合；rR 是该集合中所有数据成员之间的关系的有是该集合中所有数据成员之间的关系的有限集合；限集合；rM 是作用在该集合所有数据成员之上的方法是作用在该集合所有数据成员之上的方法（或操作）。（或操作）。38-11例：例：N 个网点之间的连通关系个网点之间的连通关系n树形关系：树形关系：n 个结点用个结点用n-1条边连通。条边连通。n网状关系（或图）：网状关系（或图）：n 个结点可以用多条边（个结点可以用多条边（0 en(n-1en(n-1)/2）连通。）连通。e 是边数。是边数。 树形关系树形关系网

8、状关系网状关系15243615243638-12数据结构是数据的组织形式数据结构是数据的组织形式n数据元素间的数据元素间的逻辑关系逻辑关系，即数据的，即数据的逻辑结构逻辑结构；n数据元素及其关系在计算机存储内的表示，即数据元素及其关系在计算机存储内的表示，即数据的数据的物理结构物理结构；n数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。逻辑结构逻辑结构用户用户物理结构物理结构公用操作集公用操作集私用操作集私用操作集访问访问使用使用通过通过映射到映射到38-13数据的逻辑结构数据的逻辑结构n数据的逻辑结构数据的逻辑结构从逻辑关系上从逻辑关系上描述数据，与数描述数据，与数据的

9、存储无关；据的存储无关；n数据的逻辑结构可以看作是从具体问题抽象出数据的逻辑结构可以看作是从具体问题抽象出来的数据模型（面向应用的）；来的数据模型（面向应用的）；n数据的逻辑结构与数据元素本身的形式、内容数据的逻辑结构与数据元素本身的形式、内容无关；无关；n数据的逻辑结构与数据元素的相对存储位置无数据的逻辑结构与数据元素的相对存储位置无关。关。38-14数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构r 线性表线性表n非线性结构非线性结构r 多维数组多维数组r 广义表广义表r 树树r 图（或网络）图（或网络）n 无结构无结构r 集合集合38-15线性结构线性结构树形结构树形结构树树 二叉

10、树二叉树 二叉搜索二叉搜索( (排序排序) )树树1413121123456789103158710119987456623131bindevetclibuser138-16堆结构堆结构“最大最大”堆堆 “最小最小”堆堆12354871110291641012115123698738-17图结构图结构 网络结构网络结构1256431254361133181466516192138-18数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言的实数据的存储结构是逻辑结构用计算机语言的实现；现；n数据的存储结构依赖于计算机语言数据的存储结构依赖于计算机语言。r 顺序存储表示顺序存储表示r

11、 链接存储表示链接存储表示r 索引存储表示索引存储表示r 散列存储表示散列存储表示38-19数据类型（数据类型（Data Type）n数据类型数据类型 一组性质相同的值的集合一组性质相同的值的集合, 以及定义于这个值以及定义于这个值集合上的一组操作的总称。集合上的一组操作的总称。n数据类型的分类数据类型的分类r基本数据类型基本数据类型r构造数据类型构造数据类型nC语言中的基本数据类型语言中的基本数据类型字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 38-20n基本数据类型可以看作是计算机中已实现的数基本数据类型可以看作是计算机中已实现的数据结构。据结构。n构造数据类型由构造

12、数据类型由基本数据类型基本数据类型或或构造数据类型构造数据类型组成，在应用中可视为一种数据模型。组成，在应用中可视为一种数据模型。n构造数据类型由不同成分类型构成。构造数据类型由不同成分类型构成。n数据类型就是数据结构，不过它是从编程者的数据类型就是数据结构，不过它是从编程者的角度来使用的。角度来使用的。n数据类型是模板数据类型是模板，必须定义属于某种数据类型，必须定义属于某种数据类型的变量，才能参加运算。的变量，才能参加运算。 38-21抽象数据类型抽象数据类型 (ADTs: Abstract Data Types)n抽象数据类型由用户定义，用以表示应用问题的抽象数据类型由用户定义，用以表示

13、应用问题的数据模型。数据模型。n抽象数据类型由构造数据类型组成抽象数据类型由构造数据类型组成, 并包括一组并包括一组相关的服务（或称操作）。相关的服务（或称操作）。n三大特征：三大特征：r信息隐蔽信息隐蔽r数据封装数据封装r使用与实现相分离。使用与实现相分离。38-22抽抽象象数数据据类类型型 查找查找 登录登录 删除删除 修改修改 符符 号号 表表38-23n抽象数据类型构成现代程序设计的基础。它的作抽象数据类型构成现代程序设计的基础。它的作用是使程序编写得易于编程、易于测试、易于修用是使程序编写得易于编程、易于测试、易于修改。改。n实现实现信息隐藏信息隐藏，把所有数据和操作分为公有和私，把

14、所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。有，可减少接口复杂性，从而减少出错机会。n实现实现数据封装数据封装，把数据和操作封装在一起，从语，把数据和操作封装在一起，从语义上更加完整。义上更加完整。n实现实现使用与实现相分离使用与实现相分离，使用者只能通过接口上，使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。以使得修改局部化，提高系统灵活性。38-24算法定义算法定义n定义：定义：一个有穷的指令集，这些指令为解决某一一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特定

15、任务规定了一个运算序列算法算法 + 数据结构数据结构 = 程序程序n特性：特性：r 输入输入 有有0个或多个输入个或多个输入r 输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)r 确定性确定性 每步定义都是确切、无歧义的每步定义都是确切、无歧义的r 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束r 有效性有效性 每一条运算应足够基本，可用计算机每一条运算应足够基本，可用计算机指令实现指令实现38-25几种常用算法的类型几种常用算法的类型n三种最基本的常用算法：三种最基本的常用算法：r穷举型：按某种顺序进行逐一枚举和检验，穷举型：按某种顺序进行逐一枚举和检验，并从中

16、找出那些符合要求的候选解作为问题并从中找出那些符合要求的候选解作为问题的解。的解。r递推型：由已知至递推型：由已知至i-1规模的解，通过递推，规模的解，通过递推，获得规模为获得规模为 i 的解。的解。 r递归型：把规模为递归型：把规模为N的问题分解成一些规模的问题分解成一些规模较小的问题，然后从这些小问题的解构造出较小的问题，然后从这些小问题的解构造出大问题的解大问题的解 。38-26穷举法举例穷举法举例n求解求解“百钱买百鸡百钱买百鸡”问题问题：公鸡每只公鸡每只5钱，母鸡钱，母鸡每只每只3钱，小鸡钱，小鸡3只只1钱。钱。n求解思路：设公鸡数为求解思路：设公鸡数为x，母鸡数为，母鸡数为y，小鸡

17、数为，小鸡数为z，则可以得到下面的整数不定方程组：，则可以得到下面的整数不定方程组： x + y + z = 100 5*x + 3*y + z/3 = 100n利用穷举法可以写出下面的算法程序：利用穷举法可以写出下面的算法程序：#include void main() 38-27int x, y, z; for ( x = 0; x = 100; x+ ) for ( y = 0; y = 100; y+ ) for ( z = 0; z = 100; z+ ) if ( x+y+z = 100 & 5*x+3*y+z/3 = 100 ) printf (%d%d%dn, x, y, z);

18、n执行结果执行结果38-28穷举法的算法分析穷举法的算法分析n虽然上述程序很简单，但分析一下可知，此程序虽然上述程序很简单，但分析一下可知，此程序为三重循环，循环次数为为三重循环，循环次数为1013 = 1030301，为，为106量级。如果改为量级。如果改为“万钱买万鸡万钱买万鸡”，循环次数将达，循环次数将达1012量级，计算量太大，这正是穷举法的缺点。量级，计算量太大，这正是穷举法的缺点。n为此，可考虑对程序做优化。例如，针对为此，可考虑对程序做优化。例如，针对“百钱百钱买百鸡买百鸡”问题，如果用所有的钱去买公鸡，最多问题，如果用所有的钱去买公鸡，最多可买可买20只，而用所有的钱去买母鸡，

19、最多可买只，而用所有的钱去买母鸡，最多可买33只，所以只，所以x、y的值范围可限定在的值范围可限定在20和和33。这样，。这样，z的值就自然确定了，而不再是一个变量，可剪去的值就自然确定了，而不再是一个变量，可剪去第第3层循环。层循环。38-29n与上面程序等效的程序：与上面程序等效的程序：#include void main() int x, y, z; for ( x = 0, x = 20; x+ ) for ( y = 0; y 1时。时。n用递推法编写的程序为：用递推法编写的程序为： # include int Fib ( int n ) int f0 = 0, f1 = 1, f,

20、 i;38-31 if ( n = 0 | n = 1 ) return n; for ( i = 2; i = n; i+ ) f = f0 + f1; /由前两步结果推出当前结果由前两步结果推出当前结果 f0 = f1; /原前一步当作下一次的前两步原前一步当作下一次的前两步 f1 = f; /当前结果当作下一次的前一步当前结果当作下一次的前一步 /在进行向前传递时，要注意传递的时序在进行向前传递时，要注意传递的时序 return f; n主程序调用方式：主程序调用方式：int n = 7; printf ( ”Fib(%d)=%dn”, n, Fib (n) ); 38-32递归法举例递

21、归法举例n所谓递归算法就是在函数过程中直接或间接调用所谓递归算法就是在函数过程中直接或间接调用自己。还是求斐波那契数列的问题，相应的递归自己。还是求斐波那契数列的问题，相应的递归程序为：程序为：int Fib ( int n ) if ( n = 0 | n = 1 ) return n;/结束项结束项else return Fib (n-1) + Fib(n-2);/递归项递归项n递归算法简单，但不能无限递归。因此，算法中递归算法简单，但不能无限递归。因此，算法中需要设置递归结束条件。需要设置递归结束条件。38-33递归法分析递归法分析n递归法的时间效率较低，原因是重复计算太多。递归法的时间

22、效率较低，原因是重复计算太多。n例如，例如，计算计算Fib(5)，总计算次数为，总计算次数为2Fib(6)-1 = 15。 递归调用树递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)38-34n例如，编写一个算法，在一个一维整数数组例如，编写一个算法，在一个一维整数数组An中查找满足给定值中查找满足给定值 x 的元素，找到后函数返回该的元素，找到后函数返回该元素的位置，否则函数返回元素的位置，否则函数返回 -1。int Search ( int A ,

23、int x, int n ) int i = 0; while ( i n ) /通过循环枚举检查通过循环枚举检查 if ( Ai = x ) return i; /满足要求满足要求 else i = i+1; return -1;更复杂的实例更复杂的实例38-35n再看递归法。每次递归自己是为了缩小查找区间，再看递归法。每次递归自己是为了缩小查找区间，逐步逼近到要查找的元素。在函数参数表中增加逐步逼近到要查找的元素。在函数参数表中增加本次递归调用时的开始查找位置。本次递归调用时的开始查找位置。 int Search ( int A , int x, int n, int start ) if

24、 ( start = n ) return -1; if ( Astart = x ) return start; else return Search ( A, x, n, start+1 ); n递归的主调用语句为递归的主调用语句为loc = Search ( A, x, n, 0 )。如果查找失败或查找成功，函数直接返回结果，如果查找失败或查找成功，函数直接返回结果，否则通过递归，到否则通过递归，到start以后的区间逐个检查。以后的区间逐个检查。38-36性能分析与度量性能分析与度量n算法就是为了问题求解。算法的效率是衡量算法就是为了问题求解。算法的效率是衡量是否具有可计算性的关键。是

25、否具有可计算性的关键。n性能分析的目的就是要了解算法的效率。性能分析的目的就是要了解算法的效率。n性能（性能（Performance），指算法功能实际执行），指算法功能实际执行的功效或表现如何。主要从算法执行的时间的功效或表现如何。主要从算法执行的时间和空间效率进行分析。分析方式有：和空间效率进行分析。分析方式有：r算法的后期测试算法的后期测试r算法的事前估计算法的事前估计38-37算法的后期测试算法的后期测试n在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数 time ( )，测，测定算法完成某一功能所花费时间。定算法完成某一功能所花费时间。n例如，有一个例如，有一个顺序搜索顺序

26、搜索 (Sequenial Search)算法算法int seqsearch ( int a , int n, int x ) /在在a0,an 1中搜索中搜索x int i = 0; while ( i n & ai != x ) i+; if ( i = n ) return -1; return i;38-38n插装插装 time( ) 后后的计时程序为的计时程序为 double start, stop; time (&start); int k = seqsearch (a, n, x); time (&stop); double runTime = stop - start; pri

27、ntf ( ”%d%dn , n, runTime );n可以测算。但受限于硬件设备和操作系统、编可以测算。但受限于硬件设备和操作系统、编译器等，测算比较有一定困难。译器等，测算比较有一定困难。38-39算法的事前估计算法的事前估计n空间复杂度度量空间复杂度度量r存储空间的固定部分存储空间的固定部分附加存储空间，常数、简单变量、定长成分附加存储空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员（如数组元素、结构成分、对象的数据成员等）变量所占空间等）变量所占空间r可变部分可变部分尺寸与问题规模有关的成分变量所占空间、尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过递

28、归栈所用空间、通过 malloc 和和 free 命令命令动态使用空间动态使用空间38-40n时间复杂度度量时间复杂度度量r运行时间运行时间 = 算法每条语句执行时间之和。算法每条语句执行时间之和。r每条语句执行时间每条语句执行时间 = 该语句的执行次数该语句的执行次数 (频频度度)语句执行一次所需时间。语句执行一次所需时间。r语句执行一次所需时间语句执行一次所需时间取决于机器的指令性取决于机器的指令性能和速度和编译所产生的代码质量，很难确能和速度和编译所产生的代码质量，很难确定。定。r设每条语句执行一次所需时间为单位时间，设每条语句执行一次所需时间为单位时间，则则一个算法的运行时间一个算法的

29、运行时间就是该算法中所有语就是该算法中所有语句的频度之和。句的频度之和。38-412n3 + 3n2 + 2n +1n例例 求两个求两个 n 阶方阵的乘积阶方阵的乘积 C = A B void MatrixMultiply ( int A , int B , int C , int n ) for ( int i = 0; i n; i+ ) n+1 for ( int j = 0; j n; j+ ) n(n+1) Cij = 0; n2 for ( int k = 0; k n; k+ ) n2(n+1) Cij = Cij + Aik * Bkj; n3 38-42渐进时间复杂度渐进时间

30、复杂度 大大O表示法表示法n算法中所有语句的频度之和是矩阵阶数算法中所有语句的频度之和是矩阵阶数 n 的函的函数数 T(n) = 2n3 + 2n2 + 2n +1n称称 n 是问题的规模。则时间复杂度是问题的规模。则时间复杂度 T(n) 是问是问题规模题规模 n 的函数。的函数。n当当 n 趋于无穷大时，称时间复杂度的数量级为趋于无穷大时，称时间复杂度的数量级为算法的渐进时间复杂度算法的渐进时间复杂度 T(n) = O(n3) 算法的算法的大大O表示表示n大大O表示表明当表示表明当n时，时，T(n)的变化趋势。的变化趋势。38-43n大大O表示法的加法规则（针对并列程序段）表示法的加法规则（

31、针对并列程序段） T1(n) = O( f (n) ) T2(m) = O( g (m) ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)n例如，有三段并列程序段例如，有三段并列程序段 x = 0; y = 0; T1(n) = O(1) for ( int k = 0; k n; k + ) x +; T2(n) = O(n) for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +; T3(n) = O(n2)并列并列38-44n整个程序的渐进时间复杂性为整个程序的渐进时间复杂性为

32、T(n) = T1(n)+T2(n)+T3(n) = O(max(1, n, n2) = = O(n2)n大大O表示法的乘法规则（针对嵌套程序段）表示法的乘法规则（针对嵌套程序段）T1(n) = O( f (n) ) T2(m) = O( g (m) ) T(n, m) = T1(n)T2(m) = O(f (n)g (m)n例如，一个选择排序程序，算法思路为：共循环例如，一个选择排序程序，算法思路为：共循环 n-1 次，循环变量次，循环变量 i 从从 1 到到 n-1，每次循环从，每次循环从 i 到到 n 选择最小者，将其对调到第选择最小者，将其对调到第 i 个元素位置。个元素位置。嵌套嵌套

33、38-45void SelectSort ( int A , int n ) / n 是表当前长度是表当前长度 for ( i = 0; i n-1; i+ ) k = i; for ( j = i+1; j n; j+ ) if ( Aj Ak ) k = j; if ( k != i ) Swap(Ak, Ai ); /一趟比较一趟比较 38-46n渐进时间复杂度渐进时间复杂度 O(f (n)*g (n) = O(n2)201ninnin21)()(-SelectSort n- -1趟趟 T1(n) = O(n)选最小者选最小者 Ak n-i-1次比较次比较交换交换 swap(Ak, Ai

34、 1次比较次比较38-47nc log2n n nlog2n n2 n3 2n 3n = 0 & Ai != k ) i-; return i;n算法的语句算法的语句 i-的频度不仅与的频度不仅与 n 有关，还与有关，还与 A 中各元素的取值，以及中各元素的取值，以及 k 的取值有关。的取值有关。38-49算法分析例题算法分析例题例题例题1. 算法的时间复杂度与（算法的时间复杂度与（ ）有关。）有关。A. 问题规模问题规模 B. 计算机硬件的运行速度计算机硬件的运行速度C. 源程序的长度源程序的长度 D. 编译后执行程序的编译后执行程序的质量质量解答：解答：A。算法的具体执行时间与计算机硬件的

35、运。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的质量有关，但行速度、编译产生的目标程序的质量有关，但这属于事后测量。算法的时间复杂度的度量属这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。于事前估计，与问题的规模有关。38-50例题例题2. 某算法的时间复杂度是某算法的时间复杂度是O(n2)，表明该算法，表明该算法（ ）。）。A. 问题规模是问题规模是n2 B. 问题规模与问题规模与n2成正比成正比C. 执行时间等于执行时间等于n2 D. 执行时间与执行时间与n2成正比成正比解答：解答：D。算法的的时间复杂度是。算法的的时间复杂度是O(n2)，这是设定，

36、这是设定问题规模为问题规模为 n 的分析结果，所以的分析结果，所以A、B 都不对；都不对；它也不表明执行时间等于它也不表明执行时间等于n2，它只表明算法的，它只表明算法的执行时间执行时间T(n)c n2（c为比例常数）。为比例常数）。有的算法，如有的算法，如n n矩阵的转置，时间复杂度为矩阵的转置，时间复杂度为O(n2)，不表明问题规模是，不表明问题规模是n2。38-51例题例题3. 下面说法中错误的是（下面说法中错误的是（ ）。）。 算法原地工作的含义是指不需要任何额外的算法原地工作的含义是指不需要任何额外的辅助辅助空间空间 在相同问题规模在相同问题规模 n 下，时间复杂度为下，时间复杂度为

37、O(n)的算的算法总是优于时间复杂度为法总是优于时间复杂度为O(2n)的算法的算法 所谓时间复杂度是指在最坏情形下估算算法所谓时间复杂度是指在最坏情形下估算算法执行执行时间的一个上界时间的一个上界 同一个算法，实现语言的级别越高，执行效同一个算法，实现语言的级别越高，执行效率越率越低低A. B. C. D. 解答：解答：A。算法原地工作的含义指空间复杂度。算法原地工作的含义指空间复杂度O(1)38-52例题例题4. 有实现同一功能的两个算法有实现同一功能的两个算法A1和和 A2，其中，其中A1 的渐进时间复杂度是的渐进时间复杂度是T1(n) = O(2n)，A2 的渐的渐进时间复杂度是进时间复

38、杂度是T2(n) = O(n2)。仅就时间复杂。仅就时间复杂度而言，具体分析这两个算法哪个好。度而言，具体分析这两个算法哪个好。解答：比较算法好坏需比较两个函数解答：比较算法好坏需比较两个函数2n和和n2。当当n = 1时，时，21 12，算法，算法A2好于好于A1当当n = 2时，时，22 = 22，算法，算法A1与与A2相当相当当当n = 3时，时，23 42，算法，算法A2好于好于A1当当n 4时，时，2n n2，算法，算法A2好于好于A1当当n时，算法时，算法A2在时间上显然优于在时间上显然优于A1。38-53例题例题5 设设n是描述问题规模的非负整数，下面程序是描述问题规模的非负整数

39、，下面程序片段的时间复杂度是片段的时间复杂度是x = 2;while ( x n/2 ) x = 2*x;A. O(log2n)B. O(n) C. O(nlog2n) D. O(n2)解答：选解答：选A。找关键操作，即最内层循环中的执行。找关键操作，即最内层循环中的执行语句语句 x = 2*x。因为每次循环。因为每次循环x都成倍增长，设都成倍增长，设 x = 2k n/2，2k+1 n，则，则k log2n-1，实际，实际while循环循环内的语句执行了内的语句执行了log2n-2次。次。 38-54例题例题6 求整数求整数n（n0）阶乘的算法如下，其时间复）阶乘的算法如下，其时间复杂度是杂度是 int fact ( int n ) if ( n = 1 ) return 1; return n*fact ( n-1 ); A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)解答：选解答：选B。因为。因为T(1) = 1，T(n) = 1+T(n-1) = 1+(1+T(n-2) = 2+(1+T(n-3) = 3+(1+T(n-4) = = (n-1)+T(1) = n。计算计算fact(n-1)计算计算* *