数据结构与算法第一章.ppt

《数据结构与算法第一章.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第一章.ppt（83页珍藏版）》请在三一办公上搜索。

1、数据结构与算法,生命学院 范 军,课程教材及参考书,教学用书：数据结构（C语言版）徐孝凯，贺桂英 编 清华大学出版社，2004年参考书：1数据结构，许卓群，张乃孝，杨冬青，唐世渭，高等 教育出版社，1987年 2.数据结构 C+与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，1998年 3数据结构(C语言版），严蔚敏、吴伟民，清华大学出版社，1997年 4.数据结构与算法，王若梅等著，中山大学出版社，2000年 5.C语言程序设计 谭浩强 清华大学出版社,第一章 概论,1.1数据结构课程研究的内容 1.2 数据结构课程的发展历史1.3 基本概念和术语 1.4 数据类型的表示与实现 1.5 算

2、法和算法分析,1.1数据结构课程研究的内容,如今计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。（数值计算？）与此相应计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。而随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂，这就给程序设计带来一些新的问题。为了编写出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是“数据结构”这门学科形成和发展的背景。,什么是程序、软件？N.沃思（Niklaus Wirth)教授提

3、出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法数据结构）。（2）算法的选择依赖于作为基础的数据结构（数据结构算法）。软件=程序+文档（软件工程的观点）,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。它是一门主要研究怎样合理地组织数据，建立合适的数据结构来提高计算机执行程序所用的时间效率和空间效率的科学。它的主要研究内容为：数据的逻辑结构-数据关系之间的逻辑关系 数据的存储结构-数据的逻辑结构在计算机中的表示 操作算法-插入、删除、修改、查询、排序等,数据结构的应用示例,电话号码簿查询系统 研究目的：构造一个

4、可以多种方式查询的电话号码查询系统。研究内容：如何建立一个可通过姓名，拼音，号码，分组进行多角度查询的电话号码查询系统如何兼顾多种查询的查询表的存储结构以及相关的关联操作,采用姓氏索引表的存储结构：,查找过程是先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名，这样查找登记表时就无需查找其它姓氏的名字了。因此，在这种新的结构上产生的查找算法就更为有效。,例2 图书馆的书目检索系统自动化,在图书馆内每本书都有多种信息条目所组成的书目信息卡。每一本书都有惟一的一个登录号，但不同的书目之间可能有近似甚至相同的书名，或者有相同的作者名，或者有相同的分类号。在书目自动检索系统中的主要

5、操作便是按照某个特定要求(如给定书名、作者、分类号等)对书目文件进行快速、准确地查询。,研究目的：书目自动检索系统中的主要操作便是按照某个特定要求(如给定书名、作者、分类号等)对书目文件进行快速、准确地查询。研究的内容：如何构建一个检索效率高的书目信息数据库？（顺序存储？链接存储？顺序存储？索引存储？）如何对这个数据库进行高效率的检索、维护和管理 操作？（索引查询、分组查询、模糊查询、关联查询、关键词查询）,如将这些信息卡片按特定的分类编排，：如按书名编排的、有按作者编排的、还有按分类编排的，等等。这样计算机按作者的要求查找起来就更加迅速。,图书馆的书目自动检索系统设计：建立所处理的基本数据（

6、数据元素）并选择合适的数据元素类型：每本书由（登录号，书名，作者，出版社,分类号)组成；设计并建立数据元素间的关系（逻辑结构）：建立一个按登录号顺序排列的书目表和按书名、作者和分类号顺序排列的索引表；设计所需的操作：一组作用在这些表上的运算（查询、插入、修改等）；设计数据的存储（存储结构）：怎样存储这些数据及其关系使得上述操作容易实现。,计算机之所以能和人对奕是因为有人将对奕的策略事先己存入计算机。并且以某种格式存储在计算机中。因此，在对奕问题中，实际上是计算机根据对奕过程中可能出现的棋盘状态在存储的对策中检索出最佳的“步骤”。若将从对奕开始到结束的过程中所有可能出现的格局都画在一张图上，则可

