数据结构选讲DATASTRUCTURE.ppt

《数据结构选讲DATASTRUCTURE.ppt》由会员分享，可在线阅读，更多相关《数据结构选讲DATASTRUCTURE.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构选讲DATASTRUCTURE Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望课程内容：课程内容：计算机软件的基础知识计算机软件的基础知识数据结构数据结构课时安排：课时安排：数据结构数据结构32学时学时教教 材：材：严蔚敏，吴伟民严蔚敏，吴伟民.数据结构数据结构.北京：清华大学出版社，北京：清华大学出版社，1997.参考书：参考书：数据结构习题与解析（数据结构习题与解析（C语言篇）语言篇）李春葆李春葆数据结构题集数据结构题集 严蔚敏，吴伟民严蔚敏，吴伟民

2、数据结构算法与应用数据结构算法与应用C+语言描述语言描述（英文版）（英文版）Sartaj Sahni McGraw-Hill&机械工业出版社机械工业出版社2022/12/32l l 数据结构的基本概念数据结构的基本概念l l 数据类型和抽象数据类型数据类型和抽象数据类型l l C语言的数据类型语言的数据类型l l 用用C语言描述算法的注意事项语言描述算法的注意事项l l 算法设计目标和算法效率度量算法设计目标和算法效率度量第一章第一章 绪绪 论论2022/12/331.1 1.1 数据结构的基本概念数据结构的基本概念数据：数据：数据是信息的载体，是描述客观事物的数据是信息的载体，是描述客观事物

3、的数、字符、以及所有能输入到计算机中，被计数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。算机程序识别和处理的符号的集合。数值性数据数值性数据 非数值性数据非数值性数据数据对象：数据对象：数据的子集。具有相同性质的数据数据的子集。具有相同性质的数据成员（数据元素）的集合。成员（数据元素）的集合。整数数据对象整数数据对象 N=0,1,2,学生数据对象学生数据对象:初等项（不可分割）、组初等项（不可分割）、组合项（可再划分）合项（可再划分）2022/12/34数据元素：数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位）数据类型数据类型：具

4、有相同性质的计算机数据集合及在这个集合上的一组操作。数据结构：数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure=D,R 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。2022/12/35数据结构依据视点的不同，分为数据逻辑结构和数据结构依据视点的不同，分为数据逻辑结构和物理结构：物理结构：u逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。u物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。u关系：物理结构是逻辑数据的存

5、储映象2022/12/36逻辑结构：u线性结构u非线性结构物理结构：u顺序存储u链接存储u索引存储u散列存储2022/12/37“学生”表格2022/12/38“课程”表格2022/12/39线性结构中各数据成员之间的线性关系线性结构中各数据成员之间的线性关系:有直接前驱和有直接前驱和直接后继直接后继(除最前、最后一个元素除最前、最后一个元素)例：电话号码查询问题例：电话号码查询问题方法方法1 1：顺序存储，顺序查找：顺序存储，顺序查找2022/12/310方法方法2 2：有序顺序存储，二分查找：有序顺序存储，二分查找姓名姓名地址地址李1李2张1张2王1王22022/12/311方法方法3 3

6、：部分有序，建立索引表：部分有序，建立索引表姓名姓名地址地址李1李2张1张2王1王2姓姓地址地址李张2022/12/312非线性结构中各数据成员之间的没有线性关系非线性结构中各数据成员之间的没有线性关系:前驱和前驱和后继可能多于一个后继可能多于一个 选课单包含如下信息 学 号 课程编号 成 绩 时 间 学生选课系统中实体构成的网状关系2022/12/313UNIX文件系统的系统结构图2022/12/314树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树2022/12/315堆结构“最大最大”堆堆 “最小最小”堆堆2022/12/316图结构图结构 网络结构网络结构2022/12/317

