数据结构章绪论

数据结构与算法DataStructures

andAlgorithm黄虎杰

唐纳德·克努特（DonaldErvinKnuth）—1938年12月7日出生于美国威斯康星州密尔沃基市；—29岁提出“算法”(Algorithm)和“数据结构”(DataStructure)；—1973年首创双向链表；—著名算法Knuth-Bendix和Knuth-Morris-Pratt的发明者；—排版系统TEX和METAFONT发明人。1956年：进入俄亥俄州克利夫兰的凯斯理工学院（现并入凯斯西储大学）物理专业；1958年：改学数学，并从此与计算机结缘；1960年：Knuth被破例同时授予学士和硕士学位，进入加州理工学院数学系；1963年：取得博士学位,1966年副教授；1968年：斯坦福大学计算机科学系教授。开始撰写著名的《计算机程序设计艺术》系列图书；《计算机程序设计艺术》1968年第一卷《基本算法》出版；1969年第二卷《半数字化算法》出版；1973年第三卷《排序与搜索》出版；目前第四卷《组合算法》已出版。1971年：首届美国计算机协会格蕾丝·赫柏奖；1973年：当选为美国科学艺术学院院士；1974年：图灵奖历史上最年轻的获奖者；1975年：当选为美国国家科学院院士。《计算机程序设计艺术》一书与牛顿的《自然哲学的数学原理》等书一起，被评为“世界历史上最伟大的十种科学著作”之一。看了这部书后，再谈起编程序都会变得谦虚谨慎。比尔·盖茨曾说：“如果你能读懂整套书的话，请给我发一份你的简历”。教学安排：讲课学时40，

实验学时16考核要求：期末考试占70%实验成绩占20%平时作业占10%软件工程专业1-2班上课时间7-16周周二3-4节and周四3-4节上课地点正心816考试时间19周，时间地点待定本课程在整个培养方案中的作用2017年计算机专业数据结构与算法成绩2017年软件工程专业数据结构与算法成绩2018年计算机专业数据结构与算法成绩2018年软件工程专业数据结构与算法成绩《数据结构与算法》是计算机大类的专业基础课，既是对前序课程的深入和扩展，也是为将来更加深入地学习其他专业课程打下基础。通过本课程的学习，学生将基本掌握数据结构和算法基础知识，能够提高程序设计的质量；根据问题的性质，能够选择合理的数据结构，并对时间复杂性进行必要的控制，培养解决实际问题的能力。课程具体目标如下：课程目标1：能够根据算法的实际操作需求，选择、设计合理地

数据结构，并能实现相关算法；课程目标2：能够对算法进行时间（空间）复杂性的分析；课程目标3：能够通过具体案例，学习并掌握基本数据结构

（线性、树、图）的设计与使用；课程目标4：通过实验验收与实验报告的撰写，培养学生的书面

表达能力和口头表达能力。课程目标（2016版）教材数据结构与算法（第4版）编著廖明宏郭福顺张岩李秀坤高等教育出版社参考资料严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社.2011.EllisHorawitz,SartajSahni,SusanAnderson-Freed著,

李建中,张岩,李治军译.FundamentalsofDataStructuresinC.

机械工业出版社.2006.SartajSahni著,汪诗林,孙晓东.DataStructures,Algorithms,andApplicationsinC++.

机械工业出版社.2006.李秀坤,张岩,李治军,娄久.数据结构与算法实验教程.

高等教育出版社.2009.了解数据结构的基本概念、研究对象以及数据结构课程的发展历史，对数据结构与算法课程有一个宏观的认识；掌握贯穿全书的重要概念--抽象数据型，包括其概念的定义和实现方法，初步掌握抽象技术方法；了解算法、算法复杂性，掌握算法性能的评价方法；了解解决问题的一般过程和算法的逐步求精方法，掌握问题求解的基本过程和方法。教学要求本章主要内容1.1数据结构研究对象1.2数据结构发展概况1.3抽象数据型(ADT)1.4数据结构与程序设计1.5算法描述与算法分析1.1数据结构研究对象◆计算机科学：信息在计算机内使用数据来表示,