7、得到棵倒长的“树”。“树根”是对奕开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对奕的过程就是从树根沿树枝到某个叶子的过程。,例 3 人机对弈问题(博弈树）,研究目的：设计一个能应对各种复杂情况的并具有记忆功能的具有人工智能的决策判断系统。研究的内容：如何构建一个检索效率高的对弈（决策）信息数据库？（树的结构？树的存储？）如何对这个数据库进行高效率的检索操作？（最优路径设计、遍历查询方法）,建立并输入对弈的棋盘格局数据（数据元素）：格局（某时刻的棋盘布局）；建立格局之间的关系（逻辑结构）：一个格局可以派生出几个下一个格局（树状结构，博弈树）；设计所需的操作：由某个格局出发，借助于以上

8、的格局树（显式地或非显式地）找出计算机赢的步骤；设计格局的存储结构：如何存储格局及其格局间的关系。,这类人机对弈的问题目前已发展成为一大类人工智能问题的研究课题：博弈树或称为最优决策树的构建、查询和存储以及自学习。具体的应用有：医疗专家系统、武器系统的人工智能决策，民用机器人的智能系统等。,例子4 田径赛的时间安排问题（无向图的着色问题）,设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。,-田径赛的时间安排问题解法（1）设用如下六个不同的代号代表不同的项目：跳高 跳远 标枪 铅球 100米 200米 A B C

9、D E F（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。,A,E,B,F,D,C,只需安排四个单位时间进行比赛,例5 设计一个考试日程安排表，使在尽可能短的时间内安排完考试，要求同一个学生选修的几门课程不能安排在同一时间内，,解决该问题，首先选择一个合适的数据结构。用数据结构中的一种称为无向图的结构来表示所要解决问题的结构，图中的顶点表示课程，不能同时考试的课程之间连接一条连线。则该问题可转化为该无向图的着色问题，即用最少的颜色对无向图的顶点着色，并且保证任何两个相连通的顶点具有不同的颜色。而同一种颜色表示相同的考试时间。答案

10、：1:A,C 2:B,D 3:E 4:F从该问题的求解过程可看出，解决此问题的关键选择合适的数据结构，以及适当的求解算法。而这两项关键因素恰恰是数据结构所研究的内容。,实际上例4，例5都可归类于利益冲突的最优分隔这一大类问题，这类的问题包含有“地图的有限颜色的着色”，“农夫带狼、羊和白菜过河”等许多人工智能规划问题。,例子6：如何在各城市之间构建一个具有最少代价的通讯联通网图的最小生成树问题,若一个联通网表示城市间的通讯系统，网的顶点代表城市，网的边代表城市之间架设通讯线路的代价，各城市的距离不同，地理条件不同，其造价也不同，即边上的权不同。如果要求既要联通城市，又要使总造价最低，这就是一个求

11、图的最小生成树的问题。,图(a)就是一个连通网，图(b),(c),(d)是它的三棵生成树，每棵树的权都不同，它们分别为57,53和38,目前，数据结构与算法中已有标准算法了解决这类问题：一是普里姆(Prim)算法，另一个是克鲁斯卡尔(Kruskal)算法。,1.2 数据结构课程的发展历史,数据结构课程的形成和发展：形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。目

12、前：它是计算机专业的核心课程，考研的核心课程。同时，它现在也成为许多非计算机专业的重要的专业选修课。,学习数据结构的目的：提高复杂程序设计的能力培养算法设计能力为后继课程（如操作系统、编译原理和数据库设计，信息系统处理等）打基础。,1.3 基本概念和术语,1.数据：是客观事物的符号表示,是信息的载体；是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据,2.数据元素：是数据的基本单位，也称之为元素、记录、结点、顶点等。有时一个数据元素可以由若干数据项(Data Item)组成（此时数据元素被称为记录）例子：学籍管理系统中一个学生的记录3

13、.数据项:是数据的不可分割的最小单位。例子：学籍管理系统中的学生的学号，姓名等数据4.数据对象:是性质相同的数据元素的集合，是数据的一个子集。例子：如整数数据对象 N=0,1,2,字母字符数据对象 C=A,B,C,F。,5.数据结构：是指组成数据的元素之间的结构以及相互之间的依赖关系。这种关系有：空间位置关系-存储结构 相互联系、作用和依赖关系-逻辑结构,(1)数据逻辑结构的类型,1.集合:数据中的元素之间没有关系.即R=2.线性结构:线性结构是指数据中各元素之间具有1对1的先后次序关系。R=(d1,d2),(d2,d3),(d(n-1),dn),3.树状结构:树结构是指数据中各元素之间具有1

14、对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。4.图状结构:图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。,数据结构的图形表示,从图形表示中可以清醒地看出：,集合结构中的元素是各自独立的，元素之间没有联系线性结构中的元素是一个接一个串联起来的，它有一个头元素和一个尾元素，其余为中间元素；每个中间元素既有前驱元素，又有后继元素在树结构中，树根结点只有后继结点，而没有前驱结点；除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点。树结构是图结构的特例，线性

15、结构是树结构的特例。为了区别于线性结构，时常把树结构和图结构称为非线性结构。,（2）数据结构的形式定义：某一数据对象的所有数据成员之间的关系。记为：B=K,R B 为一种数据结构，它由数据元素的集合K和K上二元关系的集合R所组成。K 是某一数据对象，R 是该对象中所有数据成员两两之间的关系的有限集合。,四种数据结构的二元组表示:,集合结构中的元素集合K和二元关系R分别为：K=A，B，C，D，E，F，G R=线性结构中的元素集合K和二元关系R分别为：K=A，B，C，D，E，F，G R=，树结构中的元素集合K和二元关系R分别为：K=A，B，C，D，E，F，G R=，图结构中的元素集合K和二元关系R

16、分别为：K=A，B，C，D，E，F，G R=，,（3）数据结构应用实例,注：由于每条记录的职工号各不相同，所以以每条记录的职工号作为该记录的关键字，,假定不考虑该表中记录之间的任何次序，则该表中的数据就是一个集合结构，对应的记录集合以及二元关系为：K=Rec1,Rec2,Rec3,Rec4,Rec5,Rec6,Rec7,Rec8,Rec9,Rec10 R=若考虑到该表中的职工记录是按照职工号从小到大有序排列的这个特点，则这个职工表又是一个线性结构，其中表头元素为01号职工的记录信息，接着为02号职工的，依次类推，表尾元素为10号职工的记录信息。该线性结构包含的记录集合和二元关系为：K=01,0

17、2,03,04,05,06,07,08,09,10 R=,有时需要按职工的出生日期进行数据结构的定义和处理，则可以把表中的所有职工看作是按照出生日期，从小到大有序的，由此对应的数据结构也是一种线性结构，该线性结构包含的记录集合和二元关系为：K=01,02,03,04,05,06,07,08,09,10 R=,对应的图形表示为：,在上面职工表中，还存在职工人员之间领导与被领导的关系，其中01号职工为经理，直接领导02、03和04号职工，他们分别是相应部门的主管，02号职工直接领导05和06号职工，03号职工直接领导07、08和09号职工，04号职工直接领导10号职工。由此可知，该职工表是一种树结

18、构，包含的职工集合和二元关系分别为：K=01,02,03,04,05,06,07,08,09,10 R=,对应的图形表示为：,若要反映职工之间的好友关系，假定01和02号职工是好友，01和04号是好友，02和03、02和06、02和07、03和07、04和06、05和07之间是好友，则反映这种好友关系的数据结构是图结构，二元组中的元素集合和有序对集合分别为：K=01,02,03,04,05,06,07,08,09,10 R=,对应的图形表示如下面左图所示，其中08、09和10号职工无好友，在图形中为孤立顶点，省略未画；图形中每对顶点之间的两条相反的有向边，表示这两个顶点职工是一对好朋友，为了简

19、化起见，两条相反的有向边可以用一条无向边来代替，隐含着该无向边是双向的，即连接的两个顶点互为前驱和后继，则对应的无向图表示如下面右图所示。,这样R关系可改写为：R=(01,02),(01,04),(02,03),(02,06),(02,07),(03,07),(04,06),(05,07)如果图的两个节点间的两个方向的有序对的关系是相同的则这个有序对可简化成一个，对应图形中的一条无向边，由无向边构成的图形称为无向图，反之为有向图。,(4)数据的存储结构（物理结构）,数据（逻辑）结构的存储包含数据元素的存储及其逻辑关系的存储，是数据结构在计算机中的表示(或映象)。根据存储映像的特点,存储结构可分

20、为:顺序存储结构、链式存储结构、索引和散列等。,存储结构的分类:顺序结构,顺序的方法:将逻辑上相邻的元素存储到物理上相邻的存储位置.常用于线性的数据结构.例如,D=d1,d2,d3,d4,d5 R=(d1,d2),(d2,d3),(d3,d4),(d4,d5)假定一个结点占一个单元,d1存放于200号单元,d1,d2,d3,d4,d5,200,201,202,203,204,存储结构的分类:链式结构,这种结构是给结点附加一个指针字段,指出其后继节点的位置,即存放结点的存储单元分为两部分:,指针项可以有多个,以指示多个后继（或前驱）.例如,R=(d1,d2),(d1,d3),(d2,d4),(d

21、2,d5),(d3,d6),d1,d2,d3,d6,d5,d4,d1,d2,d3,d4,d5,d6,空指针,存储结构的分类:索引结构,在线性结构中，每一个节点的内容都为查找其他线性数据结构的索引号。这样的存储结构就为索引存储，其构成的数据结构也称为索引表,数据存储区,张,王,李,赵,钱,索引表存储索引号及地址,M,存储结构的分类:散列（hashing)结构,散列的方法是用结点的关键字值直接计算出结点的存储地址。这个取值函数也称为散列函数。D：0 1 2 3 4 5 6 D=X Mod 13（假设每个数据元素都有一个关键字）最好的散列函数应满足不同的关键字具有不同的地址。如果不同的关键字对应的地

