数据结构c语言1课件

数据结构

DataStructures任课教师：刘立芳课件Email：xd_ds@126.com(password:xd123456)作业Email：xd_ds_hw@126.com数据结构

DataStructures任课教师：刘立芳课1课程性质：必修考核方式：机试+笔试（作业10%+上机20%+机试30%+笔试40%）教材：《数据结构》严蔚敏清华大学出版社《数据结构题集》严蔚敏清华大学出版社学习要求：①要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭；②上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页；③上机程序要现场验收、严禁拷贝他人程序及报告；课程性质：必修学习要求：2数据结构基础数据结构应用数据结构非线性结构线性结构线性表栈队列串数组广义表树二叉树图查找内部排序外部排序文件动态存储管理课程的内容框架数据结构基础数据结构应用数据结构非线性结构线性结构线栈队串数3很强的理论性很强的概念性 很强的连贯性

全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。容易混淆性课程特点很强的理论性课程特点4本章内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求第一章绪论本章内容：第一章绪论5数据结构学科发展背景应用领域从科学计算到非数值计算起初数据结构中内容在其他课程中表述1968年美国唐.欧.克努特(DonaldE.Knuth)开创数据结构最初体系。在《计算机程序设计技巧》第一卷《基本算法》系统阐述数据的逻辑结构、存储结构及操作数据结构的两个发展方向：面向专门领域特殊问题的数据结构；从抽象数据类型的观点讨论数据结构1.1什么是数据结构数据结构学科发展背景1.1什么是数据结构6数据结构学科的地位综合性的专业基础课介于数学、计算机硬件和计算机软件之间的核心课程前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程人工智能等数据结构学科的地位综合性的专业基础课前期课程数据结构计算机基7计算机的解题步骤1.1什么是数据结构（定义）

具体问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。计算机的解题步骤1.1什么是数据结构（定义）具体数学抽象8非数值型计算问题举例：学籍管理(信息处理类问题)IS19男张立95004IS19女刘晨95002MA18女王敏95003CS20男李勇95001SdeptSageSsexSnameSno430PASCAL语言7260编译原理6440数据结构5360操作系统4430信息系统32120数学2430数据库1CcreditCpnoCnameCno9500295002950019500195001Snoc5c2c4c2c1Cno7390886592Grade学生信息：课程：学生选课：此类问题已独立成为数据库学科，在《数据结构》中主要在文件一章有所涉及。非数值型计算问题举例：IS19男张立95004IS19女刘晨9非数值型计算问题举例：博弈类问题S0S11S10S1n……………………SK1Sqr……SK1Sqr……SK1Sqr……此类问题中的数据结构可用树描述。非数值型计算问题举例：S0S11S10S1n……10田径赛的时间安排问题

6个项目：A、B、C、D、E、F。每人至多参加3项。姓名项目1项目2项目3小张ABE小刘CD小李CEF小红DFA小强BFABDFECABDFEC非数值型计算问题举例：此类问题中的数据结构可用图描述。田径赛的时间安排问题