研究信息表示和信息处理。◆数据：是用以描述客观事物的数值、字符，以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合；数据的基本单位称为数据元素；数据的最小单位称为数据项。◆数据对象：性质相同数据元素的集合◆数据特征：数值、文本、多媒体、超媒体、实时、海量◆数据类型?高级语言中变量的取值范围和允许的操作

什么是数据？大数据(bigdata)大数据可分成：大数据技术：解决大数据问题的技术和方法；大数据工程：大数据的规划建设运营管理的系统工程；大数据科学：关注大数据网络发展和运营过程中发现和验证大数据的

规律及其与自然和社会活动之间的关系；大数据应用：解决实际问题。大数据的4个“V”：—Volume：数据体量巨大。从TB级别，跃升到PB级别；—Variety：数据类型繁多。网络日志、视频、图片、地理位置信息等—Value：价值密度低。以视频为例，连续不间断监控过程中，可能有

用的数据仅仅有一两秒。—Velocity：处理速度快，1秒定律。即要在秒级时间范围内给出

分析结果,超出这个时间,数据就失去价值了。◆数据结构：数据元素彼此之间抽象的相互关系，解决数据的存储和组织的方式，不涉及数据元素的具体内容。描述现实世界事物的数学模型及其操作在计算机中的表示和实现◆数据结构分类：线性表：(a1,a2,a3,……ai-1,ai,ai+1……an-1,an)→线性结构线性表的一般概念、字符串、数组，广义表等树：

层次结构二叉树，树等图：

网状结构有向图、无向图等①②③⑤

二叉树①②③④有向图◆结构：关系，组成整体的各部分的搭配和安排非线性结构O××OO×××O×O××O×O××OO×××OO××O×

国际象棋：每次需要考虑的合乎规则的着法平均只有35

步“回合”，计算机预先分析7至8个回合的着

法。若设为7个回合，则有超过1亿亿亿个不

同的变化，经简化后，仍有500亿至600亿个

变化。多分析一步，增加18亿个变化。资料：下棋程序围棋：分析7个回合的着法，则需要考虑超过200的

14次方个变化，经简化后，仍有1000亿亿个

变化。多分析一步，增加64万亿个变化。根据计算机“深蓝”的速度，平均5分钟走一步！根据计算机“深蓝”的速度，平均1.5年走一步！BlueGene,共装有32个并行处理器，速度：2亿步棋/秒深蓝vs

卡斯帕罗夫:第一次1996年：2月10日—17日，比分2:4，卡斯帕罗夫赢第二次1997年：5月3日—11日，比分3.5:2.5双方先后共进行6局对弈：第一局：卡斯帕罗夫执白先行，经过3个多小时的苦战击败

深蓝力拔头筹；第二局：深蓝却以凌厉的攻势和明显的优势战胜卡氏，扳回

一局；第三、第四和第五局：双方下得异常激烈，鏖战数小时，

平局；第六局：深蓝执白先行，一路强攻，仅用一个多小时，双方

仅走了19步，就让卡氏俯首称臣，取得了决定性的

胜利。IBM“深蓝”--棋王卡斯帕罗夫卡斯帕罗夫深蓝身高5英尺10英寸6英尺5英寸体重176磅1.27吨年龄34岁4岁行棋速度2步/每秒2亿步/每秒-1980年，台湾大学电机系毕业;-获得了电子工程学士学位;-美国卡内基·梅隆大学博士;-曾在IBM工作;-现在微软亚洲研究院。卡斯帕罗夫:他在观察电脑下棋时感觉电脑的决定有智慧及创意，是他所不能理解的。他亦认为电脑在棋局中可能有人类的帮助，因此要求重赛。IBM:拒绝，并把深蓝退役。2003年纪录片“游戏结束：卡斯巴罗夫与电脑”(GameOver:KasparovandtheMachine)。许峰雄深蓝-1996年，美国IBM公司；-基于RS/6000

SP设计；-AIX操作系统；-重1270公斤，32个微处理器；-每秒钟可以计算2亿步。“神来之着”阿尔法围棋（AlphaGo）是一款围棋人工智能程序，由英国伦敦的谷歌（Google）旗下DeepMind公司的戴维·西尔弗、艾佳·黄和戴密斯·哈萨比斯与他们的团队开发，这个程序利用“价值网络”计算局面，用“策略网络”选择下子。2015年10月阿尔法围棋以5:0完胜欧洲围棋冠军、职业二段选手樊麾；2016年3月对战世界围棋冠军、职业九段选手李世石，并以4:1的总比分获胜。