22、址相同，则称为“碰撞”（冲突）。,逻辑结构相同，但存储结构不同，则认为是不同的数据结构。如顺序表和链表具有相同的逻辑结构，但存储结构分别为顺序结构和链表结构,数据类型是对数据的取值范围、数据元素之间的结构以及允许的操作的一种综合描述。它是一个值的集合和定义在此集合上的一组操作的总称.一般的高级语言都提供了一些数据类型,如整数型,字符型等.用户还可以定义自己的数据类型.数据类型可分为简单类型（也称原子类型）和结构类型两种,1.4 数据类型,一、简单与结构数据类型1.简单数据类型是不可分解的数据类型如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void

23、)等,2.结构数据类型结构数据类型有由普通结构数据类型（有时简称结构数据类型）和抽象数据类型结构数据类型由若干成分（原子类型或结构类型）按某种结构组成的数据类型结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体（如抽象数据类型）,二、抽象数据类型,抽象数据类型由基本的数据类型（包括简单结构类型）和定义在此数据结构上的一组操作所组成,抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论共内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。具有信息隐蔽和数据封装，使用与实现相分离的特点抽象数据类型常由用户定义，用以表示应用问题的数据模型

24、,抽象数据类型可用（D，S，P）三元组表示.其中 D是数据对象,S是D上的关系集,P是对D的基本操作集。抽象数据类型可定义为：ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作(函数)的定义 ADT 抽象数据类型名,在C+中，抽象数据类型可以由C+的类来描述，ADT的每个运算对应一个成员函数。例如，表示圆的class class Circle private:float r,x,y;public:Circle(float v1,float v2,float v3);float area()=return pi*r*r;,1.5 算法和算法分析,一、算