7、例：田径赛的时间安排问题例：田径赛的时间安排问题姓名姓名项目项目1项目项目2项目项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M跳高跳远标枪铅球200M100M1 1、任一选手所选中的项目中应该两两有边相连；、任一选手所选中的项目中应该两两有边相连；2 2、任一两个有边相连的顶点颜色（时间）不能相同。、任一两个有边相连的顶点颜色（时间）不能相同。2022/12/318uu在解决问题时可能遇到的典型的逻辑在解决问题时可能遇到的典型的逻辑结构（数据结构）结构（数据结构）uu逻辑结构的存储映象（存储实现）逻辑结构的存储映象（存储实现）uu数据结构的相

8、关操作及其实现。数据结构的相关操作及其实现。2022/12/3191.2 数据类型和抽象数据类型数据类型数据类型 定义：定义：一个数据的集合一个数据的集合,以及定义于这个以及定义于这个数据集合上的一组操作的总称。数据集合上的一组操作的总称。C C语言中的数据类型语言中的数据类型 基本数据类型、基本数据类型、指针类型、数组类型、结指针类型、数组类型、结构体类型、公用体类型、枚举类型构体类型、公用体类型、枚举类型2022/12/320抽象数据和抽象数据类型(ADTs:Abstract Data Types)由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型由由基本的数据类

9、型基本的数据类型组成组成,并包括并包括一一组相关的服务组相关的服务（或称操作）（或称操作）信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现，使用与实现相分离（物理实现封装）相分离（物理实现封装）2022/12/321ADT：抽象数据类型名数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义抽象数据类型的定义：抽象数据类型的定义：操作名（参数表）操作结果：操作结果描述基本操作的定义：基本操作的定义：2022/12/322抽抽象象数数据据类类型型2022/12/323好的和坏的数据结构？好的和坏的数据结构？如果一个如果一个如果一个如果一个DSDSDSDS可以通过某种可以通过

10、某种可以通过某种可以通过某种“线性规则线性规则线性规则线性规则”被转化为线性的被转化为线性的被转化为线性的被转化为线性的DSDSDSDS（例如线性表），则称它为（例如线性表），则称它为（例如线性表），则称它为（例如线性表），则称它为好的好的好的好的DSDSDSDS。好的。好的。好的。好的DSDSDSDS通常对应于好通常对应于好通常对应于好通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为的（高效的）算法。这是由计算机的计算能力决定的，因为的（高效的）算法。这是由计算机的计算能力决定的，因为的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，

11、因此如果没有计算机本质上只能存取逻辑连续的内存单元，因此如果没有计算机本质上只能存取逻辑连续的内存单元，因此如果没有计算机本质上只能存取逻辑连续的内存单元，因此如果没有线性化的结构逻辑上是不可计算的。线性化的结构逻辑上是不可计算的。线性化的结构逻辑上是不可计算的。线性化的结构逻辑上是不可计算的。树是好的树是好的树是好的树是好的DSDSDSDS它有非常简单而高效的线性化规则，因此它有非常简单而高效的线性化规则，因此它有非常简单而高效的线性化规则，因此它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很可以利用树设计出许多非常高效的算法。树的实现和使用都很可以

12、利用树设计出许多非常高效的算法。树的实现和使用都很可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中简单，但可以解决大量特殊的复杂问题，因此树是实际编程中简单，但可以解决大量特殊的复杂问题，因此树是实际编程中简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性最重要和最有用的一种数据结构。树的结构本质上有递归的性最重要和最有用的一种数据结构。树的结构本质上有递归的性最重要和最有用的一种数据结构。树的结构本质上有递归的性质。质。质。质。2022/12/3241.3 C语言的数据类型1

13、 1 1 1、基本数据类型、基本数据类型、基本数据类型、基本数据类型int short;long;unsigned int short;long;unsigned int short;long;unsigned int short;long;unsigned float float;double;long double float float;double;long double float float;double;long double float float;double;long double 2 2 2 2、指针类型、指针类型、指针类型、指针类型3 3 3 3、数组类型数组类型数组类