6个项目：A、B、C、D、E、F11什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象间的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义和实现相应运算的学科。1.1什么是数据结构（定义）什么是数据结构1.1什么是数据结构（定义）12基本概念数据(Data)：指所有能输入到计算机中并被计算机程序加工处理的符号的总称。1.2基本概念和术语能被计算机识别、存储和加工处理的信息的载体。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。基本概念1.2基本概念和术语能被计算机识别、存储和加工处13基本概念数据元素(DataElement)：数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。数据项(DataItem)：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京………………数据项记录表:学籍表基本概念学号姓名性别籍贯出生年月住址101赵红玲女河北19814基本概念数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。综上所述，再分析数据概念：数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。基本概念综上所述，再分析数据概念：数据结构(DataSt151.逻辑结构内涵：数据元素之间的关系，或称为“结构”。分类：

*集合：松散的关系

*线性结构：一对一的关系

*树形结构：一对多的关系

*网状结构：多对多的关系描述性定义： 用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。形式化定义： Data_Structure=（D，S） D={数据元素的有限集合} S={D上关系的有限集合}数据结构的内容1.逻辑结构数据结构的内容16例：设数据结构描述如下： Data_Structure=(D,R) D={1,2,3,4,5,6} R={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>} 画出其逻辑结构图？例：设数据结构描述如下：172.存储结构(物理结构)： 数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：顺序存储结构链式存储结构描述方式：数据元素用高级语言中的“数据类型”来描述数据元素间的关系用数据元素间的存储相对位置关系(顺序存储结构)或在数据元素上增加指针(链式存储结构)来表达2.存储结构(物理结构)：183.数据的运算对数据施加的操作，通过算法描述。算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。抽象运算定义在逻辑结构上，而实现在存储结构上。3.数据的运算19数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合20数据类型(DataType)数据类型是一组性质相同的值的集合以及定义在这个值集上的一组操作的总称。该类型的取值范围，该类型中可允许使用的一组运算。数据类型是数据结构在程序设计语言中的实现。原子类型结构数据类型数据类型(DataType)数据类型是数据结构在程序设计211.3抽象数据类型的表示与实现抽象数据类型(AbstractDataType，ADT) ADT指一个数学模型以及定义在该模型上的一组操作。由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（即算法的顶层设计与底层实现分离）1.3抽象数据类型的表示与实现抽象数据类型(Abstrac22抽象数据类型形式化定义 ADT=（D，S，P） D={数据对象} S={D上的关系集} P={对D的基本操作集}定义形式：ADT抽象数据类型名{ 数据对象：… 数据关系：… 基本操作：…}ADT抽象数据类型名抽象数据类型形式化定义23抽象数据类型示例ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3属于ElemSet}数据关系：R={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3) DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) ……}ADTTriplet抽象数据类型示例24类C语言书写的算法与C程序之间的差别：(1)算法中除形式参数外,变量不作定义，在C程序中必须定义；(2)算法中使用的元素类型(ElemType)没有定义，C程序中必须定义，常量OK、ERROR、OVERFLOW等在第一章统一定义；(3)算法中的比较运算符(equal、less)未作定义，C程序中必须定义；(4)必要的头文件(用作输入输出的stdio.h及内存申请的stdlib.h)，在C程序中必须包含。类C语言的描述语法 类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述。如：存储结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头的参数为引用参数；等等。类C语言书写的算法与C程序之间的差别：类C语言的描述语法251.4算法和算法分析算法内涵: 是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:有穷性：有穷步+有穷时间/每一步确定性：指令的语义无二义性可行性：算法能用基本操作完成输入：零个或多个输入输出：一个或多个输出1.4算法和算法分析算法26算法设计的要求正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求算法的描述方式自然语言程序设计语言流程图类高级语言（类C语言、类Pascal语言等）算法效率的考虑时间与空间算法设计的要求27算法时间效率的度量程序运行消耗时间取决于下列因素算法策略问题规模语言层次编译程序所产生的机器代码的质量机器执行指令的速度算法时间效率度量 算法时间效率在软硬件环境相同的情况下取决于问题的规模，即T(n)=f(n)。算法时间效率度量的基本做法 在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间效率的度量282个N*N矩阵相乘for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}n+1n(n+1)n2n2(n+1)n3语句频度：是指该语句在一个算法中重复执行的次数。2个N*N矩阵相乘for(i=1;i<=n;++i)29算法的时间复杂度算法中基本操作重复执行的次数是问题规模n的函数f(n)。算法的时间度量记作T(n)=O(f(n))。T(n)和f(n)是定义在正数集上的正函数，如果存在正的常数C和自然数M，使得当n≥M时有T(n)≤Cf(n)，则称函数T(n)当n充分大时上有界，且f(n)是它的一个上界，记为T(n)=O(f(n))。（OrderofMagnitude）。用“O”来表示数量级，所谓算法的时间复杂度，即是算法的时间量度，记作：T(n)=O(f(n))

算法的时间复杂度30（1）x=x+1；其时间复杂度为O(1)，我们称之为常量阶；（2）for(i=1;i<=n;i++)x=x+1;其时间复杂度为O(n)，我们称之为线性阶；（3）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;其时间复杂度为O(n2),我们称之为平方阶。（4）for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2，其时间复杂度为：O(n2)