25、法 1.定义：一个算法是对特定问题求解步骤的一种描述，它是精确定义的指令的有穷序列，对于给定的初始状态，它将根据指令最终到达一个终止状态.2.通常，算法分为两大类：数值算法和非数值算法 3.算法具有以下特性:1)有穷性:一个算法总是在执行有穷步后结束 2)确定性:算法的每一步都必须是明确地定义的.3)可行性:算法中的每一步都是可以通过已经实现的操 作来完成的 4)输入:一个算法有零个或者多个输入,这些输入取 自于特定的对象集合 5)输出:一个算法有一个或者多个输出，它们是与输 入有特定关系的量,例1.3 一个不是算法的例子(1)begin(2)n=0(3)n=n+1(4)repeat(3)(5

26、)end,例1.4 一个不超过100次计数的算法(1)begin(2)n=0(3)n=n+1(4)if n=100 do(5)else repeat(3)(5)output n(6)end,二、算法的描述算法的描述可以用下列语言描述：自然语言：易于阅读，但是，不精确，或会有歧义；程序设计语言（程序）：精确，无歧义，但是，不便阅读；介于自然语言和程序设计语言的伪代码框图：便于交流，不依赖于实现,例 假设有n(=1)个整数a1,a2,an.要求对此数列由小到大进行排序。思路：1 从未排好序的数列中选出最小的元素，将其放到排好序的数列后 2 重复这个过程，直至排序结束。,a1,a2,a3,an,找出

27、最小元素am,am,a2,a3,an,a1,交换a1和am,am,a2,a3,an,aj,找出最小元素aj,am,aj,a3,an,a2,交换a2 和aj,void selectSort(int a,const int n)/将整数列a0,an-1按非递减序排列 for(int i=0;i n-1;i+)int j=i;/找出ai到an-1的最小数aj for(int k=i+1;k n,k+)if(ak aj)j=k;/j指示当前的最小数/交换ai和aj int temp t=ai;ai=aj;aj=t;,例2 求n个元素中的最大值 算法就是解决特定问题的方法，该方法可以借助各种工具描述出来