14、型数组类型4 4 4 4、字符串、字符串、字符串、字符串5 5 5 5、结构体类型、结构体类型、结构体类型、结构体类型6 6 6 6、共用体类型、共用体类型、共用体类型、共用体类型7 7 7 7、枚举类型、枚举类型、枚举类型、枚举类型8 8 8 8、自定义类型、自定义类型、自定义类型、自定义类型2022/12/3251.4 用C语言编写算法的注意事项1 1 1 1、避免使用出现二义性的表达式、避免使用出现二义性的表达式、避免使用出现二义性的表达式、避免使用出现二义性的表达式i+;i+;i+;i+;i=+i;i=+i;i=+i;i=+i;i=1;j =i+i-;i=1;j =i+i-;i=1;j

15、 =i+i-;i=1;j =i+i-;2 2 2 2、避免使用转向语句、避免使用转向语句、避免使用转向语句、避免使用转向语句3 3 3 3、避免使用预处理避免使用预处理避免使用预处理避免使用预处理4 4 4 4、避免函数返回值隐含说明、避免函数返回值隐含说明、避免函数返回值隐含说明、避免函数返回值隐含说明2022/12/3261.5 算法设计目标和算法效率度量算法设计目标和算法效率度量uu定义：定义：一个有穷的指令集，这些指令为解决某一一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特定任务规定了一个运算序列uu特性：特性：输入输入 有有0 0个或多个输入个或多个输入输出输出 有

16、一个或多个输出有一个或多个输出(处理结果处理结果)确定性确定性 每步定义都是确切、无歧义的每步定义都是确切、无歧义的 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束 有效性有效性 每一条运算应足够基本每一条运算应足够基本算法的描述算法的描述:c+,c,PASCAL等语言等语言2022/12/327算法有这样一些算法有这样一些算法有这样一些算法有这样一些特点：特点：特点：特点：1 1、有有有有穷穷穷穷性性性性：要要要要求求求求序序序序列列列列中中中中的的的的指指指指令令令令是是是是有有有有限限限限的的的的；每每每每条条条条指指指指令令令令的的的的执执执执行行行行包包包包含含含含有

17、有有有限限限限的的的的工工工工作作作作量量量量；整整整整个个个个指指指指令令令令序序序序列列列列的的的的执执执执行行行行在在在在有有有有限限限限的的的的时时时时间内结束。间内结束。间内结束。间内结束。2 2、确确确确定定定定性性性性：算算算算法法法法中中中中的的的的每每每每一一一一个个个个步步步步骤骤骤骤都都都都必必必必须须须须是是是是确确确确定定定定的的的的，而而而而不不不不应当含糊、模棱两可。应当含糊、模棱两可。应当含糊、模棱两可。应当含糊、模棱两可。3 3、有零个或多个输入、有零个或多个输入、有零个或多个输入、有零个或多个输入4 4、有一个或多个输出、有一个或多个输出、有一个或多个输出、

18、有一个或多个输出5 5、有有有有效效效效性性性性：算算算算法法法法中中中中的的的的每每每每一一一一个个个个步步步步骤骤骤骤都都都都应应应应当当当当能能能能被被被被有有有有效效效效的的的的执执执执行行行行，并并并并得得得得到到到到确确确确定定定定的的的的结结结结果果果果。例例例例如如如如：被被被被零零零零除除除除的的的的计计计计算算算算动动动动作作作作是是是是不不不不能能能能被被被被有效执行的。有效执行的。有效执行的。有效执行的。2022/12/328uu设计算法的基本方法设计算法的基本方法设计算法的基本方法设计算法的基本方法:把一个具体问题转变成一个算把一个具体问题转变成一个算把一个具体问题转

19、变成一个算把一个具体问题转变成一个算法法法法uu事例学习：事例学习：事例学习：事例学习：选择排序问题选择排序问题选择排序问题选择排序问题uu明确问题：明确问题：明确问题：明确问题：非递减排序非递减排序非递减排序非递减排序uu解决方案：解决方案：解决方案：解决方案：逐个选择最小数据逐个选择最小数据逐个选择最小数据逐个选择最小数据uu算法框架：算法框架：算法框架：算法框架：for(intfor(int i=i=0;0;in-in-2;2;i+i+)/)/n n-1-1趟趟趟趟 从从从从a a i i 检查到检查到检查到检查到a a n-n-1;1;若最小的整数在若最小的整数在若最小的整数在若最小的