面对AlphaGo碾压式的实力，19岁的“大魔王”柯杰：“AlphaGo实在下得太好。我担心的每一步棋他都会下，还下出我想不到的棋，我仔细慢慢思索，发现原来又是一步好棋。我只能猜出AlphaGo一半的棋，另一半我猜不到，就是差距，我和他差距实在太大。”2017年5月23、25、27日

AlphaGo设计者：戴维·西尔弗（DavidSilver），剑桥大学计算机科学学士，硕士，加拿大阿尔伯塔大学计算机科学博士。现为伦敦大学学院讲师及GoogleDeepMind研究员。艾佳·黄（黄士杰，AjaHuang），台湾交通大学计算机科学学士，台湾师范大学计算机科学硕士和博士，加拿大阿尔伯塔大学计算机科学博士后。现为GoogleDeepMind研究员。AlphaGo使用1820多块CPU及280多块GPU（GraphicProcessingUnit），据说，这次围棋对战分析只用了服务器总的百分之三十资源，其余的在空闲。谷歌AlphaGo计算能力超IBM深蓝2.5--3万倍！经过短短3天的自我训练，AlphaGoZero就强势打败了此前战胜李世石的旧版AlphaGo，战绩是100:0的。经过40天的自我训练，AlphaGoZero又打败了AlphaGoMaster版本。“Master”曾击败过世界顶尖的围棋选手，甚至包括世界排名第一的柯洁。Master补充1：适用于并行计算——并发数据结构或多线程数据结构设计并发数据结构（互斥锁）设计不使用互斥锁的并发数据结构以队列为例：并发队列并发阻塞队列有超时限制的并发阻塞队列有大小限制的并发阻塞队列有操作限制的并发阻塞队列如何设计支持并发访问的数据结构？设计可以基于互斥锁，也可以是无锁的。无论哪种方式，要考虑的问题不仅仅是这些数据结构的基本功能—具体来说，必须一直记住线程会争夺执行权，要考虑线程重新执行时如何恢复操作。试图从没有数据的队列读取数据，仅仅会抛出异常并继续执行。但是，这种做法不总是我们想要的，读线程很可能希望等待，直到有数据时为止。这种队列称为阻塞的队列。补充2：适用于分布式系统——分布式Hash表或者分布式B+树Hash算法：模N（N为机器数）Hash或者一致性Hash模N哈希的主要问题：机器上下线时机器数变化导致所有的数据都需要重新分布，一致性Hash用来解决这个问题。分布式Hash存储系统由于只支持随机读取，一般用选择相对较好的磁盘，分布式B+树存储系统同时支持随机读取和顺序扫描，当用来支持使用模式主要为顺序扫描的应用时，可以选择相对较差的磁盘，比如SATA盘。Hash空间组织成一个环，环上相邻节点包含的数据构成一个桶；比如Hash空间为A,B,C，那么有[A,B],[B,C],以及[C,A]三个桶；每个桶内的数据结构为Log-StructuredHashTable；当然，可根据需要修改每个桶的单机数据结构；桶是负载均衡和任务调度的基本单元；每个桶存放3个副本。1.1数据结构研究对象1、数据结构研究方法逻辑结构：对操作对象的一种数学描述，或从操作对象中抽象出的数学模型，用以描述数据元素之间的逻辑关系，与存储方式无关。物理结构：数据结构在计算机中的表示或映象，逻辑结构

的存储方式。又称存储结构，分为顺序映象和非顺序映象；