28、。如从n个整数元素中查找出最大值，若用流程图描述则如下图所示。若采用文字描述，则如下列步骤所示：（1）给n个元素a1an输入数值；（2）把第一个元素a1赋给用于保存最大值元素的变量x；（3）把表示下标的变量i赋初值2；（4）如果ix则将ai赋给x，否则不改变x的值，这使得x始终保存着当前比较过的所有元素的最大值；（6）使下标i增1，以指示下一个元素；（7）转向第（4）步继续执行。,#include#define N 8/*定义N常量为整数8*/void main(void)int i,x,aN;/*用a0aN1保存a1an元素*/printf(请输入%d个整数：,N);for(i=0;ix)x

29、=ai;i+;printf(%d个整数中的最大值为：%dn,N,x);,三、算法的设计要求算法的设计应满足：1）正确性：对于合法的输入产生符合要求的输出；2）可读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法；3）健壮性：当输入非法时，算法还能做出适当的反应而不会崩溃，如输出错误信息；算法中应该考虑适当的错误处理；4）效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大存储空间。,四、算法分析,算法分析通常有两种方法：事后统计：不同算法的程序运行在同一组输入上，根据时间和空间的统计来比较优劣。缺陷：事先编写程序；依赖于程序运行的软硬件

30、环境。事前估计：一种不考虑算法的程序运行软硬件环境的分析方法。一个算法的运行工作量的大小只依赖于问题的规模。通常考虑两个度量：时间复杂度：算法执行的时间总数作为问题规模的函数。空间复杂度：算法执行时所占用的存储空间作为问题规模的函数。,1.时间复杂度 算法的时间复杂度是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间长短，是问题规模n的函数f(n)，对于给定规模的问题，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境

31、决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素算法中进行简单操作次数的多少。不管一个算法是简单还是复杂，最终都是被编译后分解成简单操作再通过CPU来具体执行的。因此，每个算法都对应着一定的简单操作的次数。显然，在一个算法中，进行简单操作的次数越少，其运行时间也就相对地越短；次数越多，其运行时间也就相对地越长。所以，通常把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能。反之，如果已知一个算法所包含的简单运算的次数，那么通过统计该算法的运行时间就可评估计算机的运算性能。（如评估超级计算机 Linpack基准）,统计算