20、整数在a a k k,交换交换交换交换a a i i 与与与与a a k k;uu细化程序：细化程序：细化程序：细化程序：程序程序程序程序 SelectSortSelectSort 算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 2022/12/329性能分析与度量u算法的性能标准算法的性能标准u算法的后期测试算法的后期测试u算法的事前估计算法的事前估计2022/12/330分析评价算法时应考虑的分析评价算法时应考虑的分析评价算法时应考虑的分析评价算法时应考虑的因素：因素：因素：因素：1 1、正正正正确确确确性性性性 在在在在给给给给定定定定有有有有效效效效的的的的输输输输入入入入数数

21、数数据据据据后后后后，算算算算法法法法经经经经过过过过有有有有穷穷穷穷时时时时间间间间的的的的计算能给出正确的答案。计算能给出正确的答案。计算能给出正确的答案。计算能给出正确的答案。2 2、复杂度、复杂度、复杂度、复杂度 时间复杂度时间复杂度时间复杂度时间复杂度3 3、简单性、简单性、简单性、简单性4 4、最最最最优优优优性性性性 算算算算法法法法A A是是是是最最最最优优优优的的的的是是是是指指指指：在在在在给给给给定定定定问问问问题题题题的的的的所所所所有有有有算算算算法法法法中中中中，A A执行的进步运算次数最少执行的进步运算次数最少执行的进步运算次数最少执行的进步运算次数最少5 5、可

22、读性、可读性、可读性、可读性 要求算法易于理解，便于分析要求算法易于理解，便于分析要求算法易于理解，便于分析要求算法易于理解，便于分析6 6、可可可可修修修修改改改改可可可可扩扩扩扩展展展展性性性性 如如如如果果果果问问问问题题题题P P 的的的的一一一一个个个个算算算算法法法法是是是是A A，为为为为了了了了解解解解答答答答一一一一个个个个与与与与P P类类类类似似似似的的的的问问问问题题题题，希希希希望望望望对对对对A A稍稍稍稍做做做做改改改改动动动动就就就就可可可可正正正正确确确确运运运运行行行行，如如如如算算算算法法法法A A满足这一点，则说满足这一点，则说满足这一点，则说满足这一点

23、，则说A A的可修改性好。的可修改性好。的可修改性好。的可修改性好。2022/12/331与算法效率有关的因素与算法效率有关的因素程序设计语言程序设计语言编译的代码质量编译的代码质量机器执行指令的速度机器执行指令的速度问题的规模问题的规模2022/12/332求解同样一个问题可能会有许多不同的算法，如何评价这些算法的好坏呢？首先算法必须是正确的。此外还需考虑：1、算法易于理解，易于编程（在计算机上实现），易于调试。2、要求算法高效，节省时间与空间。一个算法运行所需时间的长短、空间的大小具有非常重要的意义。时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。2022/12/333算算算算

24、法法法法高高高高效效效效与与与与算算算算法法法法易易易易理理理理解解解解、易易易易编编编编程程程程之之之之间间间间也也也也有有有有一一一一种种种种制制制制约关系约关系约关系约关系这两个要求有时互相矛盾。因此，对反复运行的这两个要求有时互相矛盾。因此，对反复运行的这两个要求有时互相矛盾。因此，对反复运行的这两个要求有时互相矛盾。因此，对反复运行的算法，首先考虑的是高效性，对偶尔运行的算法，算法，首先考虑的是高效性，对偶尔运行的算法，算法，首先考虑的是高效性，对偶尔运行的算法，算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程（以排序为例则需突出算法易理解和易编程（以排序为例则