或称顺序存储结构和链式存储结构；计算机解题过程：问题→数学模型→算法→程序→测试→计算分析数据并确定存储结构输入到计算机中2、数据结构研究的范畴程序设计：为计算机处理问题编制一组指令集算法：怎么处理的策略数据结构：问题的数学模型程序设计、算法、数据结构数值计算的程序设计问题：问题算法数学模型求解一元二次方程？求根公式一组整数排序“冒泡”方法数组结构静力分析计算？线性代数方程组全球天气预报？环流模式方程非数值计算的程序设计问题：问题算法数学模型求一组整数的最大值比较两个数的大小？计算机对弈对弈的规则和策略棋子、棋盘的表示足协的数据库管理什么项目？如何管理？接口？条例？规则？表格，数据库1.2数据结构发展概况数据结构侧重解决非数值问题FORTRAN,ALGOL等高级语言是以程序为中心侧重于解决数值问题；LISP,SONBOL表或串处理语言是以数据为中心侧重于解决非数值问题；1968年以前，数据结构的内容大多包含在形如表、树、图论、集合代数论、格、关系等方面。1968年开始，“数据结构”逐渐开始成为独立的一门课程；

作为一门专业基础课，“数据结构”是计算机专业的核心课程之一，是其他专业课的基础。是数学、硬件和软件三者的交叉，很受重视。从PASCAL语言开始逐渐形成二者结合；知识结构《数据结构》所处的地位1.3抽象数据型AbstractDataTypes（ADT）＊软件系统由数据结构、操作过程和控制机能三者组成，软件设计是对三者的抽象过程，即数据抽象、过程抽象和控制抽象。【定义】抽象数据型是一个数学模型和在该模型上定义的操作的集合。ADT特点：①降低了软件设计的复杂性；②提高了程序的可读性和可维护性；③程序的正确性容易保证。抽象：从众多事物中舍弃个别的、非本质的属性，抽出共同的、本质性的特征。是形成概念的重要手段，其目的是使复杂度降低。线性表LIST=(D,R)D={ai|ai

∈ElementSet,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：设L的型为LIST线性表实例，x的型为ElementType的元素实例，p为位置变量。所有操作描述为：①Insert(x,p,L)；②Locate(x,L)；③Retrieve(p,L)；④Delete(p,L)；⑤Previous(p,L),Next(p,L)；⑥MakeNull(L)；⑦First(L)；数学模型【例1-1】定义任意线性表类型为LIST，其中元素类型为Elementtype，设有线性表L，函数Purge用以删除线性表L中所有重复出现的元素。VoidPurge(LISTL){Positionp,q;p=First(L);while(p!=End(L)){q=Next(p,L);while(q!=End(L))if(same(Retrieve(p,L),Retrieve(q,L)))

Delete(q,L);elseq=Next(q,L);p=Next(p,L);}}【例1-2】假设利用两个线性表LA和LB分别表示两个集合，设计算法求一个新的集合A=A∪B。VoidUnion(LIST&A；LISTB){Positionp;ElementTypee;p=First(B);while(p!=End(B){e=Retrieve(p,B);if(same(Locate(e,A),End(A)))

Insert(e,End(A),A);p=Next(p,B);}}抽象数据型的规格描述△完整性：反映所定义的抽象数据型的全部特征；△统一性：前后协调，不自相矛盾；△通用性：适用于尽量广泛的对象；△不依赖性：不依赖于程序设计语言，可以用任意的语言来描述；规格描述的两个方面:语法和语义△语法：给出操作的名称、I/O参数的数目和类型；△语义：由一组等式组成，定义各种操作的功能及相互间的关系；例如：抽象数据型——栈(Stack)【定义】栈是一个后进先出（LIFO）的线性表，所有插入、删除操作是在表的一端（栈顶）进行。聚集数组，链表(结构体、记录)，文件栈(Stack)示意图typeStack[ElementType];NewStack()→Stack；Push(ElementType,Stack)→Stack；Pop(Stack)→Stack∪{UNDEFINED}；Top(Stack)→ElementType∪{UNDEFINED}；Empty(Stack)→Boolean;抽象数据型—栈语法：declarestk:Stack,elm:ElementType;Pop(NewStack)=NewStack；Pop(Push(elm,stk))=stk；Top(NewStack)=UNDEFINED；Top(Push(elm,stk))=elm；Empty(NewStack)=TRUE；Empty(Push(elm,stk))=FALSE;抽象数据型—栈语义：

规格描述给出操作的名称,I/O参数的数目和类型定义各种操作的功能及相互间的关系抽象数据型的实现抽象描述：（高级语言）编写的程序三条原则：①符合规格描述的定义；②有尽可能好的通用性；③尽可能独立于程序的其他部分。多层次抽象技术自底向上与自顶向下相结合、由简单到复杂1.4数据结构与程序设计Algorithms+DataStructures=Programs算法+数据结构=程序设计《系统程序设计导论》（《SystematicProgramming：AnIntroduction》，Prentice-Hall，1973；《算法+数据结构=程序》（《Algorithms+DataStructures=Programs》，Prentice-Hall，1976）；《算法和数据结构》（《AlgorithmsandDataStructures》，Prentice-Hall，1986）；《Modula-2程序设计》（《ProgramminginModula-2》，Springer，1988，第4版）。《PASCAL用户手册和报告：ISOPASCAL标准》（《PASCALUserManualandReport：ISOPASCALStandard》，Springer，1991）；《Oberon计划：操作系统和编译器的设计》（《ProjectOberon：theDesignofanOperatingSystemandCompiler》，ACMPr.，1992）；《Oberon程序设计：超越Pascal和Modula》（《ProgramminginOberon：StepsbeyondPascalandModula》，ACMPr.，1922）；《数字电路设计教材》（《DigitalCircuitDesignforComputerScienceStudents：AnIntroductoryTextbook》，Springer，1995）。尼古拉斯·沃斯（NiklausWirth，1934年2月15日）；生于瑞士温特图尔，瑞士计算机科学家；苏黎世工学院获得学士学位，美国加州大学伯克利分校获得博士学位；代表性著作有：获奖：1984年：获图灵奖（ACM）；1987年：获计算机科学教育杰出贡献奖（ACM）；1983年：EmanualPiore奖（IEEE）；1988年：计算机先驱奖（IEEE）；1992年：加州大学伯克利分校命名沃斯为“杰出校友”。1984问题解决问题的算法实现算法的程序问题总是先于算法程序设计的四个里程碑：

①子程序、②高级语言、③结构程序设计、④面向对象(OOP)结构化程序设计：

①限制使用GOTO语句（基于三种基本结构）；

②逐步求精的设计方法；

③自顶向下的设计、编码与调试；

④主程序员组的组织形式；问题环境数据结构程序结构读和写

程序要完成的任务可执行的操作程序结构基于数据结构的根源1.4数据结构与程序设计“我们对复杂性问题的最重要的办法是抽象，对一个复杂问题，不应马上用计算机指令、数字与逻辑字来表示，而应该用较为自然的抽象语句来表示，从而得出抽象程序。抽象程序对抽象的数据进行某些特定的运算并用某些合适的记号(可能是自然语言)来表示。基于数据结构的jackson设计方法：①研究问题环境，确定要处理的数据结构；②基于数据结构，形成程序结构（骨架）；③用初等操作来定义要完成的任务，并分配初等操作。“从上到下，逐步求精”对抽象程序作进一步的分解，并进入下一层的抽象，这样的精细化过程一直进行下去，直到程序能被计算机接受为止。此时的程序可能是某种高级语言或机器指令书写的。”——N.wirth算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则；通俗点说,就是计算机解题的过程；在这个过程中，无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。1.5算法描述与算法分析早期的语言学家：algiros(费力的)+arithmos(数字)组合派生而成，但另一些人认为这个词是从“喀斯迪尔国王Algor”派生而来的；数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的PersianTextbook(《波斯教科书》)的作者的名字AbuJa‘farMohammedibnMûsâal-Khowârizm（约公元前825年）意思是“Ja’far的父亲，Mohammed和Mûsâ的儿子，Khowârizm的本地人”。Khowârizm是前苏联XИBA(基发)的小城镇。Al-Khowârizm写了著名的书Kitabaljabrw‘al-muqabala(《复原和化简的规则》)；另一个词，“algebra”(代数)，是从他的书的标题引出来的；牛津英语字典:这个词是由于同arithmetic(算术)相混淆而形成的错拼词。由algorism又变成algorithm；德文数学词典VollstandigesMathematischesLexicon(《数学大全辞典》)，给出了Algorithmus(算法)一词的如下定义：“在这个名称之下，组合了四种类型的算术计算的概念，即加法、乘法、减法、除法”。拉顶短语algorithmusinfinitesimalis(无限小方法)，在当时就用来表示Leibnitz(莱布尼兹)所发明的以无限小量进行计算的微积分方法；1950年左右，algorithm一词经常地同欧几里德算法(Euclid'salgorithm)联系在一起。这个算法就是在欧几里德的《几何原本》中所阐述的求两个数的最大公约数的过程(即辗转相除法)。资料：Algorithm与Logarithm经过月数兔子对数001121324355687138219341055118912144(1175-1250）意大利数学家从Fibonacci数列开始……,神奇的数列！斐波那契在《算盘书》中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，1对兔子每个月能生出1对小兔子来。如果所有兔都不死，那么1年以后可以繁殖多少对兔子？我们不妨拿新出生的1对小兔子分析一下：第1个月小兔子没有繁殖能力，所以还是1对；2个月后，生下1对小兔总数共有2对；3个月以后，老兔子又生下1对，因为小兔子还没有繁殖能力，所以一共是3对；…….

12个月以后呢？Fibonacci:0,1,1,2,3,5,8,13,21,34,55,89,……….0如果n=01如果n=1Fn-1+Fn-2

如果n>1Fibonacci数列的生成规则：Fn=Fn≈20.694n,Fibonacci数增长的速度几乎与2的幂增长的速度相当!F30超过了100万，F100已经达到21位数字！F200是多少？谁能告诉Fibonacci?Longintfib1(intn){if(n==0)return(0);if(n==1)return(1);return(fib1(n-1)+fib(n-2);}fib1(200)执行的基本操作次数:T(200)=T(199)+T(198)+3>=2138以每秒33.86千万亿次的计算机测算Fib1(200)的计算时间>=282秒另外一个计算方法：longintfib2(intn){longintF[200],i;if(n==0)return(0);F[0]=0；F[1]=1;for(i=2;i<=200;i++)F[i]=F[i-1]+F[i-2];return(F[200]);}Fib2(n)执行的基本操作次数T(n)是关于n的线性函数!T(n)=O(f(n))=O(n)

这仅是以加法为基本操作，你发现新的问题了吗？计算F200的时间>1.11*256年Fn≈20.694n≈(1.6)n,计算Fn+1的时间是计算Fn的1.6倍，Fn+1=1.6Fn摩尔定律(Moore’slow)：计算机的运算速度每年增长约1.6倍。“神威·太湖之光”击败的是霸占榜首3年的“天河2号”。“神威·太湖之光”运算速度达到93petaflop（每秒运算一千万亿次），理论最高速达125.4petaflops。这一数值约为“天河2号”的两倍。2016年6月20日德国法兰克福国际超级计算机大会（ISC）公布了新一期世界计算机500强榜单，我国最新的超级计算机“神威·太湖之光”登顶。最受关注的是，“神威·太湖之光”实现了核心处理器的全国产化。超算2018新一期全球超级计算机500强榜单2018年6月25日发布，美国超级计算机“顶点”超过中国的“神威·太湖之光”名列第一，这是美国超级计算机多年后重回榜首。美国能源部下属橡树岭国家实验室的超算“顶点”，浮点运算速度为每秒12.23亿亿次，峰值接近每秒18.77亿亿次。排名第二的是曾4次蝉联冠军的中国超算“神威·太湖之光”，其浮点运算速度没有变化，仍维持在每秒9.3亿亿次。随后排在第三至五位的超算依次是美国能源部下属劳伦斯利弗莫尔国家实验室的“山脊”、中国超算“天河二号”、日本超算“人工智能桥接云基础设施”（ABCI）。

5月在天津举办的第二届世界智能大会上，中国国家超算天津中心对外展示了我国新一代百亿亿次超级计算机“天河三号”原型机，有望在2020年研制成功并重回超算榜首。递归技术：最常用的算法设计思想，体现于许多优秀算法之中；分治法：分而制之的算法思想，体现了一分为二的哲学思想；模拟法：用计算机模拟实际场景，经常用于与概率有关的问题；贪心算法：采用贪心策略的算法设计；状态空间搜索法：被称为“万能算法”的算法设计策略；随机算法：利用随机选择自适应地决定优先搜索的方向；动态规划：常用的最优化问题解决方法。常见的计算机算法：“好”的算法的标准：①正确性，算法能满足具体问题的需求；②可读性，首先方便阅读与交流，其次才是机器执行；③健壮性，输入错误时，能作出反应，避免异常出错；④效率与低存储量要求。算法的特征：

①有穷性、②确定性、③输入、④输出、⑤能行性算法效率衡量和准则：①事后统计法

必须执行程序，

可能有其他因素掩盖算法的本质；②事前分析估算法对算法“正确性”的要求：

①不含语法错误；

②对于几组输入数据能得到满足要求的结果；

③对精心选择苛刻并带有刁难的数据能得到满足要求的结果；

④对于一切合法的输入均得到满足要求的结果；算法描述：

①自然语言；②程序设计语言；③类语言*；关于本书采用的类语言描述：

①结构类型说明；

②输入输出约定(cin>>v,cout<<v)；

③new和delete；

④引入引用类型；

⑤其他；影响算法执行的因素：

①算法实现后所消耗的时间**；②算法实现后所占存储空间的大小*；③算法是否易读、易移植等等其它问题。影响时间特性的五个因素：①算法选用的策略；

②程序运行时输入数据的总量，即问题的规模；③对源程序编译所需的时间，产生机器代码的质量；④计算机执行每条指令所需的时间/速度；⑤程序中指令重复执行的次数*。【定义】语句频度：语句重复执行的次数。程序运行时间渐近时间复杂度（时间复杂度）T（n）

算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作：

T（n）=O（f（n））它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。渐近空间复杂度（空间复杂度）S（n）S（n）=O（g（n））运算法则：设：T1(n)=O(f(n))，T2(n)=O(g(n))

加法规则：T1(n)+T2(n)=O(max{f(n),g(n)})

乘法规则：T1(n)·T2(n)=O(f(n)·g(n))程序运行时间比较T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△T(n)设：T(x)：取变量或常量x之值所消耗时间T(.V)：取变量V之地址所消耗的时间T(=)：赋值所消耗时间T(θ)：执行基本运算θ所耗时间T(call/return)：执行函数调用和返回所耗时间T(par)：将参数par传给函数所消耗时间～(1)表达式和赋值语句

exp::=常数|变量|F-name(e1,e2,…,em)|(expθexp)T(v=exp)=T(.v)+T(=)+T(exp)T(expθ

exp)=T(exp)+T(θ)+T(exp)

T(F-name(e1,e2,…,em))=T(call/return)+mT(par)+T(F-body)

例：

T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b)

相应的汇编程序为：

loadainR1loadbinR2addR2toR1loadcinR2storeR1inR2～～通常取O(1)(2)语句序列

T(s1,s2,…,sk)=max{T(s1),T(s2),…,T(sk))(3)条件语句

T(if(B)s1elses2)=T(B)+T(else)+max{T(s1),T(s2)}

通常取T(B)+T(else)=O(1)T(if(B)s)=O(1)+T(s)(4)Switch语句设语句sswitch(E){caseE1:S1;…caseEk:Sk;default:Sm}T(s)=T(E)+∑T(Ei)+max{T(s1),…,T(sk),T(sm)}

O(1)ki=1(5)for语句

T(for(i=1;i<=n;i++)s)=∑(T(s)+T(i=1)+T(i<=n)+T(i++)+T(for))O(1)(6)while语句

while(B)si=0;while(B){s;i++}

设RT0表示某一次循环开始执行时的绝对时间关于循环的定时不变式RT为

RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j))

其中：T(while)代表测试循环终止条件所耗时间

T(j)代表跳回循环头所耗时间可简化成：T(j)=T(while)T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while)(7)函数调用非递归调用：∑被调用子函数运行时间递归调用：求解递归方程(8)goto语句

goto语句破坏了程序结构一般对goto语句限制使用对有条件的goto转移可忽略不计【例1-3】

①s=0;→f(n)=1;T1(n)=O(f(n))=O(1)常量阶

②for(i=1;i<=n;++i){++x;s+=x;}→f(n