此外算法还能呈现的时间复杂度有对数阶O(log2n),指数阶O(2n)等。（1）x=x+1；其时间复杂度为O(1)，我们称31数据结构中常用的时间复杂度频率计数O(1)常数阶O(n)线性阶O(n2)平方阶O(n3)立方阶O(2n)指数阶O(log2n)对数阶O(nlog2n)线性对数阶指数时间的关系为：O(2n)<O(n!)<O(nn)多项式阶O(nk)的算法我们称之为“好算法”数据结构中常用的时间复杂度频率计数指数时间的关系为：O(32大O的运算规则加法准则(并列程序段) a)前提：T1(m)=O(f(m));T2(n)=O(g(n)) 结论：T(n)=T1+T2=O(max(f(m),g(n))) b)前提：T1(n)=O(f(n));T2(n)=O(g(n)) 结论：T(n)=T1+T2=O(f(n)+g(n))乘法准则(嵌套程序段) 前提：T1(n)=O(f(n));T2(n)=O(g(n)) 结论：T(n)=T1*T2=O(f(n)*g(n))大O的运算规则33例如：下列程序段：for(i=1;i<n;i++)for(j=i;j<=n;j++)x++;语句x++的执行频度为n+(n-1)+(n-2)+…+3+2+1=n(n+1)/2而该语句执行次数关于n的增长率为n2,即时间复杂度为O(n2)。例如：下列程序段：34最坏、最好和平均时间复杂度算法中基本操作重复执行的次数还随所处理的数据集的状态有关。算法的空间复杂度关于算法的存储空间需求，类似于算法的时间复杂度，我们采用空间复杂度作为算法所需存储空间的量度，记作：S(n)=O(f(n))最坏、最好和平均时间复杂度算法的空间复杂度35数据结构逻辑结构存储结构数据运算（算法）线性结构（线性表、栈和队列、串）非线性结构（广义表、树、图、文件）链式存储结构顺序存储结构数据结构逻辑结构存储结构数据运算（算法）线性结构（线36练习例1：设逻辑结构图如下，试给出其数据结构表示。abcdef数据结构定义为：Data_Structure=(D,S)其中D={a,b,c,d,e,f}S={R}R={(a,b),(a,c),(c,d),(c,e),(c,f),(d,f)}

练习abcdef数据结构定义为：37例2：设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数，写出其时间复杂度。x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;例2：设n为正整数，利用大“O”记号，将下列程序段的执行时间38例3：计算机执行下面的语句时，语句S的执行次数（频度）为多少？写出其时间复杂度？for(i=1;i<n-1;i++)for(j=n;j>=i;j--)S;例3：计算机执行下面的语句时，语句S的执行次数（频度）为多少39例4：试说明下列计算过程是否是一个算法？（1）开始；（2）n<=0;（3）n++；（4）重复（3）；（5）结束；不具备算法的有穷性，不是一个算法。例4：试说明下列计算过程是否是一个算法？40voidexam1(){n=2;while(n%2==0)n=n+2;printf(“%d\n”,n);}voidexam2(){y=0;x=3/y;printf(“%d,%d\n”,x,y);}违反了有穷性。违反了可行性。voidexam1()voidexam2()违反了有穷性41作业《数据结构题集》P7：（3、8、9、17）作业《数据结构题集》42数据结构

DataStructures任课教师：刘立芳课件Email：xd_ds@126.com(password:xd123456)作业Email：xd_ds_hw@126.com数据结构

DataStructures任课教师：刘立芳课43课程性质：必修考核方式：机试+笔试（作业10%+上机20%+机试30%+笔试40%）教材：《数据结构》严蔚敏清华大学出版社《数据结构题集》严蔚敏清华大学出版社学习要求：①要独立思考，按时完成作业。在自己不会解答时可参考其他资料或他人答案，在分析别人的处理思路之后自己动手，鼓励相互讨论，严禁抄袭；②上机实验前应先就要处理的问题写出自己的解决思路和大纲，严禁在机房游戏、网上聊天、流览不相关的网页；③上机程序要现场验收、严禁拷贝他人程序及报告；课程性质：必修学习要求：44数据结构基础数据结构应用数据结构非线性结构线性结构线性表栈队列串数组广义表树二叉树图查找内部排序外部排序文件动态存储管理课程的内容框架数据结构基础数据结构应用数据结构非线性结构线性结构线栈队串数45很强的理论性很强的概念性 很强的连贯性