25、需突出算法易理解和易编程（以排序为例则需突出算法易理解和易编程（以排序为例 冒泡排序和快速排序）。冒泡排序和快速排序）。冒泡排序和快速排序）。冒泡排序和快速排序）。2022/12/334我们重点考虑时间因素。我们重点考虑时间因素。我们重点考虑时间因素。我们重点考虑时间因素。一一一一个个个个算算算算法法法法所所所所耗耗耗耗费费费费的的的的时时时时间间间间，应应应应该该该该是是是是该该该该算算算算法法法法中中中中每每每每条条条条语语语语句句句句的的的的执执执执行行行行时时时时间间间间之之之之和和和和，而而而而每每每每条条条条语语语语句句句句的的的的执执执执行行行行时时时时间间间间又又又又是是是是该

26、该该该语语语语句句句句的的的的执执执执行行行行次次次次数数数数（频频频频度度度度）与与与与该该该该语语语语句句句句执执执执行行行行一一一一次次次次所所所所需时间的乘积。需时间的乘积。需时间的乘积。需时间的乘积。我我我我们们们们假假假假定定定定，每每每每条条条条语语语语句句句句一一一一次次次次执执执执行行行行的的的的时时时时间间间间都都都都是是是是相相相相同同同同的的的的，为为为为单单单单位位位位时时时时间间间间。这这这这样样样样我我我我们们们们对对对对时时时时间间间间的的的的分分分分析析析析就就就就可可可可以以以以独独独独立立立立于软硬件系统。于软硬件系统。于软硬件系统。于软硬件系统。2022

27、/12/335 我我我我们们们们将将将将算算算算法法法法求求求求解解解解问问问问题题题题的的的的输输输输入入入入量量量量称称称称为为为为问问问问题题题题的的的的规规规规模模模模，用用用用一一一一个个个个整整整整数数数数来来来来表表表表示示示示，一一一一个个个个算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度度度度是是是是该该该该算算算算法法法法的的的的时时时时间间间间耗耗耗耗费费费费，一般地说，时间复杂度是问题规模的函数一般地说，时间复杂度是问题规模的函数一般地说，时间复杂度是问题规模的函数一般地说，时间复杂度是问题规模的函数 T(n)T(n)。当当当当问问问问题题题题的的的的规规规