32、法从开始到运行终止时所需总程序步数T,并将其视为问题规模n的函数T(n).T(n)称为算法的时间复杂度。T(n)=O(f(n)时间复杂度是衡量算法好坏的一个最重要的标准,复杂度的度量通常计算到数量级，即只要大致计算出相应的数量级（Order）即可，其数量级可由其同数量级函数g(n)得到，g(n)的定义为：设f(n)的一个辅助函数g(n),定义为n大于等于某个正整数n0时，存在着两个正整数A和B（其中AB）,使得：成立，则称g(n)是f(n)的同数量级函数。把T(n)表示成数量级的形式为：,由于g(n)往往是一些最基本的数量级函数（不带系数），因此在计算算法的时间复杂度时，采用g(n)要比使用原

33、算法基本步数的统计函数f(n)更加简单。,例子：（1）简单操作：y*=x;f(n)=2（2）累加求和：int sum(int b,int n)int s=0;for(i=0;in;i+)s+=bi;return s;,把下列程序进一步分解为最基本的语句，可变为：i=0;/1次 Mark1:if(i=n)goto mark2/n+1次 s+=bi;/n次 i+;/n次 goto mark1;/n次 Mark2:return s;/2次 算法的基本程序步之和为f(n)=4n+4,取g(n)=n，则,其同阶表示形式为T(n)=O(g(n)=n，即算法时间复杂度O(n)=n,(3)矩阵相加 void

34、MatrixAdd(int aMsMs,int bMsMs,int cMsMs,int n)/实现矩阵an,n和bn,n的加法，其和存入cn,n中 int i,j;for(i=0;i=n)goto mark4;/n+1次 j=0;/n次 mark2:if(j=n)goto mark3;/n(n+1)次 cij=aij+bij;/n*n次 j+;/n*n次 goto mark2;/n*n次 mark3:i+;/n次 goto mark1;/n次 mark4:;算法的基本程序步之和为f(n)=4n2+5n+2,取g(n)=n2，则,其同阶表示形式为T(n)=O(n)，即算法时间复杂度O(n)=n2

35、,（4）分析以下程序段的时间复杂度i=1;while(i=n)i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即，取最大值则该程序段的时间复杂度为：,/*1*/,/*2*/,在以上的四个算法中，程序段的时间复杂度分别为O(1),O(n),O(n2),O(log2n)分别称为常量阶，线性阶，平方阶，对数阶。,复杂度的度量通常计算到数量级T(n)=O(n2)的含义：当n适当大时，算法的运行时间的增长率不超过n2的常数倍时间复杂度除常量阶O(1),线性阶O(n),平方阶O(n2)，对数阶O(logn)外，还有排列阶O(n!)，指数阶O(2n)等，它们是相对于问题规模n的增长率的表示方法各

36、种数量级对应时间复杂度存在着以下的关系：排列阶、指数阶随问题规模增长过快，一般不宜使用,常见的复杂度：O(1),O(log2 n),O(n),O(nlog2 n),O(n2),O(2n),O(n!),n,T(n),200log2n,100n,5n2,2n,20,2000,20,表1.1多项式增长和指数增长的比较,通常，当基本语句的计算次数超过1.01015时，该算法的普通计算机执行时间就无法接受。我们可以计算如下：计算机每秒可执行一亿(1.0109)条基本语句，则执行一个需1.01015次基本操作（指数级，n=50）的算法需要的时间为：T=1.01015/（1.0109）=1.0 106（S)

37、=277.8(h)=11.6(d)当指数级，n=100 时，计算机速度提高到1000万亿次/每秒（1.0 1016），T=1.0 1030/（1.0 1016）=1014(s)=11.6 108(d)3 106(y),时间复杂度T(n)可能依赖于输入，即不同的输入（相同的规模）其复杂度不同。一个算法的时间复杂度还可以具体分为最好、最差（又称最坏）和平均三种情况讨论。平均复杂度(The Average Case)：所有可能输入.数据集的期望值最坏情况复杂度(The Worst Case)：估算最坏情况下时间复杂度的一个上界这也是通常所指的复杂度最好复杂度(The Best Case):在最理想输

38、入情况下的时间复杂度。,下面结合从一维数组an中顺序查找其值等于给定值key的元素的算法进行说明。int SequenceSearch(int a,int n.int key)/*若查找成功则返回元素的下标值，否则返回-1*/int i;for(int i=0;in;i+)if(ai=key)return i;return-1;此算法的时间复杂度主要取决于for循环体被反复执行的次数。最好情况：时间复杂度为 O(1)；最差情况：时间复杂度为 O(n)；平均情况：时间复杂度为,在一个算法中，最好情况的时间复杂度最容易被求出，但它通常没有多大实际意义，因为数据一般都是随意分布的，出现最好情况分布的

39、概率极小；最差情况下的时间复杂度也容易求出，它比最好情况有实际意义，通过它可以估计到算法运行时所需的相对最长时间，并且能够使用户知道如何设法改变数据的排列顺序，尽量避免或减少最差情况的发生；平均情况下的时间复杂度的计算要困难一些，因为它往往需要运用概率统计等方面的数学知识，有时还需要经过严格的理论推导才能求出，但平均情况下的时间复杂度最有 实际意义，它确切地反映了运行一个算法的平均快慢程度，通常就用它来表示一个算法的时间复杂度。对于一般算法来说，平均和最差这两种情况下的时间复杂度的数量级往往是相同的，它们主要是差别在最高次幂的系数上。另外有一些算法，其最好、最差和平均情况下的时间复杂度或相应的

40、数量级都是相同的。,如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度（如根据某些判据可出现多个程序分支，而各分支的时间复杂度又不同）如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度,2.空间复杂度空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：S(n)=O(f(n)通常以简单变量的存储空间为单位算法的存储空间包括：1）程序本身、常量和变量等所需空间 2）程序运行中动态申请的空间和递归调用所需空间,附录：需重点掌握的C语言基础知识：,基本的输入和输出语句的语法和应用 如 scanf（）语句和printf（）语句的使用指针变量的定义使用函数的调用以及函数中参数的传递方式 函数的定义、函数的传值调用和传址调用结构体的定义及应用 struct 定义和typedef（别名）定义和使用，结构体中子域的调用,作业：1.11.3 中的2、3、4、5 小题,