全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明。容易混淆性课程特点很强的理论性课程特点46本章内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求第一章绪论本章内容：第一章绪论47数据结构学科发展背景应用领域从科学计算到非数值计算起初数据结构中内容在其他课程中表述1968年美国唐.欧.克努特(DonaldE.Knuth)开创数据结构最初体系。在《计算机程序设计技巧》第一卷《基本算法》系统阐述数据的逻辑结构、存储结构及操作数据结构的两个发展方向：面向专门领域特殊问题的数据结构；从抽象数据类型的观点讨论数据结构1.1什么是数据结构数据结构学科发展背景1.1什么是数据结构48数据结构学科的地位综合性的专业基础课介于数学、计算机硬件和计算机软件之间的核心课程前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程人工智能等数据结构学科的地位综合性的专业基础课前期课程数据结构计算机基49计算机的解题步骤1.1什么是数据结构（定义）

具体问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。计算机的解题步骤1.1什么是数据结构（定义）具体数学抽象50非数值型计算问题举例：学籍管理(信息处理类问题)IS19男张立95004IS19女刘晨95002MA18女王敏95003CS20男李勇95001SdeptSageSsexSnameSno430PASCAL语言7260编译原理6440数据结构5360操作系统4430信息系统32120数学2430数据库1CcreditCpnoCnameCno9500295002950019500195001Snoc5c2c4c2c1Cno7390886592Grade学生信息：课程：学生选课：此类问题已独立成为数据库学科，在《数据结构》中主要在文件一章有所涉及。非数值型计算问题举例：IS19男张立95004IS19女刘晨51非数值型计算问题举例：博弈类问题S0S11S10S1n……………………SK1Sqr……SK1Sqr……SK1Sqr……此类问题中的数据结构可用树描述。非数值型计算问题举例：S0S11S10S1n……52田径赛的时间安排问题

6个项目：A、B、C、D、E、F。每人至多参加3项。姓名项目1项目2项目3小张ABE小刘CD小李CEF小红DFA小强BFABDFECABDFEC非数值型计算问题举例：此类问题中的数据结构可用图描述。田径赛的时间安排问题

