《数据结构概念》PPT课件.ppt
《《数据结构概念》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据结构概念》PPT课件.ppt(97页珍藏版)》请在装配图网上搜索。
上午9时45分,1,第一章 数据结构概念,集美大学计算机学院,王 俊 玲,2,上午9时45分,什么是数据结构 抽象数据类型及面向对象概念 算法定义 模板 算法简单性能分析与度量,第一章 数据结构概念,3,上午9时45分,“学生”表格,学生选课系统,4,上午9时45分,“课程”表格,学生选课系统,5,上午9时45分,学生 (学号,姓名,性别, 籍贯,出生年月),课程 (课程号,课程名,学时),选课单 (学号,课程号, 成绩,时间),“选课单”包含如下信息 学号 课程号 成绩 时间 学生选课系统中实体构成的网状关系,学生选课系统,6,上午9时45分,UNIX文件系统的系统结构图,7,上午9时45分,数据(data),数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号的集合。 数据的分类: 数值性数据:整型、浮点型、复数、双精度数等 非数值性数据:字符和字符串、文字、图形、 图像、语音等,8,上午9时45分,数据元素 (data element),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项 (Data Item)组成。数据项是具有独立含义的最小标识单位。分为初等项和组合项。 数据元素又称为元素、结点、记录。,9,上午9时45分,什么是数据结构,定义: 由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为: Data_Structure = D, R 其中,D 是某一数据元素的集合,R 是该集合中所有数据元素之间的关系的有限集合。 称为数据结构的二元组表示法。,10,上午9时45分,例:N 个网站之间的通讯网络,树形关系,图状关系,以最小代价将n个网站连通,形成,网络中任一网站出现故障,整个网络仍然保持畅通,形成,11,上午9时45分,数据结构是数据的组织形式,包括三个方面: 数据元素间的逻辑关系,即数据的逻辑结构; 数据元素及其关系在计算机存储内的表示,即数据的存储表示(存储结构/物理结构); 数据的运算,即对数据元素施加的操作。,12,上午9时45分,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据,与数据的存储无关; 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型; 数据的逻辑结构与数据元素本身的形式、内容无关; 数据的逻辑结构与数据元素的相对存储位置无关。,13,上午9时45分,数据的逻辑结构分类,线性结构 线性表 非线性结构 树 图(/网络) 集合,层次结构,群结构,14,上午9时45分,线性结构,树形结构,树 二叉树 二叉搜索树,15,上午9时45分,堆结构,“最大”堆 “最小”堆,16,上午9时45分,图结构 网络结构,17,上午9时45分,数据的存储结构,数据的存储结构是逻辑结构用计算机语言在计算机中的表示和实现。 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,主要用于内存的存储表示,主要用于外存 (文件) 的存储表示,18,上午9时45分,随编程环境的不同而不同,当用高级程序进行编程时,通常可用高级编程语言中提供的数据类型描述之。 例如,当以“顺序存储结构”表示长整数时,可将它定义为数组: typedef int Long_int3; 同样,此时对数据元素也要借用高级编程语言中的数据类型描述之。,数据结构的存储结构的描述方法,19,上午9时45分,对每一个数据结构而言,必定存在与它密切相关的一组操作。若操作的种类和数目不同,即使逻辑结构相同,数据结构能起的作用也不同。 不同的数据结构其操作集不同,但下列操作必不可缺: 1) 结构的生成; 2) 结构的销毁; 3) 在结构中查找满足规定条件的数据元素; 4) 在结构中插入新的数据元素; 5) 删除结构中已经存在的数据元素; 6) 遍历。,数据结构的操作,20,上午9时45分,综合实例:学生表,21,上午9时45分,学生表的存储结构-顺序结构,22,上午9时45分,head,1,张斌,男,9901,8,刘丽,女,9902,34,李英,女,9901,20,陈华,男,9902,12,王奇,男,9901,26,董强,男,9902,5,王萍,女,9901,链式结构-物理结构/存储结构: 学生表构成的链表如右图。其中head为第一个数据元素的指针。,学生表构成的链表,学生表的存储结构-链式结构,23,上午9时45分,采用二元组表示表1.1的学生表。 学生表中共有7个结点,依次用k1k7表示,则对应的二元组表示为B=(K,R),其中: K=k1,k2,k3,k4,k5,k6,k7 R=, 具体表示如下: ,学生表的二元组表示,24,上午9时45分,该构利用图形形象地表示(图形中的每个结点对应着一个数据元素,两结点之间的连线对应着关系中的一个序偶)。 上述“学生表”数据结构用下图的图形表示。,学生表数据结构图示,学生表的图形表示,25,上午9时45分,存放学生表的结构体数组Stud定义为:(顺序存储结构的线性表) struct int no; /*存储学号*/ char name8; /*存储姓名*/ char sex2; /*存储性别*/ char class4; /*存储班号*/ Stud7=1,“张斌”,“男”,“9901”,5,“王萍“,“女“,“9901“;,学生表的计算机语言描述C/C+语言,26,上午9时45分,对于“学生表”这种数据结构,可以进行一系列的运算,例如,增加一个学生记录、删除一个学生记录、查找性别为“女”的学生记录、查找班号为“9902”的学生记录等等。(基本操作:查 插 删 改) 从前面介绍的两种存储结构看到,同样的运算,在不同的存储结构(线性结构、链式结构)中,其实现过程是不同的。如下页所示:,学生表的操作:查 插 删 改(基本操作),27,上午9时45分,例如,查找学号为20的学生的姓名: 线性结构的查找:对于Stud数组,可以从Stud0开始比较,Stud0.no不等于20,再与Stud1.no比较,直到Stud3.no等于20,返回Stud3.name。 链式结构的查找:对于head为首结点指针的链表,从head所指结点开始比较,head-no不等于20,从它的next得到下一个结点的地址,再与下一个结点的no域比较,直到某结点的no域等于20,返回其name域。,学生表的操作:查找,顺序表,链 表,28,上午9时45分,抽象数据类型及面向对象概念,数据类型 定义:一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,29,上午9时45分,构造数据类型由基本数据类型或构造数据类型组成。 构造数据类型由不同成分类型构成。 基本数据类型可以看作是计算机中已实现的数据结构。 数据类型就是数据结构,不过它是从编程者的角度来使用的。 数据类型是模板,必须定义属于某种数据类型的变量,才能参加运算。,程序1.15,30,上午9时45分,抽象数据类型 (ADTs: Abstract Data Types),抽象数据类型是由用户定义,用以表示应用问题的数据模型。 特点是:信息隐蔽和数据封装,使用与实现相分离(类型的声明与其实现分开)。 抽象数据类型可用(D, S, P)三元组表示,其中,D 是数据元素的集合(简称数据对象),S 是 D上的关系集合,P 是对 D 的基本操作集合。,31,上午9时45分,抽象数据类型,32,上午9时45分,封装物理实现,公开界面接口。改变抽象数据类型的物理实现,不影响其他使用该抽象数据类型的程序(只要界面中的接口或服务方式不变)。,33,上午9时45分,抽象数据类型的描述,其中数据对象、数据之间的关系用伪码描述;基本操作定义格式为,ADT 抽象数据类型名 数据对象:数据对象的定义 数据关系:数据关系的定义 基本操作:基本操作的定义 ADT 抽象数据类型名,基本操作名(参数表) 前置条件:先决条件描述 后置条件:操作结果描述,34,上午9时45分,基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以&打头,除可提供输入值外,还将返回操作结果。 “前置条件”描述了操作执行之前数据结构和参数应满足的先决条件,若不满足,则操作失败,并返回相应出错信息。 “后置条件”说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若前置条件为空,则省略之。 C+语言中使用struct和class定义抽象数据类型,35,上午9时45分,自然数的抽象数据类型定义(伪码描述),ADT NaturalNumber is objects: 一个整数的有序子集合,它开始于0, 结束于机器能表示的最大整数(MaxInt)。 Function: 对于所有的 x, y NaturalNumber; False, True Boolean, +、-、=、= 等都是可用的服务。 Zero( ) : NaturalNumber /前置条件:无 /后置条件:返回自然数0,36,上午9时45分,IsZero(x) : Boolean /前置条件:x为NaturalNumber /后置条件:if (x = 0) then 返回True else 返回False Add (x, y) : NaturalNumber /前置条件:x, y为NaturalNumber且x+yMaxInt /后置条件:返回 x+y Subtract (x, y) : NaturalNumber /前置条件: x, y为NaturalNumber且xy /后置条件:返回 x- y,37,上午9时45分,Equal (x, y) : Boolean /前置条件: x, y为NaturalNumber /后置条件: if (x = y) 返回True else 返回 False Successor (x) : NaturalNumber /求后继 /前置条件: x为NaturalNumber /后置条件: if (x = MaxInt) 返回 x else 返回 x+1 end NaturalNumber,38,上午9时45分,自然数的抽象数据类型定义,程序1.2,39,上午9时45分,例:复数的抽象数据类型定义: 用两个实数来表示复数,将复数定义为两个实数的有序对,并约定实部是前驱,虚部是后继。 ADT Complex 数据对象: D=e1,e2|e1,e2均为实数 数据关系: R1=| e1是复数的实数部分,e2 是复数的虚数部分 ,40,上午9时45分,基本操作: AssignComplex(&Z,v1,v2):构造复数Z,其实部和 虚部分别赋以参数v1和v2的值。 DestroyComplex(&Z):复数Z被销毁。 GetReal(Z,&real):用real返回复数Z的实部值。 GetImag(Z,&Imag):用Imag返回复数Z的虚部值。 Add(z1,z2,&sum):用sum返回两个复数z1,z2的和值。 ADT Complex,41,上午9时45分,面向对象的概念,面向对象 = 对象类继承通信 对象 在应用问题中出现的各种实体、事件、规格说明等。 由一组属性值和在这组值上的一组服务(或称操作)构成。 与C中构造数据类型不同在于:C中的构造数据类型的变量仅涉及属性值,与操作分离,而C+中的对象则不然(操作的声明也放在类的声明中)。,42,上午9时45分,类 (class),实例 (instance) 具有相同属性和服务的对象归于同一类,形成类。 类中的对象为该类的实例。 同一类的实例 共享类的属性和类的操作; 通过继承共享其父类的公共的和保护性的属性和操作;(私有的不能继承) 同一类的不同实例有不同的属性值。,43,上午9时45分,四边形类及其对象,44,上午9时45分,继承 派生类(子类):四边形,三角形, 基类(父类):多边形,45,上午9时45分,通信 消息传递:对象的“消息传递”也就是函数调用 。 C+中消息传递的方式: 定义:Point p; void move(int x, inty); 使用:p.move(x, y); C中则不同,需使用函数调用方式: 定义:Point p; void move(Point q, int x, inty); 使用:move(p, x, y);,46,上午9时45分,Draw( ) move(x, y) contains(aPoint),Polygon,referencePoint Vertices,Polygon 类,referencePoint Vertices,Draw( ) move(x, y) contains(aPoint),Polygon的子类 Quadrilateral类,Quadrilateral,47,上午9时45分,算法定义,定义:一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列 特性: 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本,48,上午9时45分,事例学习:选择排序问题 明确问题:递增排序 解决方案:逐个选择最小数据 算法框架: for (int i = 0; i n-1; i+) /n-1趟 从ai检查到an-1; 若最小整数在ak, 交换ai与ak; 细化程序:程序 SelectSort,算法设计 自顶向下,逐步求精,49,上午9时45分,void selectSort ( int a , const int n ) /对n个整数a0,a1,an-1按递增顺序排序 for (int i = 0; i n-1; i+) int k = i; /从ai查到an-1, 找最小整数, 在ak for (int j = i+1; j n; j+) if (aj ak) k = j; int temp = ai; ai = ak; ak = temp; ,50,上午9时45分,模板 (template),定义 适合多种数据类型的类定义或算法,在特定环境下通过简单地代换,变成针对具体某种数据类型的类定义或算法。,51,上午9时45分,用模板定义用于排序的数据表类 #ifndef DATALIST_H /定义在“dataList.h”中 #define DATALIST_H #include using namespace std; template class dataList private: E *element; int listSize; void swap (int m1, int m2); int minKey (int low, int high);,#ifndef,iostream.h是C+标准输入输出库文件。C+的输入输出语句是cin ,cout。,K是表项关键码类型,E是表项类型,转Swap函数的实现,转minKey函数的实现,转dataList.h的使用,转类dataList的使用,52,上午9时45分,public: dataList (int size = 10) : listSize (size), element (new Esize) dataList ( ) delete element; void sort ( ); friend ostream #endif,友元函数,不是dataList类的成员函数,可能是一常规函数,或另一个类的成员函数,此处为常规函数。,友元函数:同上,转操作符的实现,转操作符的实现,转Sort函数的实现,#endif,53,上午9时45分,类中所有操作作为模板函数的实现 template void dataList : swap (int m1, int m2) /交换由m1, m2为下标的数组元素的值 E temp = element m1; element m1 = element m2; element m2 = temp; ,转Swap函数的声明,转Swap函数的使用,54,上午9时45分,template int dataList:minKey (int low, int high) /查找数组Elementlow到Elementhigh中具 /有最小关键码值的表项,函数返回其位置 int min = low; for (int i = low+1, i = high, i+) if ( elementi elementmin ) min = i; return min; ,后面的sick结构体中定义了重载操作符”“,转minKey函数的声明,转minKey函数的使用,55,上午9时45分,template ostream ,转操作符的声明,转操作符的使用,56,上午9时45分,template istream ,转操作符的声明,转操作符的使用,57,上午9时45分,template void dataList : sort ( ) /按非递减顺序对listSize个关键码element0到 /elementArraySize-1排序 for (int i = 0; i = listSize-2; i+) int j = minKey (i, listSize-1); /查找数组Elementi到ElementlistSize-1中具 /有最小关键码值的表项,函数返回其位置 if (j != i) swap (j, i); /交换由j,i为下标的数组元素的值 #endif,转Sort函数的声明,转minKey函数的声明,转Swap函数的声明,转Sort函数的使用,58,上午9时45分,使用模板的选择排序算法的主函数 #include using namespace std; #include “ dataList.h “ const int SZ = 10; int main ( ) struct sick /患者 int key; char *name15; int age; char *address30; bool operator (sick x) return key x.key; ;,转dataList的声明,重载原来的操作符“”,59,上午9时45分,dataList TestList (SZ); cin TestList; cout TestList endl; TestList.Sort ( ); cout TestList endl; return 0; ,定义对象时,代入实际数据类型,使用重载友元操作符“ ”,标准IO操作,转Sort声明,使用重载友元操作符“ ”,使用重载友元操作符“ ”,标准IO操作,K是表项关键码类型,E是表项类型,10个测试患者,转类dataList 声明,60,上午9时45分,算法简单性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,61,上午9时45分,算法的性能标准,正确性 (Correctness ) 算法应满足具体问题的需求。 可读性(Readability) 算法应该容易阅读。以有利于阅读者对程序的理解。 效率 效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。 健壮性 (Robustness) 算法应具有容错处理的功能。当输入非法数据时,算法应对其作出反应,而不应产生莫名其妙的输出结果。,62,上午9时45分,算法的后期测试,对一个算法要作出全面的分析可分成两个阶段进行,即事前分析和事后测试 事前分析要求事前求出该算法的一个时间界限函数。 事后测试则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。 事后分析要求在算法中的某些部位插装时间函数 time ( ),测定算法完成某一功能所花费时间。,63,上午9时45分,例如,给出顺序搜索 (Sequenial Search)算法 int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索与给定值 x 相等的元 /素,函数返回其位置,失败返回-1。 int i = 0; while ( i n ,64,上午9时45分,插装 time( ) 的计时程序 double start, stop; time( 事实上,算法运行时间要受输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。,转seqsearch函数的实现,标准计时函数,65,上午9时45分,算法的事前估计,算法的事前估计主要包括时间复杂性和空间复杂性的分析: 问题的规模:如:矩阵的阶数、图的结点个数、被分类序列的正整数个数等。 时间复杂性:算法所需时间和问题规模的函数,记为 T(n)。当 n 时的时间复杂性,称为渐进时间复杂性。 空间复杂性:算法所需空间和问题规模的函数。记为 S(n)。当 n 时的时间复杂性,称为渐进空间复杂性。,66,上午9时45分,空间复杂度度量,存储空间的固定部分 程序指令代码的空间,常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,67,上午9时45分,空间复杂度,可以估计的情况,不好估计的情况 动态存储分配的空间复杂度,68,上午9时45分,时间复杂度度量,编译时间 运行时间 程序步 语法上或语义上有意义的一段指令序列; 执行时间与问题规模无关; 例如:注释:程序步数为0; 声明语句:程序步数为0; 表达式:程序步数为1,69,上午9时45分,执行时间与问题规模有关; 表达式: 赋值语句: 循环语句: switch语句: if_then语句: 函数执行/函数调用语句: 动态存储管理语句: 转移语句:,70,上午9时45分,程序步确定方法 插入计数全局变量count 建表,列出各语句的程序步数,例 以迭代方式求累加和的函数 float sum (float a , int n) float s = 0.0; for (int i = 0; i n; i+) s = s + ai; return s; ,71,上午9时45分,在求累加和程序中加入 count 语句 float sum (float a , int n) float s = 0.0; count+; /针对赋值语句 for (int i = 0; i n; i+) count += 2; /针对 for 语句 s += ai; count+; /针对赋值语句 count += 2; /针对 for 的最后一次 return s; count+; /针对 return 语句 执行结束得程序步数 count = 3*n+4,72,上午9时45分,程序的简化形式 void sum (float a , int n) for (int i = 0; i n; i+) count += 3; count += 4; ,73,上午9时45分,注意: 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。如下分析: 例如: 赋值语句x = sum (R, n) 本身程序步数为 1; 一次执行对函数 sum (R, n) 的调用需要的程序步数为 3*n+4; 一次执行x = sum (R, n)的程序总步数为 1+3*n+4 = 3*n+5,74,上午9时45分,计算累加和程序 程序步数计算工作表格,75,上午9时45分,时间复杂度的渐进表示法,例 求两个n阶方阵的乘积C = AB,void MatrixMultiply (int Ann, int Bnn, int Cnn) for (int i = 0; i n; i+) 2n+2 for (int j = 0; j n; j+) n(2n+2) Cij = 0; n2 for (int k = 0; k n; k+) n2(2n+2) Cij = Cij + Aik * Bkj; n3 ,3n3 + 5n2 + 4n +2,76,上午9时45分,时间复杂度的渐进表示法,算法中所有语句的频度之和是矩阵阶数n的函数 T(n) = 3n3 + 5n2 + 4n +2 一般地,称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。 当n趋于无穷大时,把时间复杂度的数量级(阶)称为算法的渐进时间复杂度 T(n) = O(n3) 大O表示法,77,上午9时45分,各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n! 加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m),78,上午9时45分,T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2),并列程序段,79,上午9时45分,乘法规则 针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 渐进的空间复杂度 S (n) = O(f (n) 两个并列循环 其中一个嵌套循环的例子,80,上午9时45分,void exam (float x , int m, int n) float sum ; for (int i = 0; i m; i+) /x中各行 sumi = 0.0; /数据累加 for (int j = 0; j n; j+) sumi += xij; for (i = 0; i m; i+) /打印各行数据和 cout i “ : “ sum i endl; 渐进时间复杂度为 O(max (m*n, m),81,上午9时45分,起泡排序 void bubbleSort (int a , int n ) /对表 a 逐趟比较, n 是表当前长度 for (int i = 1; i = i; j-) /n-i次比较 if (aj-1 aj) int tmp = aj-1; aj-1 = aj; aj = tmp; /一趟比较 ,82,上午9时45分,渐进时间复杂度 O(f (n)*g (n) = O(n2),83,上午9时45分,有时, 算法的时间复杂度不仅依赖于问题规模 n,还与输入实例的初始排列有关。 在数组 An 中查找给定值 k 的算法: int i = n-1; while (i = 0 算法的语句 i- 的频度不仅与 n 有关,还与 A 中各元素的取值以及 k 的取值有关。,84,上午9时45分,例:设有两个算法在同一机器上运行,其执行时间分别为 100n2 和 2n,问:要使前者快于后者,n 至少要取多大? 解答: 问题是找出满足 100n2 2n = 8192 n = 14时,100n2 = 19600 2n = 16384 n = 15时,100n2 = 22500 2n = 32764 取 n = 15 满足要求。,85,上午9时45分,出错处理问题举例,试编写一个函数计算 n!*2n 的值,结果存放于数组 An 的第 i 个数组元素中 (0 i n)、 (教材习题1.18) 若设计算机中允许的整数的最大值为 maxInt,则当 i arraySize 或者对于某一个 k ( 0 k n ),使得k!*2k maxInt 时,应按出错处理。,86,上午9时45分,可有如下几种不同的出错处理方式:,用 cerr 及 exit (1) 语句来终止执行并报告错误; 用返回整数函数值 0, 1 来实现算法,以区别是正常返回还是错误返回; 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回。 抛出异常。,87,上午9时45分,#include #define n 100 #define maxInt 0x7fffffff /4字节, 0x表示16进制数 bool calc (int T , int n) int i, value = 1; if ( n != 0 ) for (i = 1; i maxInt / n / 2) return false; /直接判断 i!*2i MaxInt 是危险的 value *= n * 2; ,88,上午9时45分,Tn = value; /n!*2n Tn return true; void main ( ) int An, i; for (i = 0; i n; i+) if (!calc (A, i) cout “failed at “ i endl; break; ,89,上午9时45分,李春葆教材P26 1.5(3) 下面程序段的时间复杂性的量级为【 】 int fun(int n) int i0,s0; while(sN) s+=+i; return i; ,90,上午9时45分,(3) 设 while循环语句执行次数为T( n ),则: s = 1+2+3+ + T( n )= s n-1 T 2 ( n ) + T( n ) 2n 2 当 n - , T 2 ( n ) - n T( n ) = O ( ),91,上午9时45分,1.3 设三个函数f,g和h分别为: f(n)=100n3+n2+1000 g(n)=25n3+5000n2 h(n)=n1.5+5000nlog2n 请判断下列关系式是否成立: A.f(n)=O(g(n) B. ( g(n)=O( f(n) C.h(n)=O(n1.5) D.h(n)=O(nlog2n),李春葆第一章习题讲解,92,上午9时45分,李春葆第一章习题讲解,1.3 A. f( n ) = 100n3 + n2 + 1000 = O ( n3 ) g( n ) = 25n3 + 5000n2 = O ( n3 ) f( n ) = O ( g(n) ) 成立 B. 由A的分析可知,g( n ) = O ( f(n) ) 成立 C.当n-时, log2n n1.5 nlog2n h( n ) = n1.5 + 5000 nlog2n = O (n1.5) 等式成立 D.由C分析可知,等式不成立。,93,上午9时45分,1.5设n为正整数,给出下列各种算法关于n的时间复杂度 (1) void fun1(int n) int i=1,k=100; while(in) k=k+1; i+=2; ,94,上午9时45分,1.5(2) void fun2(int b,int n) int i,j,k,x; for(i=0;ibj) k=j; x=bi;bi=bk;bk=x; ,95,上午9时45分,1.5 (1)设while循环语句执行次数为T(n),则: i n-1 i = 2T(n)+1 所以 2T(n)+1 n-1 T(n) T(n) = O ( n ) (2) 设基本运算语句 if ( b k b j ) k = j 的执行次数为T(n),则: T(n) = = = n ( n-2 ) -1 + n ( n - 3 ) 1 + + n 0 1 = 1 + 2 + + ( n -2 ) + ( n - 1 ) = O ( n2 ),96,上午9时45分,1.6下面程序段的时间复杂度为多少? void mergesort(int i,int j) int m; if(i!=j) m=(i+j)/2; mergesort(i,m); mergesort(m+1,j); merge(i,j,m); 其中,mergesort()用于数组an的归并排序,调用方式为mergesort(0,n-1);merge()用于两个有序子序列的合并,是非递归函数,它的时间复杂度为O( n ),97,上午9时45分,1.6 分析得到如下的递归关系: O( 1 ) n = 1 T ( n ) = 2 T( ) + O ( n ) n1 O ( n )为merge()所需的时间,设为cn(c为常量),则: T ( n ) = 2 T( ) + cn = 2 ( 2T ( ),- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构概念 数据结构 概念 PPT 课件
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文