数据结构与算法分析PPT课件.ppt

1 主讲 朱立华副教授南邮计算机学院E mail zlhlgy DATASTRUCTURE 2 教材 1 数据结构部分 数据结构 用C 语言描述 陈慧南主编 南大学出版社2 算法分析与设计部分 计算机算法设计与分析 王晓东编著 电子工业出版社课时安排 第一次面授 数据结构 第一章到第五章第二次面授 数据结构 第六章到第十章第三次面授 算法分析 第二章到第七章 部分 考试时间及方式 第三次面授最后半天 复习加考试 开卷 3 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 内容提要 1 给出数据结构的概念2 介绍抽象数据类型和面向对象的基本概念3 回顾C 语言的基本特征4 说明数据结构的描述方法5 介绍算法和算法分析的基本方法 第一章绪论 数据结构 DATASTRUCTURE 4 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 1什么是数据结构 在程序设计时就已经遇到过 一维数组是一个数据结构例如 一维数组A a1 a2 a3 a4 inta 4 定义并创建一维整型 数组 a 0 a 1 a 2 a 3 x a 2 读数组元素a 2 的值a 2 x 置a 2 的值为x 数据结构由数据元素依某种逻辑关系组织起来 在数据结构上需要定义一组操作 运算 1 数据结构学科的定义 主要是为研究和解决如何使用计算机处理非数值问题而产生的理论 技术和方法 5 1 数据 是信息的载体 是计算机加工处理的对象 2 数值数据和非数值数据 1 数值数据 包括整数 实数或复数 主要用于工程计算 科学计算 2 非数值数据 包括字符 文字 图形 图象 语音等 用于情报检索 企业管理 图形图象 人工智能 远程教育 远程医疗 电子商务 电子图书馆和办公自动化等诸多领域 3 数据元素 组成数据的基本单位 第一章绪论1 1什么是数据结构一 数据和数据元素二 什么是数据结构 一 数据和数据元素 6 例如 一维数组A a1 a2 a3 a4 1 数据元素间的逻辑关系 B D R 其中 D是数据元素的有限集合 R是D上关系的有限集合 本书中一般只考虑R包含一个关系的情况 即R r D a1 a2 a3 a4 r R r 第一章绪论1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例 1 数据元素之间的逻辑关系 二 什么是数据结构 1 数据结构举例 7 1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例 1 数据元素之间的逻辑关系 2 数据在计算机内的表示 2 数据在计算机内的表示 例如 一维数组A a1 a2 a3 a4 8 Create 建立一个数组 Retrieve i 返回下标为i的元素值 Store i x 将下标为i的数据元素的值置为x 1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例 1 数据元素之间的逻辑关系 2 数据在计算机内的表示 3 运算的定义和算法 3 运算的定义和算法 例如 inta 4 定义一个一维整型数组 a 0 a 1 a 2 a 3 x a 2 读数组元素a 2 的值a 2 x 置a 2 的值为x 9 2 4种基本的逻辑结构 集合结构 结构中的数据元素之间除了 同属于一个集合 的关系外 别无其它关系 线性结构 结构中的数据元素之间存在一对一的关系 树形结构 结构中的数据元素之间存在一对多的关系 图结构 结构中的数据元素之间存在多对多的关系 1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例2 4种基本的结构关系3 什么是数据结构 10 1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例2 4种基本的结构关系3 什么是数据结构 2 4种基本的逻辑结构 11 第一章绪论1 1什么是数据结构一 数据和数据元素二 什么是数据结构1 数据结构举例2 4种基本的结构关系3 什么是数据结构 数据结构包括以下四个方面 1 数据元素及特性是数据结构中的最基本信息单元 2 数据的逻辑结构对数据元素间的逻辑关系的描述 3 数据的存储表示 存储结构 数据在计算机内的组织方式 4 运算的定义和算法数据结构上执行的运算和实现 3 什么是数据结构 12 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 2数据抽象和抽象数据类型 抽象 抽取事物的共同的和实质的东西 忽略其非本质的细节 例如 学生 这一概念是对学生群体的抽象 它抽取了学生这一群体的共性 忽略了每个学生的特殊性 13 第一章绪论1 2数据抽象和抽象数据类型一 数据类型1 C语言的数据类型二 数据抽象三 抽象数据类型 一 数据类型 1 C语言的数据类型 1 基本类型 字符 整数 枚举 实数 双精度数 2 构造类型 数组 结构和联合 3 指针类型 指针 例如 二维整型数组inta 3 5 定义了一个包含15个整数的二维数组 14 第一章绪论1 2数据抽象和抽象数据类型一 数据类型1 C语言的数据类型二 为什么要研究数据结构三 什么是数据结构 又如 结构类型structStudent char name intstudent id chargrade 定义了结构类型Student 包括以下三个域 name student id和grade 15 第一章绪论1 2数据抽象和抽象数据类型一 数据类型1 C语言的数据类型2 数据类型二 数据抽象三 抽象数据类型 2 数据类型一个数据类型定义了一个值的集合以及作用于该值集的操作的集合 例如 inta 变量a的取值范围是 32768 32767对变量a执行的操作有 算术运算 关系运算 赋值运算 16 第一章绪论1 2数据抽象和抽象数据类型一 数据类型二 数据抽象三 抽象数据类型 二 数据抽象 数据类型 是具有相同值集和操作集的数据对象 变量和常量 的抽象 相同的数据类型的变量具有相同的取值范围 允许执行相同的操作 对变量执行允许的操作 可以不必考虑变量在计算机内的存储细节和这些操作是如何执行的 17 第一章绪论1 2数据抽象和抽象数据类型一 数据类型二 数据抽象三 抽象数据类型 三 抽象数据类型 抽象数据类型 abstractdatastructureADT 是一个数据类型 其主要特征是该类型的对象及其操作的规范 与该对象的表示和操作的实现分离 即使用和实现分离 并实行封装和信息隐蔽 18 第一章绪论1 2数据抽象和抽象数据类型一 数据类型二 数据抽象三 抽象数据类型 例如 inta 整型int的规范包括变量a的取值范围是 32768 32767对变量a执行的操作有 算术运算 关系运算 赋值运算 整型int的实现是指变量a在计算机内存储表示方法 操作的实现是指整型上定义的操作的具体实现方法 19 第一章绪论1 2数据抽象和抽象数据类型一 数据类型二 数据抽象三 抽象数据类型 使用和实现分离 使用者通过规范使用该类型的数据 而不必考虑其实现细节 改变实现将不影响使用 封装和信息隐蔽 将数据和代码组合在一起 数据类型的细节对外部是隐蔽的 例如 inta 其实现是隐蔽的 使用者只能通过整型上定义的一组运算对变量a执行操作 20 第一章绪论1 2数据抽象和抽象数据类型一 数据类型二 数据抽象三 抽象数据类型四 数据结构的规范和实现 数据结构可分成以下两部分 1 数据结构的规范 逻辑结构和运算的定义 2 数据结构的实现 存储结构和运算算法实现 规范是实现的准则和依据 规范指明 做什么 实现解决 怎样做 21 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象方法1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 3面向对象方法 例子 问题的陈述 开发一个非常简单的字处理程序 该系统允许用户产生文档 所产生的文档存储在一个用户目录中 用户可以打印和显示文档 文档可以改变 也可以被删除 对象服务文档产生 存储 打印显示 改变 删除目录存储 删除 22 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象方法1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 3面向对象方法 对象 应用领域内的实体和概念 它们通常是问题陈述中的名词 属性 刻划对象的特征 服务或运算 施于对象属性的操作 它们通常是问题陈述中的动词 同类对象具有相同的属性和服务 同一个类 class 中的每个对象称为该类的一个实例 23 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象方法1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 继承 是指派生类 子类 可自动共享基类 父类 的公有的和保护的属性和服务的机制 它是面向对象方法最重要的共享机制 从而减少数据和代码的重复 这也是面向对象方法最有特色的方面 24 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 4C 程序设计 回顾C 语言的基本特征 内容提要 1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承和派生类1 4 5多态性 虚函数和动态联编1 4 6纯虚函数和抽象类1 4 7模板 25 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数的返回值3 函数原型 1 4 1函数与参数传递 includeintAbc inta int 1 传值参数与引用参数 见dsapg4 cpp 运行结果 z 8 x 3 y 4 原因 x3a3a a4y3y4bb b 26 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数的返回值3 函数原型 常量引用参数 constint c 见dsapg4 cpp includeintAbc inta constint 运行结果 z 6 27 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数的返回值3 函数原型 函数执行时 1 传值参数 实在参数的值赋给了形式参数 形式参数得到了实在参数的一个副本 函数执行后 实在参数的值不会改变 2 引用参数 实在参数的地址传给了形式参数 函数执行后 实在参数的值将可能改变 常量引用参数 函数不得修改该引用参数 否则将导致编译出错 28 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数返回值3 函数原型 1 函数返回一个值intAbc inta int 2 函数返回值 见dsapg5 cpp 29 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数的返回值3 函数原型 3 函数原型 函数原型包括 函数名 返回类型和参数表 例如 下面的程序由三个文件组成 greet h greet cpp main cpp 见greet文件夹 存放在头文件greet h voidGreet 函数原型 30 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 传值参数和引用参数2 函数的返回值3 函数原型 存放在源代码文件greet cpp中 include include greet h 预处理指令voidGreet 函数 charName 16 cout enteryourname cin get Name sizeof Name cout ngreetings Name n 存放在源代码文件main cpp中 include greet h 预处理指令voidmain 主程序 Greet 31 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配 1 4 2动态存储分配 C语言的动态分配和释放函数 malloc 和free int x x int malloc sizeof int x 10 printf x d n x free x inta 100 32 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配 例如 int y y newint y 10 三步合并为 int y newint 10 C 的动态分配和释放函数 new 和delete 33 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配 例如 分配包括10个整数的数组int a newint 10 a 2 5 a 3 7 a 3 7 printf a 2 d n a 2 printf a 3 d n a 3 释放数组空间delete a 例见dsapg6 cpp C 的数组动态分配和释放 new 和delete 34 1 C 类 数据和操作组合成类 C 类体现了抽象数据类型的思想 支持面向对象程序设计 实现封装和信息隐蔽的原则 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类 1 4 3C 类 三种存取级别 public private protected 35 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类 public域 共有成员 可被程序的其它部分访问 private域 私有成员 只能由该类的成员函数以及被声明为友元的函数或类的对象访问 protected域 保护成员 除了具有private访问权限外 还允许该类的子类访问它们 private域用来保护对象内部的数据 实现信息隐蔽 private是缺省的存取级别 36 完整程序见dsapg7 cpp classFaculty C 类举例protected char name intage public Faculty char name intage Faculty voidChange char name intage 建立类的对象 实例化 Faultyemp Faulty emp1 newFaulty deleteemp1 释放对象存储空间 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类 37 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载 ComplexComplex operator constComplex 复数相加 38 C 编译器将com1 com2解释为 com1 operator com2 表达式com1 100是错误的 因为100不是Complex类的一个对象 TheEnd 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载 39 3 友元函数和友元类 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载3 友元函数和友元类 友元函数 在类的声明中使用了保留字friend 给出一个普通函数的原型 将此函数定义为该类的友元函数 友元类 在类的声明中使用了保留字friend 将另一个类的所有函数定义为该类的友元函数 40 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载3 友元函数和友元类 友元类举例classY classX friendY classY 友元函数可以存取类的私有成员和保护成员 41 程序见dsapg8 cpp classComplex private doublereal image public 构造函数Complex real 0 0 image 0 0 Complex doubler doublei 0 0 real r image i Complex Complex 2020 1 9 42 43 重载加法操作符 实现两个复数相加Complexoperator Complex 44 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载3 友元函数和友元类 voidmain Complexc1 2 3 c2 5 6 c3 c3 c1 c2 cout c1 c2 c3 运行结果2 3 0i5 6i7 3 6i 定义3个复数对象 c1 2 3 c2 5 6i c3计算 c3 c1 c2 45 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类 1 4 4继承性和派生类 继承性 派生类继承基类所定义的数据和方法 public继承性 派生 基类所有的公有成员成为派生类的公有成员 基类所有的保护成员成为派生类的保护成员 46 classFaculty protected char name intage public Faculty char name intage Faculty voidChange char name intage classProfessor publicFaculty public voidChangeLevel intn Professor char name intage intlevel Professor private intlevel C 类Faculty Professor继承了Faculty所定义的数据和方法 本例称为public继承 派生 从类Faculty派生类Professor 47 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编 1 4 5多态性 虚函数与动态联编 多态性 允许同一个函数 或操作符 有多个版本 对不同的对象执行不同的版本 1 函数或操作符重载 2 虚函数 1 多态性 48 一个虚函数的例子 见dsapg10 cpp includeclassBase public virtualvoidwho cout Base n 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编 虚函数 虚函数在基类中被声明为virtual 并在一个或多个派生类中被重定义 2 虚函数 49 classfirst d publicBase public voidwho cout Firstderivation n classsecond d publicBase public voidwho cout Secondderivation n main void Base p Basebo first dfo second dso p 输出结果 BaseFirstderivationSecondderivation 50 动态联编与静态联编 当一个派生类的对象用基类指针指示时 C 将根据该指针所指向的派生类对象的实际对象类型 在运行时确定应调用哪一个函数 这种在运行时才将对象连接到它的成员函数的做法称为动态联编 动态联编是通过使用派生类和虚函数来完成的 在编译时已明确所调用的对象的成员函数 称为对函数的静态联编 如函数调用 重载函数和操作符调用 3 动态联编 Complexc1 2 3 c2 5 6 c3 c3 c1 c2 p 51 4 操作符重载 在构造类时 如果希望能使用C 的操作符 对类的对象进行操作 必须重新定义操作符的意义 称为操作符重载 保留字operator称为操作符函数名 后跟需重定义的操作符 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 C 类2 操作符重载 重载加法运算符 为了将加法运算符 用于复数相加 可重载加法运算符 ComplexComplex operator constComplex c 52 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编1 4 6纯虚函数与抽象类 1 4 6纯虚函数与抽象类 纯虚函数 在基类中只给出虚函数的声明而不给出具体定义的虚函数称为纯虚函数 抽象类 至少有一个纯虚函数的类称为抽象类 抽象类不能生成实例 因为抽象类中至少有一个函数无定义 抽象类作为基类被其它类继承 53 包含纯虚函数的类称为抽象类 纯虚函数被初始化为0 对dsapg10 cpp直接修改 classBase public virtualvoidwho 0 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编1 4 6纯虚函数与抽象类 54 classfirst d publicBase public voidwho cout Firstderivation n classsecond d publicBase public voidwho cout Secondderivation n main void Base p first dfo second dso p 输出结果 FirstderivationSecondderivation 55 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编1 4 6纯虚函数与抽象类1 4 7模板 1 4 7模板 模板函数的定义 template其中 T1 Tn为n个通用数据类型参数 保留字class可以称为类型 使用该模板函数时 将以实在的参数类型取代通用数据类型 1 模板函数 使用通用的函数代码处理不同的数据类型 56 voidmain intx 2 intz Abc 3 x cout z z floatr 2 2F r1 3 2F floaty Abc r1 r cout y y Complexc1 2 3 c2 5 6 Complexc3 Abc c1 c2 cout c3 c3 运行结果 z 5y 5 4c3 7 3 6i 见dsapg12 cpp templateT 其中 a为传值参数 b为引用参数 函数返回一个引用参数 57 第一章绪论1 4C 程序设计1 4 1函数与参数传递1 4 2动态存储分配1 4 3C 类1 4 4继承性和派生类1 4 5多态性 虚函数与动态联编1 4 6纯虚函数与抽象类1 4 7模板 模板类的定义 template其中 T1 Tn为n个通用数据类型参数 模板类的成员函数如果在类声明外部定义时 必须定义为带模板参数的模板函数 所有将类作为类型的引用都必须包含模板类型 2 模板类类的定义中包含通用类型的数据成员和成员函数 58 程序1 1堆栈类 见dsapg13 cpp 基类Stack为 抽象类 模板类constintMaxSize 50 templateclassStack public Stack 构造函数virtualvoidPush constT 判断堆栈是否满 59 constintMaxSize 50 templateclassSeqStack publicStack 派生类 顺序栈SeqStackprivate Ts MaxSize inttop public SeqStack top 1 构造函数voidPush constT 60 主程序 建立一个数据元素为整数的顺序栈实例istkvoidmain 模板类实例化 应给出实在类型SeqStackistk 建立一个整数顺序栈对象istk Push 5 向栈中插入整数5istk Push 9 向栈中插入整数9cout istk Top endl 输出栈顶元素9istk Pop 删除栈顶元素9cout istk Top endl 输出栈顶元素5 61 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 5数据结构的描述 1 数据结构的抽象层次数据结构抽象为一种聚集结构 62 数据结构被看成是一个类属抽象数据类型 用格式化的自然语言来描述之 另外 数据结构可以形式地用一个C 的抽象模板类描述之 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 2 数据结构的描述方法 63 堆栈数据结构举例 64 ADT1 1栈抽象数据类型ADTStack Data 零个或多个元素的线性序列 a1 a2 an 遵循LIFO原则 Operations Create 创建一个空栈 Push x 在栈中插入元素x Pop 删除栈顶元素 Top 返回栈顶元素 IsEmpty 若栈空 则返回true 否则返回false IsFull 若栈满 则返回true 否则返回false 用ADT描述数据结构 堆栈的例子 65 程序1 2栈的C 抽象类templateclassStack public Stack virtualvoidPush constT除了构造函数 其余成员函数都是纯虚函数 顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现 它是从抽象类Stack派生出来的 它可以实例化 66 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 1 6算法及其性能分析 内容提要 1 6 1算法及其性能分析1 6 2算法的空间复杂度1 6 3算法的时间复杂度1 6 4渐近时间复杂度 67 1 什么是算法一个算法 algorithm 是对特定问题的求解步骤的一种描述 它是指令的有限序列 此外 算法具有下列五个特征 1 输入算法有零个或多个输入 2 输出算法至少产生一个输出 3 确定性算法的每一条指令都有确切的定义 没有二义性 4 能行性算法的每一条指令都足够基本 它们可以通过已经实现的基本运算执行有限次来实现 5 有穷性算法必须总能在执行有限步之后终止 1 6 1算法及其性能分析 68 2 算法描述方法算法可以自然语言 表格法 流程图或程序设计语言描述 当一个算法用程序设计语言描述时 便成为程序 本书中主要使用C 语言描述 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 69 3 算法的性能标准 1 正确性算法的执行结果应当满足预先规定的功能和性能要求 2 简明性一个算法应当思路清晰 层次分明 简单明了 易读易懂 3 健壮性当输入不合法数据时 应能做适当处理 不至于引起严重后果 4 效率有效使用存储空间和有高的时间效率 5 最优性解决同一个问题可能有多种算法 应进行比较 选择最佳算法 70 算法的空间复杂度 是程序运行从开始到结束所需的存储量 1 6 2算法的空间复杂度 问题实例的特征 与问题的具体实例有关的量 例如 对一组特定个数的元素进行排序 对该组元素的排序是排序问题的一个实例 元素的个数可视为该实例的特征 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 71 程序运行所需的存储空间包括两部分 1 固定部分这部分空间与所处理数据的大小和个数无关 或者称与问题的实例的特征无关 主要包括程序代码 常量 简单变量 定长成分的结构变量所占的空间 2 可变部分这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关 例如 分别为100个元素的两个数组相加 与分别为10个元素的两个数组相加 所需的存储空间显然是不同的 72 1 6 3算法的时间复杂度 程序步 一个程序步是指在语法上或语义上有意义的程序段 该程序段的执行时间与问题实例的特征无关 算法的时间复杂度 是程序运行从开始到结束所需的时间 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 73 程序1 2求一个数组元素的累加之和floatsum floatlist constintn floattempsum 0 0 count 针对赋值语句for inti 0 i n i count 针对for语句tempsum list i count 针对赋值语句 count 针对for的最后一次执行count 针对return语句returntempsum 返回 count是全局变量 用来计算程序步数 每一程序步均与问题实例的规模n无关 程序步数为2n 3 74 1 6 4渐近时间复杂度 一 大O记号 如果存在两个正常数c和n0 使得对所有的n n n0 有f n cg n 则有f n O g n 即函数f n 当n充分大时上有界 且g n 是它的一个上界 也称f n 的阶不高于g n 的阶 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 例如 设T n 3 6n3 2 5n2 2 8 取n0 1 则当n n0时 T n 3 6n3 2 5n3 2 8n3 8 9n3取c 8 9 则根据大O记号的定义得 T n O n3 75 渐近时间复杂性 使用大O记号表示的算法的时间复杂性 称为算法的渐近时间复杂性 在大O记号下 可用程序步来估计算法的执行时间 很多情况下 可以通过考察一个算法中的关键操作 关键操作被认为是一个程序步 的执行次数来计算算法的渐近时间复杂性 常见的渐近时间复杂性从小到大排列有 O 1 O log2n O n O nlog2n O n2 O n3 76 例如 程序1 2为求一个数组元素的累加之和的算法 1 其总的程序步数为2n 3 则渐近时间复杂性为O n 2 语句tempsum list i 可认为是关键操作 它的执行次数为n次 则渐近时间复杂性为O n 第一章绪论1 1什么是数据结构1 2数据抽象和抽象数据类型1 3面向对象程序设计1 4C 程序设计1 5数据结构的描述1 6算法及其性能分析 77 voidMult