6个项目：A、B、C、D、E、F53什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象间的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义和实现相应运算的学科。1.1什么是数据结构（定义）什么是数据结构1.1什么是数据结构（定义）54基本概念数据(Data)：指所有能输入到计算机中并被计算机程序加工处理的符号的总称。1.2基本概念和术语能被计算机识别、存储和加工处理的信息的载体。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。基本概念1.2基本概念和术语能被计算机识别、存储和加工处55基本概念数据元素(DataElement)：数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。数据项(DataItem)：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京………………数据项记录表:学籍表基本概念学号姓名性别籍贯出生年月住址101赵红玲女河北19856基本概念数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。综上所述，再分析数据概念：数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。基本概念综上所述，再分析数据概念：数据结构(DataSt571.逻辑结构内涵：数据元素之间的关系，或称为“结构”。分类：

*集合：松散的关系

*线性结构：一对一的关系

*树形结构：一对多的关系

*网状结构：多对多的关系描述性定义： 用自然语言描述相互之间存在一种或多种特定关系的数据元素的集合。形式化定义： Data_Structure=（D，S） D={数据元素的有限集合} S={D上关系的有限集合}数据结构的内容1.逻辑结构数据结构的内容58例：设数据结构描述如下： Data_Structure=(D,R) D={1,2,3,4,5,6} R={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>} 画出其逻辑结构图？例：设数据结构描述如下：592.存储结构(物理结构)： 数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：顺序存储结构链式存储结构描述方式：数据元素用高级语言中的“数据类型”来描述数据元素间的关系用数据元素间的存储相对位置关系(顺序存储结构)或在数据元素上增加指针(链式存储结构)来表达2.存储结构(物理结构)：603.数据的运算对数据施加的操作，通过算法描述。算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。抽象运算定义在逻辑结构上，而实现在存储结构上。3.数据的运算61数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合62数据类型(DataType)数据类型是一组性质相同的值的集合以及定义在这个值集上的一组操作的总称。该类型的取值范围，该类型中可允许使用的一组运算。数据类型是数据结构在程序设计语言中的实现。原子类型结构数据类型数据类型(DataType)数据类型是数据结构在程序设计631.3抽象数据类型的表示与实现抽象数据类型(AbstractDataType，ADT) ADT指一个数学模型以及定义在该模型上的一组操作。由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（即算法的顶层设计与底层实现分离）1.3抽象数据类型的表示与实现抽象数据类型(Abstrac64抽象数据类型形式化定义 ADT=（D，S，P） D={数据对象} S={D上的关系集} P={对D的基本操作集}定义形式：ADT抽象数据类型名{ 数据对象：… 数据关系：… 基本操作：…}ADT抽象数据类型名抽象数据类型形式化定义65抽象数据类型示例ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3属于ElemSet}数据关系：R={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3) DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) ……}ADTTriplet抽象数据类型示例66类C语言书写的算法与C程序之间的差别：(1)算法中除形式参数外,变量不作定义，在C程序中必须定义；(2)算法中使用的元素类型(ElemType)没有定义，C程序中必须定义，常量OK、ERROR、OVERFLOW等在第一章统一定义；(3)算法中的比较运算符(equal、less)未作定义，C程序中必须定义；(4)必要的头文件(用作输入输出的stdio.h及内存申请的stdlib.h)，在C程序中必须包含。类C语言的描述语法 类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述。如：存储结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头的参数为引用参数；等等。类C语言书写的算法与C程序之间的差别：类C语言的描述语法671.4算法和算法分析算法内涵: 是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:有穷性：有穷步+有穷时间/每一步确定性：指令的语义无二义性可行性：算法能用基本操作完成输入：零个或多个输入输出：一个或多个输出1.4算法和算法分析算法68算法设计的要求正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求算法的描述方式自然语言程序设计语言流程图类高级语言（类C语言、类Pascal语言等）算法效率的考虑时间与空间算法设计的要求69算法时间效率的度量程序运行消耗时间取决于下列因素算法策略问题规模语言层次编译程序所产生的机器代码的质量机器执行指令的速度算法时间效率度量 算法时间效率在软硬件环境相同的情况下取决于问题的规模，即T(n)=f(n)。算法时间效率度量的基本做法 在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间效率的度量702个N*N矩阵相乘for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}n+1n(n+1)n2n2(n+1)n3语句频度：是指该语句在一个算法中重复执行的次数。2个N*N矩阵相乘for(i=1;i<=n;++i)71算法的时间复杂度算法中基本操作重复执行的次数是问题规模n的函数f(n)。算法的时间度量记作T(n)=O(f(n))。T(n)和f(n)是定义在正数集上的正函数，如果存在正的常数C和自然数M，使得当n≥M时有T(n)≤Cf(n)，则称函数T(n)当n充分大时上有界，且f(n)是它的一个上界，记为T(n)=O(f(n))。（OrderofMagnitude）。用“O”来表示数量级，所谓算法的时间复杂度，即是算法的时间量度，记作：T(n)=O(f(n))

算法的时间复杂度72（1）x=x+1；其时间复杂度为O(1)，我们称之为常量阶；（2）for(i=1;i<=n;i++)x=x+1;其时间复杂度为O(n)，我们称之为线性阶；（3）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;其时间复杂度为O(n2),我们称之为平方阶。（4）for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2，其时间复杂度为：O(n2)

此外算法还能呈现的时间复杂度有对数阶O(log2n),指数阶O(2n)等。（1）x=x+1；其时间复杂度为O(1)，我们称73数据结构中常用的时间复杂度频率计数O(1)常数阶O(n)线性阶O(n2)平方阶O(n3)立方阶O(2n)指数阶O(log2n)对数阶O(nlog2n)线性对数阶指数时间的关系为：O(2n)<O(n!)<O(nn)多项式阶O(nk)的算法我们称之为“好算法”数据结构中常用的时间复杂度频率计数指数时间的关系为：O(74大O的运算规则加法准则(并列程序段) a)前提：T1(m)=O(f(m));T2(n)=O(g(n)) 结论：T(n)=T1+T2=O(max(f(m),g(n)))