页数：102页文件大小：1.87 MB来源： 数据结构ppt课件
本课件为课程绪论，从为什么学习数据结构入手，给出数据、数据元素、逻辑结构与存储结构的严格定义，介绍线性、树、图等逻辑结构与顺序、链接、索引、散列四类存储映射，并讲解算法的特性、ADL 描述语言、正确性证明方法与时间复杂性分析。
数据结构第一章绪论
课程相关信息教材：《数据结构》，刘大有等编著，高等教育出版社，2010年9月.参考书目：苏运霖译Donald E. Knuth著.计算机程序设计艺术（第一卷基本算法；第二卷半数值算法；第三卷排序与查找），国防工业出版社。清华大学出版社、高等教育出版社和机械出版社等出版的数据结构教材.教学形式：理论＋实验考核方式：考试
第一章绪论1.1为什么要学习数据结构1.2数据结构概念1.3算法1.4算法的正确性证明1.5算法分析基础
为什么学习数据结构计算机学科中一门重要的专业基础课；是程序设计的重要基础；是许多计算机专业课的基础，如算法分析、编译原理、操作系统、数据库系统等。
教学计划第一章绪论(算法分析基础)第二章线性表、堆栈、队列第三章数组、字符串第六章递归第四章树第五章图第七章排序第八章查找
第一章绪论1.1为什么要学习数据结构1.2数据结构概念1.3算法1.4算法的正确性证明1.5算法分析基础
计算机算法与数据结构方面最权威的经典巨著——计算机程序设计艺术第一、二、三卷D. E. Knuth（D. E.克努斯）
1974年，因克努斯在算法分析和编程语言设计方面的突出贡献，荣获美国计算机协会图灵奖（计算机界的诺贝尔奖），是历史上最年轻的获奖者。《计算机程序设计艺术》一书与牛顿的《自然哲学的数学原理》等书一起，被评为“世界历史上最伟大的十种科学著作”之一。
1.数据定义1.1数据是指对象的表示，即按照适合于通信、解释或处理（借助人或自动装置）的方式所形成的关于事实、概念或指令的表示；数据只是表示，而无含义[3]。[3]张效祥等.计算机科学技术百科全书.北京:清华大学出版社，2005
数据是计算机科学与技术中最基本的概念，它是计算机程序要处理的“原料”，是所有被计算机识别、存储和加工处理的符号的总称[4,5]。[4]管纪文，刘大有.数据结构.北京:高等教育出版社，1988.[5]刘大有，唐海鹰等.数据结构.北京:高等教育出版社，2001
数据不仅仅指整数和实数，计算机可以处理的字符串、图像、声音等都被称为数据。例如，一个简单的数值计算程序所使用的数据是一些实数或整数，一个编译程序使用和加工的数据是源程序，而一个能修改自身的计算机程序所使用和加工的数据（对象）就是其自身。
数据元素（或曰数据成分）还可被称为元素、结点或顶点等,是组成数据的基本单位。数据元素可大可小，大到可以是一篇文稿、一本书，小到可以是一个字符，甚至是计算机二进制数中的一位。数据元素可由若干个数据项（也称为域或字段）组成，数据项是构成数据的最小单位。
通讯录表：例1.1 通讯录表，表中每一行表示一个结点，每个结点由姓名、区号、办公电话和手机号码四个域组成。
| 姓名 | 区号 | 办公电话 | 手机号码 |
|---|---|---|---|
| 赵甲 | 010 | 63644587 | 13911001234 |
| 钱乙 | 020 | 89634159 | 13809771333 |
| 孙丙 | 021 | 45976528 | 13916586666 |
| 李丁 | 024 | 63427541 | 13804076111 |
数据结构
逻辑结构
数据的逻辑结构从较抽象的角度刻画了数据结构所具有的数学性质,将数据元素抽象为结点,数据元素之间的关系;连接结点的边。一个逻辑结构可形式定义为一个二元组：L=(N,R)，其中，N是有限结点集合，R是定义在集合N上的二元关系r的集合。
设L=(N,R)是一个逻辑结构.r1∈R是与线性结构、树结构和二叉树对应的一种关系，若a，b∈N，且(a，b)∈r1，则称a是b的前驱结点，b是a的后继结点，a和b是相邻结点.若a∈N，但不存在y∈N使得(y，a)∈r1，则称a为始结点；若d∈N，但不存在y∈N使得(d，y)∈r1，则称d为终结点.abcd
设L=(N,R)是一个逻辑结构.r2∈R是与图结构对应的一种关系。若a,b∈N且(a,b)∈r2，则称a和b是相邻结点；对于有向图结构，若存在(a，b)∈r2，则称a是b的前驱结点，b是a的后继结点。uaubucud
逻辑结构分类
一般以关系为逻辑结构的分类准则。据此，数据的逻辑结构可分为两类：线性结构和非线性结构。
(1)线性结构线性结构是n个数据元素(简称元素，结点)的有序集合.它有四个基本特征：1.集合中存在唯一一个首元素;2.集合中存在唯一一个尾元素;3.除尾元素外，其它数据元素均有唯一的后继;4.除首元素外，其它数据元素均有唯一的前驱.数据结构中，结点（或元素）间的关系是线性关系，也称前后关系、大小关系等。
若线性结构的结点数为1，则该结点既是始结点又是终结点；若线性结构的结点数≥2，始结点有一个后继，终结点有一个前驱，中间结点有且仅有一个前驱和一个后继。
(2)非线性结构非线性结构之结点可能有多个前驱结点和多个后继结点（这里的多个系指有限多个）。“树”（层次结构）和“图”是两种主要的非线性结构。
树也称为树形结构、树结构等。树中有且仅有一个没有前驱结点的结点，称为根结点；其他结点都只有一个前驱结点。树中结点允许有多个后继结点。从根结点到任一非根结点，有且仅有一条路径。树中的关系r也称为层次关系、父子关系等。图也称为图结构、网络结构等。图中任意结点的前驱结点和后继结点的个数可以是0个或多个。图中的关系r也称为相邻关系。
有些书也将数据的逻辑结构分为集合、线性结构、树和图等四种类型。其中，集合的特点是：结构中的数据元素之间除了同属于一个集合的关系外，别无其他关系。集合线性结构树图
存储结构
3．存储结构在计算机存储器中，人们希望能利用高级程序语言，通过数据结构的存储结构来实现其逻辑结构。数据的存储结构是指数据的逻辑结构在计算机中所需的存储空间、空间的构成结构及对该存储结构的访问方式等的总称[3]。数据的存储结构系指逻辑结构到存储空间的映射。对逻辑结构L=(N,R)，建立映射：N→M（存储区域），其中每个结点对应M中唯一的连续存储单元，每个关系元组(a,b)∈r被映射为存储单元的地址顺序关系，或指针地址的指向关系。
基本的存储映射方法有:顺序、链接、索引和散列等方法。
1）顺序存储结构把一组结点存放在地址相邻的存储单元中，结点间的逻辑关系用存储单元的自然顺序关系表达。302A[0]304306308A[1]A[2]A[3]
342）链接存储结构在结点的存储结构中附加指针字段，两个结点的逻辑后继关系用指针的指向来表达。(a)可用存储空间freea0a2a1a3 firstlast(b)执行创建单链表操作后
3）索引存储结构索引表把整数索引值映射到结点的存储地址。索引表存储一串指针，每个指针指向存储区域的一个数据结点。0231V0V1V2V
4）散列存储结构适用于大数据量、高速检索的场合。索引存储的一种延伸和扩展，利用散列函数进行索引值的计算，并通过索引表求出结点的指针地址。0231V0V1V2V3f(v)v
存储结构总结顺序、链接、索引和散列存储结构，可以单独使用，也可以组合使用。存储结构要正确反映逻辑结构，并便于操作。
381.2.3对数据结构的操作简介几种数据逻辑结构上的常用操作。插入：向数据结构中增加新结点；删除：将指定的结点从数据结构中删除；修改：改变指定结点的一个或多个字段的值；排序：将某集合中的结点按某种序关系进行排列；查找：在某结点集合中寻找关键词域之值等于给定变元K的结点，或寻找属性值满足特定条件的一些结点。
第一章绪论1.1为什么要学习数据结构1.2数据结构的概念1.3算法1.4算法的正确性证明1.5算法分析基础
§1.3算法算法（Algorithm）概念最早出现在1747年出版的一本德文《大全数学辞典》中.《Webster词典》指出:算法系指在有限步骤内解一个数学问题的过程，步骤中常包括某一操作的重复。计算机算法：欲完成解题任务，除选取适当的数据结构外，还要给出解决问题的切实可行的方法和步骤。1967年，克努斯指出:“计算机科学是有关算法的学问”，并指出“对所有的计算机程序设计来说，算法的概念总是最基本的”。
数据结构与算法紧密相关。算法无疑也是本书的重要内容。
1.3.1算法及其特性定义1.3一个算法就是一个有穷规则的集合，其中的规则规定了一个解决某一特定类型问题的运算序列；此外，它还应具有如下5个重要特性：有限性：一个算法在执行有限步骤后必然终止；确定性：对算法的每个步骤，每个动作都必须给出严格、无歧义的描述（定义）；输入：一个算法有0个或多个输入；输出：算法有1个或多个输出；
可行性：算法的所有操作都必须是充分基本的，原则上人们用纸和笔都可在有限时间内精确的完成它们。
假若一组规则，除有限性之外，具有2)至5)四大特征，则称其为计算方法。即使是算法，在有限性程度方面也有差异。从计算机执行和实际应用而言，不仅要求算法结束于有限步数，而且还希望结束于很有限的步数，这就需要对其进行时空复杂性分析。
1.3.2算法的描述一个算法可用自然语言、数学语言、算法描述语言或程序设计语言等来描述。本书将使用算法描述语言ADL和C++程序设计语言对算法进行描述。下面给出著名欧几里得（Euclid）算法的ADL描述，以期具体展示一个算法及其书写规范。
例欧几里得算法算法E (m,n.n)E1. [求余数]r←m−⌊m/n⌋×n.//有0≤r<nE2. [余数为零？]IFr=0 THEN RETURNn.//若余数为0，n即为答案E3. [减少]m←n.n←r. GOTO E1.▐算法E运行的例子:44m>n?
r=m−q×nnm⌊m/n⌋×n=q×nm/n步骤5441191190119/544E1E2119544E368476544/119E1E268119E35168119/68E1E25168E3175168/51E1E21751E305151/17E1(119 , 544)=17E
462.算法描述语言——ADL①ADL的格式算法<算法名>(变量i1,…,变量im.变量j1,…,变量jn)//<算法的概括说明>或者<步骤名>.[<本步骤的概括说明>]<操作1>…<操作J><步骤名>.[<本步骤的概括说明>]…▐<算法名>是由字母和数字组成的有限字符串，且串中第一个符号必须是字母.在变量表中，变量ik为输入变量,1≤k≤m, m≥0;变量jk为输出变量，1≤k≤n，n≥1
2.算法描述语言——ADL①ADL的格式算法<算法名>(变量i1,…,变量im.变量j1,…,变量jn)//<算法的概括说明>或者<步骤名>.[<本步骤的概括说明>]<操作1>…<操作J><步骤名>.[<本步骤的概括说明>]语句序列.▐对整个算法进行概括说明，应包含算法的主要思想、参变量、功能和约束等的解释.47
2.算法描述语言——ADL①ADL的格式算法<算法名>(变量i1,…,变量im.变量j1,…,变量jn)//<算法的概括说明>或者<步骤名>.[<本步骤的概括说明>]<操作1>…<操作J><步骤名>.[<本步骤的概括说明>]语句序列.▐步骤号后紧接一对方括号，该方括号内是对该步骤所执行操作的高度概括.算法的每一步骤都要有名称,名称由<算法名或算法名缩写><数字><.>组成.48
492.算法描述语言——ADL①ADL的格式算法<算法名>(变量i1,…,变量im.变量j1,…,变量jn)//<算法的概括说明>或者<步骤名>.[<本步骤的概括说明>]<操作1>…<操作J><步骤名>.[<本步骤的概括说明>]语句序列.▐本步骤的一系列操作，每个操作由ADL语句给出，若某操作难于理解则需在其后对其做出解释.每个算法都需要用符号“▐”作为其被书写完毕的结束符，注意算法不一定在符号“▐”处运行结束.
②表达式算术运算符+,−,×,*,/,DIV,MOD,⌊⌋,⌈⌉,关系运算符=、≠、<、>、≥、≤逻辑运算符AND , OR , NOT逻辑常量true , false集合运算符∩,∪,−（差）,⊂,⊃③语句语句结束符.赋值语句a←b. a↔b. a←b←c.50
条件语句①IF <逻辑表达式>THEN (语句1. … .语句m).②IF <逻辑表达式>THEN (语句1. … .语句m).ELSE (语句1. … .语句n).③CASE DO( <逻辑表达式1>: (语句1. … .语句n1).…<逻辑表达式m>:语句1. … .语句nm)).51
循环语句①WHILE <逻辑表达式>DO (语句1. ….语句n ).②FOR<变量> = <算术表达式1> TO<算术表达式2> STEP <算术表达式3>DO (语句1. … .语句n ).③FOR<变量>∈<集合>DO(语句1. … .语句n ).52
转移语句GOTO (<步骤名>) .EXIT语句结束本层WHILE或者FOR循环的执行RETURN语句指出算法执行的终点输入语句：READ(x)
例算法SM(A ,n. max , min)SM1.[初始化]max←min←A[1].SM2.[比较]FOR I=2TO n DO//求最大和最小元素(IFA[I]>max THENmax←A[I].IFA[I]<min THENmin←A[I]) .▌54
ADL的特点书写简便–不必考虑过多程序设计语言的细节–例:交换a和b的值易于理解–便于不同编程习惯的人交流–不必考虑与算法无关的内容(运行环境、编译状态等)C++ADLint temp;int a;int b;temp=a;a=b;b=temp;a↔b
3.算法性能评估的5条准则正确性时间复杂性空间复杂性(指令、数据和环境栈空间)可读性鲁棒性（ROBUST）还应该具有灵活性、可重用性和自适应性等。
1)正确性说一个算法是正确的，如果对于一切合法的输入数据，该算法执行有限时间都能产生正确的结果。具体包括两方面：一是解决问题的方法；二是实现这一方法的一系列指令(步骤、语句)。证明相关的引理和定理，以确认一个算法所用方法的正确性；证明一系列语句确实做了符合规定的操作.57
2)时间复杂性算法的实际执行时间是不是时间复杂性的理想度量呢?不是。其原因是：算法的实际执行时间依赖于机器。同一个算法在不同机器上的执行时间不一定相同。算法的实际执行时间还依赖于编写算法的程序设计语言。一个用C或Pascal编写的算法可能要比用BASIC语言编写的算法快20倍。
度量算法时间复杂性的标准：能刻画算法所采用的方法的时间效率；与算法描述语言及设计风格无关；与算法的许多细节无关；足够精确和具有一般性。度量算法效率，应用能表达算法输入规模和执行时间关系的逻辑度量单位——所研究问题的基本运算。一个算法的时间复杂性;该算法所执行的基本运算的次数。
3)占用的存储空间包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。
4)可读性最简单、最直接的算法尽管不一定是最有效的，但却具有良好的可读性。可读性好的算法其正确性证明比较容易（即其正确性易于保证），同时便于设计、修改、阅读和调试，可见可读性是十分重要的。对于那些需经常使用的算法来说，高效率比可读性更为重要。
5)鲁棒性对有缺失、有噪声或有错误的输入数据，算法应具有较强的应付能力。如，能对输入数据语法、语义检验、提出修改错误的建议并提供重新输入的机会。6)好的算法还应该具有可移植、易用、安全、灵活和可重用等特性。
最优算法定义//以时间复杂性为评价标准最优算法定义：某算法A为最优，当且仅当被研究的解决同一领域同一问题的所有算法集合SA(A∈SA)中没有一个算法执行的基本运算次数比算法A更少。如何找到最优算法？给出下确界，用逼近的方法
第一章绪论1.1为什么要学习数据结构1.2数据结构的概念1.3算法1.4算法的正确性证明1.5算法分析基础
算法的正确性证明对于一个算法来说正确性是前提，也是非常重要的。对于明显是正确的算法（或程序），可以通过上机调试验证其正确性。调试用的数据要精心挑选，以保证算法对“所有的”数据都是正确的。
Testing (测试)Black Box Methods黑盒法侧重测试程序的功能，不考虑程序是如何实现的，即代码结构。设计测试用例，检查能否得到预想的结果。White Box Methods白盒法侧重测试程序的代码结构Statement Coverage语句覆盖:使程序中的每一条语句都至少执行一次。
Decision Coverage分支覆盖：使程序中的每一个分枝都至少执行一次。
算法正确性证明算法的正确性是非常重要的。对明显是正确的算法，可通过上机调试验证其正确性。调试用的数据要精心挑选，以保证算法尽可能对所有的数据都是正确的;只要找出一组数据使算法失败，就能否定算法的正确性;算法的正确性一般通过数学方法进行推理证明，常用的数学方法除了直接证明法外，还有反证法和数学归纳法。
1.反证法①要证明定理T是正确的，首先假定T是错误的②使用正确的命题和正确的推理规则进行推理，若出现下列条件之一，就会得出矛盾的结果：与已知条件矛盾与公理矛盾与证明过的定理矛盾自相矛盾③由此推出定理T是正确的。
2.数学归纳法数学上证明与自然数N有关的命题的一种特殊方法，它主要用来研究与正整数有关的数学问题。数学归纳法依靠假设的事实来证明定理，是用“有限”步骤解决“无限”问题的一种严格证明方法。
数学归纳法设T是一个定理，自然数n是T中参数.数学归纳法表明，如果下面两个条件为真，则对于参数n的任何值，T都是正确的：(1)基础归纳：n=c时，T成立。(2)归纳步骤：如果n = k−1时T成立，则n = k时T也成立。其中，c是一个较小的常量，n≥c.通常，证明初始归纳很容易，而证明归纳步骤很难。
强归纳法设T是一个定理，自然数n是T之参数.数学归纳法表明，如果下面两个条件为真，则对于参数n的任何值，T都是正确的：①基础归纳：n=c时，T成立。②归纳步骤：如果n=k−1时T成立，则n=k时T也成立②归纳步骤：若对于c≤k<n，T都成立，则T对于n也成立。
例:证明由递归关系式T(n)=T(n−1 )+1，T(1)=0，可推出T(n)=n−1，其中，n>1.证明：基础归纳：n=1时，T( 1)=1−1=0，结论成立。归纳步骤：假设T(n−1 )=n−2成立（归纳假设）往证T(n)=n−1成立。由递归关系式可知：n>1时，有T(n)=T(n−1 )+1再由归纳假设：T(n)=T(n−1 )+1=n−2+1=n−1由数学归纳法推出T(n)=n−1成立，证毕▐74
第一章绪论1.1为什么要学习数据结构1.2数据结构的概念1.3算法1.4算法的正确性证明1.5算法分析基础
1.算法时间复杂性的分析方法例算法SM(A , n.max , min)SM1[初始化]max←min←A[1].SM2[比较]FORi=2 TO n DO(IFA[i]>maxTHENmax←A[i].IFA[i]<minTHENmin←A[i]). ▐基本运算:元素的比较运算算法SM的时间复杂性为2(n−1).76
例算法F(R, n, K. i)F1[初始化]i←1.F2[比较]WHILEi≤nDO(IFR[i]=KTHEN RETURN.i←i+1) . ▐最少比较次数：1最大比较次数：n
上例中，假定q表示K是R中元素的概率，又假定K等于R的每个元素有相同的概率。令Dn={I1,I2,…,In,In+1}，其中Ij(1≤j≤n)表示K等于R[j]的任一输入In+1表示K不是R中元素的任一输入。当1≤j≤n时，P(Ij)=q/n,T(Ij)=j,P(In+1)=1−q,T(In+1)=n.算法F的期望复杂性为：79
E(n)=∑{P(I)*T(I)}=(q/n)×1+(q/n)×2+…+(q/n)×n+(1−q)×n=q(n+1)/2+(1−q)n如果已知K在R中，即q=1，则有E(n)=(n+1) /2该算法在最坏情况下的复杂性W(n)=max{T(i)|1≤i≤(n+1)}=n该算法在最好情况下的复杂性W(n)=mim{T(i)|1≤i≤(n+1)}=180
例算法SM的改进算法BS算法BS（A , i , j . fmax , fmin）BS1.[递归出口]IFi=jTHEN(fmax←fmin←A[i]. RETURN.)IFi=j−1THEN(IFA[i]<A[j] THEN(fmax←A[j]. fmin←A[i]).ELSE (fmax←A[i].fmin←A[j]). RETURN).BS2.[取中值]mid←⌊(i+j)/2⌋BS3.[递归调用]BS (A, i, mid.Gmax, gmin). BS (A, mid+1, j.hmax, hmin).BS4.[合并]fmax←max{gmax, hmax}.fmin←min{gmin, hmin}. ▐81
i=5mid=6j=8A[5] A[6] A[7] A[8]304025 16i=1mid=2j=4A[1] A[2] A[3] A[4]52012 7i=1mid= 4j=8A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]5 20 12 7 304025 16算法SM的改进82i=1 j=2A[1] A[2]520i=3 j=4A[3] A[4]127i=5 j=6A[5] A[6]3040i=7 j=8A[7] A[8]2516
BS(A , i=1, j=8 . fmax , fmin)BS1. BS2. mid←4 .BS3.BS(A , i=1 , j=4. gmax , gmin)BS1. BS2. mid←2 .BS3.BS(A , i=1 , j=2. gmax , gmin)BS1.gmax←20.gmin←5 . RETURN.BS(A , i=3 , j=4. hmax , hmin)BS1.hmax←12.hmin←7. RETURN.BS4.gmax←20 .gmin←5 .BS(A , i=5 , j=8. hmax , hmin)BS1. BS2. mid←6 .BS3.BS(A , i=5 , j=6. gmax , gmin)BS1.gmax←40.gmin←30. RETURN.BS(A , i=7 , j=8. hmax , hmin)BS1.hmax←25.hmin←16. RETURN.BS4.hmax←40 .hmin←16 .BS4.fmax←40.fmin←5.▌
i=1mid= 4j=8A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]5 20 12 7 304025 16i=5mid=6j=8A[5] A[6] A[7] A[8]304025 16i=1mid=2j=4A[1] A[2] A[3] A[4]52012 7算法SM的改进84i=1 j=2A[1] A[2]520i=3 j=4A[3] A[4]127i=5 j=6A[5] A[6]3040i=7 j=8A[7] A[8]2516①②③⑥④⑤⑦①②③④⑤⑥⑦
容易看出，BS对A[i]到A[j]的不同的输入都有相同的基本运算次数。设T(n)表示其基本运算次数，则根据算法BS的递归过程，有如下的递归表达式：85若n是2的幂(即存在正整数k ,使得n=2k)则有T(n)=2×T(n/2)+2=2×(2×T(n/4)+2)+2=4×T(n/4)+4+2=4×(2×T(n/8)+2)+4+2=8×T(n/8)+8+4+2=…=2k−1×T(2)+(21+22+…+2k−1)=(3n/2)−2
BS与SM的比较算法SM和BS的时间复杂性均为线性，但因3n/2−2<2(n−1)，故算法BS优于算法SM.算法BS是递归算法，因此它的实现需要额外的辅助空间栈。
确定算法基本运算次数的目的在于能比较功能相同的两个算法之间的时间复杂性；预测随实例特性的改变，运行时间的增减情况。在很多情况下，特别当输入规模n较大时，确定一个算法的基本运算次数T，得到T和n之间的函数关系非常困难。算法分析中通常采用大O、大和大来渐近表示算法的基本运算次数。2.复杂性函数的渐近表示
1892年，保罗巴赫曼(PaulBachmann)提出了大O表示法，主要用于估计函数的增长速率。定义设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是O(g(n))，当且仅当存在正的常数C和n0，使得对任意的n≥n0，有f(n)≤Cg(n).f和g之间关系的含义是“f(n)的阶至多为g(n)”或“f至多与g增长得一样快”.大O表示法
例f(n)=3n−2是O(n).证明：由大O的定义，存在C=3，n0=1，使得对任意的n≥n0，有3n−2≤3n即f(n)≤Cg(n) .例f(n)=3 logn+loglogn是O(logn)证明：由大O的定义，存在C=4，n0=2，使得对任意的n≥n0，有3logn+loglogn≤4 logn即f(n)≤Cg(n) .89
一个算法的时间复杂性为O(g(n))，表明它的基本运算次数至多是g(n)的某个常数倍。O(1)表示算法的时间复杂性为一常数。O(n)、O(n2)、O(n3)、O(nm)和O(2n)分别表示算法时间复杂性为线性阶的、平方阶的、立方阶的、多项式阶的和指数阶的，其中m≥1，且m为常数。
定理1.1若A(n)=amnm+…+a1n+a是关于n的m次多项式，则A(n)=O(nm)算法分成两类：多项式阶算法和指数阶算法。函数的阶取决于：多项式中，幂次最高的项，与其系数和其它较低幂次的项无关。
定义设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是(g(n)),当且仅当存在正的常数C和n0,使得对任意的n≥n0，有f(n)≥Cg(n).f(n)=(g(n))的含义是f(n)的阶至少为g(n)或f的增长速率不低于g.大表示法
例f(n)=3logn+loglogn证明f(n)=(logn)证明：由大之定义，存在C=3，n0=2，使得对任意的n≥n0，有3 logn+loglogn≥3logn即f(n)≥Cg(n) .由大的定义，f(n)=(logn)，证毕▌93
定义设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)是Θ(g(n))，当且仅当存在正的常数C1,C2和n0,使得对任意的n≥n0,有C1g(n)≤f(n)≤C2g(n) .f(n)=Θ(g(n))的含义是f(n)和g(n)的阶相同或f和g以相同的速率增长.大Θ表示法
例若f(n)=3logn+loglogn证明:f(n)=Θ(logn)证明：由上例可得3logn≤3 logn+loglogn≤4logn由大的定义，f(n)=Θ(logn)，证毕▌95
例如，一个算法执行时间为30秒，前10秒算法占用60个字节，第二个10秒算法占用70个字节，最后10秒算法占用80个字节。该算法的时空分布如图所示。807060302010YX效率图时空分布示意图显然算法的时空积分为：60×10+70×10+80×10=2100(字节秒)
基于时空积分，我们可以比较算法SM和BS的优劣，时空积分较小的算法是较优的算法。图算法SM与算法BS的时空积分比较图（b）算法BS的时空图(a)算法SM的时空图STX算法需要的空间算法需要的空间STXBLSM比BS多用的时间BS比SM多占用的空间
算法SM的计算时间为L，占用空间为S；算法BS的计算时间为T(T<L)，占用空间为B(B>S)。Y(a) SM的时空图STXLY(b) BS的时空图STXBL=L−TB=B−SWSM=(T+L)×S WBS=(S+B)×TWSM−WBS=L×S−B×TTa×(5n/3−2)La×(2×(n−1)−(5n/3−2))=a×n/3Sb×nBc×log2nWSM−WBSa×b×n2/3−c×log2n×a(5n/3−2)=O(n2)当n比较大时，WSM>WBS，算法BS优于算法SM.99
本章练习题1.简述下列术语：数据、结点、逻辑结构、存储结构、数据处理、数据结构。2.试根据以下信息：校友姓名、性别、出生年月、毕业时间、所学专业、现在工作单位、职称、职务、电话等，为校友录构造一种适当的数据结构(作图示意)，并定义必要的操作和用文字叙述相应的算法思想。3.什么是算法？算法的主要特点是什么？4.如何评价一个算法？
课后作业1.求下述计算f=1！+2！+3！+…+n！的算法的时间复杂性。voidfactorsum(intn){inti,j；intf,w；f=0；for(i=1;i<=n;i++){w=1；for(j=1;j<=i;j++)w=w*j;f=f+w;}return；}
课后作业2.23页1-5设计并分析算法3.23页1-11证明对正整数n≥3，算法BS的元素比较次数。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}