28、规模模模模n n 趋趋趋趋于于于于无无无无穷穷穷穷大大大大时时时时，把把把把时时时时间间间间复复复复杂杂杂杂度度度度T(T(n n)的的的的数数数数量量量量级级级级（阶阶阶阶）称称称称为为为为算算算算法法法法的的的的渐渐渐渐进进进进时时时时间间间间复复复复杂杂杂杂度度度度（有有有有时时时时简简简简称称称称为为为为时时时时间间间间复杂度复杂度复杂度复杂度）。）。）。）。严严严严格格格格的的的的数数数数学学学学定定定定义义义义为为为为：若若若若T(T(n n)和和和和 f(f(n n)是是是是定定定定义义义义在在在在正正正正整整整整数数数数集集集集合合合合上上上上的的的的两两两两个个个个函函函函数

29、数数数，当当当当存存存存在在在在两两两两个个个个正正正正的的的的乘乘乘乘数数数数C C和和和和n n0 0时时时时，使使使使得得得得对对对对所有的所有的所有的所有的成立，则成立，则成立，则成立，则都有都有都有都有这时称这时称这时称这时称T(n)T(n)的时间复杂度为的时间复杂度为的时间复杂度为的时间复杂度为f(n)f(n)数量级。数量级。数量级。数量级。2022/12/336算法运行所需要的时间与两个因素有关：算法运行所需要的时间与两个因素有关：1、问题实例的大小问题实例的大小 （如（如1000个数的排序）；个数的排序）；2 2、实例的具体情况实例的具体情况 （如（如10001000个数的排列

30、情况）个数的排列情况）2022/12/337算法分析算法分析算法分析算法分析1 1、假假假假定定定定每每每每条条条条语语语语句句句句的的的的执执执执行行行行时时时时间间间间为为为为单单单单位位位位时时时时间间间间。算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度度度度是是是是该该该该算算算算法法法法中中中中所所所所有有有有语语语语句句句句的的的的执执执执行行行行频频频频度度度度之和。之和。之和。之和。2022/12/338例：求两个方阵的乘积例：求两个方阵的乘积例：求两个方阵的乘积例：求两个方阵的乘积 C CA*BA*Bdefine n define n 自然数自然数自然数自然数MA

31、TRIXMLT(float Ann,float Bnn,float Cnn)MATRIXMLT(float Ann,float Bnn,float Cnn)int i,j,k;int i,j,k;for(i=0;in;i+)/for(i=0;in;i+)/for(j=0;jn;j+)/for(j=0;jn;j+)/Cij=0;/Cij=0;/for(k=0;kn;k+)/for(k=0;kn;k+)/Cij=Aik*Bkj /Cij=Aik*Bkj /2022/12/3392 2、一般情况下，对步进循环语句只考虑循环体语句的执一般情况下，对步进循环语句只考虑循环体语句的执一般情况下，对步进循环

32、语句只考虑循环体语句的执一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中部长加一、终值判别、循环转行次数，而忽略该语句中部长加一、终值判别、循环转行次数，而忽略该语句中部长加一、终值判别、循环转行次数，而忽略该语句中部长加一、终值判别、循环转移等成份。因此，当有若干个循环语句时，算法的时间移等成份。因此，当有若干个循环语句时，算法的时间移等成份。因此，当有若干个循环语句时，算法的时间移等成份。因此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频复杂度是由嵌套层数最多的循环语句中最内层语句的频复杂度是由嵌套层数最多的循环语句中最内层语句的频复

33、杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。度所决定的。度所决定的。度所决定的。2022/12/340例：例：例：例：x=0;y=0;x=0;y=0;for(k=1;k=n;k+)for(k=1;k=n;k+)x+;x+;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=n;j+)/n*n for(j=1;j=n;j+)/n*n y+;y+;y+;y+;一般情况下，对步进循环语句只需考虑循环体一般情况下，对步进循环语句只需考虑循环体一般情况下，对步进循环语句只需考虑循环体一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加中

34、语句的执行次数，而忽略循环体中步长加中语句的执行次数，而忽略循环体中步长加中语句的执行次数，而忽略循环体中步长加1 1 1 1、终值判断、控制转移等成分。、终值判断、控制转移等成分。、终值判断、控制转移等成分。、终值判断、控制转移等成分。2022/12/341例：例：例：例：x=1;x=1;for(i=1;i=n;i+)for(i=1;i=n;i+)for(j=1;j=i;j+)for(j=1;j=i;j+)for(k=1;k=j;k+)for(k=1;k=0)&Ai!=k)while(i=0)&Ai!=k)j-;j-;return i;return i;此问题不仅与规模此问题不仅与规模此问题

35、不仅与规模此问题不仅与规模 n n n n 有关，而且与数组有关，而且与数组有关，而且与数组有关，而且与数组A A A A中各元中各元中各元中各元素的取值有关。素的取值有关。素的取值有关。素的取值有关。2022/12/345例：例：例：例：fact(n)fact(n)if(n=1)return 1;if(n=1)return 1;else return(n*fact(n-1);else return(n*fact(n-1);设设设设 fact fact 的运行时间函数为的运行时间函数为的运行时间函数为的运行时间函数为T T（n n），），），），则有则有则有则有2022/12/3462022/12/347常数阶常数阶常数阶常数阶对数阶对数阶对数阶对数阶线性阶线性阶线性阶线性阶线性对数阶线性对数阶线性对数阶线性对数阶平方阶平方阶平方阶平方阶立方阶立方阶立方阶立方阶K K K K次方阶次方阶次方阶次方阶指数阶指数阶指数阶指数阶常见的时间复杂度，按数量级递增排序：常见的时间复杂度，按数量级递增排序：常见的时间复杂度，按数量级递增排序：常见的时间复杂度，按数量级递增排序：2022/12/348算法的后期测试在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数 time()测定算法完成某一功能所花费的时间测定算法完成某一功能所花费的时间2022/12/349