计算机软件及应用chapter是

TeachingMaterialTextBookDataStructureAndAlgorithmsInC++——secondedition.Adam.DrozdekReferenceBook王红梅.数据结构（C＋＋版）.清华大学出版社MarkAllenWeiss.DataStructures&algorithmanalysisinC++(secondedition)严蔚敏.数据结构.清华大学出版社.1997StudyHighlightTimeComplexity(算法与时间复杂度)

kəm'pleksiti]LinearList(线性表)StackandQueue(栈和队列）GeneralList(广义线性表)TreeandBinaryTree(树与二叉树)Graph(图)Searching(查找)Sorting(排序)算法与数据结构是计算机科学的两大支柱计算机科学早期定义为：研究算法的科学

近期定义为：研究数据的科学数据结构是程序设计的基础是计算机科学中一门综合性专业课程尼克劳斯．沃思（NiklausWirth）:瑞士计算机科学家。PASCAL之父，结构化程序设计的首创者，获得1984年图灵奖。Program=DataStructure

+Algorithm使用最适当的【数据结构】，才能够设计出最有效率的【算法】，进而转换成为有效率的【程序】。qualto这句话从此就成了计算机学科的一句名言，数据结构是一门和程序设计密切相关的课程DataStructureMainlyContent87352545电子商务学院电话号码130012长春工程学院邮编510103780618748身份证号码例1：87352545130012510103780618748结论1. 杂乱的数据不能表达和交流信息例2: 电话号码簿(a1，b1)(a2，b2)…(an，bn)其中：ai为某人姓名，bi为该人的电话号码。要求：设计一个算法，给定一个姓名时，能查出此人的电话号码。如果姓名和电话号码的排列次序无规律，则只能逐一比较姓名进行查找如果姓名按字典顺序组织，则查找就快捷多了结论2. 数据之间是有联系的这些联系常常影响算法的选择和效率。《DS》就是要研究数据之间的联系。DataStructureMainlyContent例3：大学学生管理机构长春工程学院 土木．．电信．．．

09级10级11级…

本科

专科张三李四结论３． 数据之间是有结构的例３中数据之间呈分层结构（Tree）《DS》就是要研究数据之间的各类结构。DataStructureMainlyContent例４：图书目录管理设每个书目含：书名，作者，登录号，分类，出版年月对图书目录常有如下操作：查找：某书在书库中是否存在？插入：购进新书时的登录；删除：报废或丢失的书，需从目录中去掉；结论４． 在某种数据结构上可定义一组运算《DS》要研究各类数据结构上的各种运算。DataStructureMainlyContent综上所述：《DS》主要研究内容：数据的各种逻辑结构和物理结构，以及它们之间的相应关系；对每种结构定义相适应的各种运算；设计出相应的算法；分析算法的效率。

常见的数据结构有：表(linearlist)、数组(array)、串(string)、栈(stack)、队列(queue)、树(tree)、图(graph)等。方法：查找（search）、排序(sort)StudyPurposeaboutDataStructure数据结构课程的三级标准1.掌握各类基本数据结构类型和相应的存储结构2.提高阅读和编写算法的能力3.能针对给定问题，选择相适应的数据结构，并能设计和分析算法C++语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比本课程在计算机专业课程中所处的地位课程性质数据结构是计算机专业的专业基础课

公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心专业基础课、承上启下

前导课：高等数学、离散数学、程序设计语言后续课：数据库、操作系统、编译原理……属于武术中的“练功”科目

“练武不练功，到头一场空”考研需要大家课后自己复习的内容：

第0章预备知识学习目标掌握基本的数据结构

工具箱→复用、修改、重组培养算法设计能力、程序设计能力

算法——程序的灵魂问题求解过程：问题→想法→算法→程序培养算法分析能力

评价算法、改进算法学习要求循序渐进，切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学→读书正确对待考试作习题

华罗庚：“学数学不做习题等于入宝山而空返”

作实验

计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。

成绩组成平时成绩

10％：出勤＋作业实验成绩

20％：出勤＋程序＋报告期末考试成绩

70％Chapter1:IntroductionHistoryofDataStructureResearchobjectsBasicconceptsAlgorithmandalgorithmanalysisbasiccontent：1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：TheArtofComputerProgramming他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。数据结构的创始人——克努思1.1History程序设计的实质是什么?datapresentation：将数据存储在计算机中dataprocessing：处理数据，求解问题数据结构问题起源于程序设计

实例：学生成绩管理系统数据结构随着程序设计的发展而发展计算机学科的飞速发展是其他任何学科所无法比拟的。Nostructurestage:20世纪40~60年代,计算机主要用于科学计算.ApplicationField：科学计算；Processeddata：数值型数据Therelationshipamongdata：数学方程或数学模型1.1History2.Structuredstage：数据结构＋算法＝程序ApplicationFields：科学计算与非数值处理；Processeddata：数值型数据和非数值型数据Therelationshipamongdata：产生了数据结构，提出了程序结构模块化，开始注意数据表示和操作的结构化。drawback：以数据为中心，不易应对变化1.1History3.Object-orientedstage：(数据结构＋算法)=程序ApplicationFields：更多地应用于非数值处理；Processeddata：更多地处理非数值型数据Therelationshipamongdata：数据结构发展到面向对象阶段类和数据结构之间的对应关系：1.1History类属性方法数据结构数据之间的关系基本操作对应数据结构的发展并未终结1.2ResearchObjectsofDSstepsforsolvingproblemswithcomputer:Aproblem→Abstractaproblemmodel→FindoutthesolutionofthismodelProblem——Numericalproblemandnon-numericalproblem

Numericalproblem→MathematicalEquation

non-numericalproblem→DSKnown

lengthandwideofaswimmingpool,thenfindoutareaofthepool.

◆

Buildamodel问题涉及的对象：游泳池的长len、宽wide和面积area对象之间的关系Therelationshipamongobjects：area=len

wide◆设计求解问题的方法Designthemethodofsolvingtheproblem◆编程programming[nəun]['εəriə]example一、NumericalProblemsandnon-numericalproblem

NumericalproblemKnown

lengthandwideofaswimmingpool,thenfindoutareaofthepool.◆

Buildamodel问题涉及的对象：length,wideandarea.对象之间的关系:area=len

wide◆Designthemethodofsolvingtheproblem◆programmingexample一、NumericalProblemsandnon-numericalproblem

Numericalproblem#include<iostream.h>voidmain(){intlen,wide,area;cin>>len>>wide;area=len*wide;cout<<"area="<<area<<endl;}1.1数据结构讨论的范畴2）non-numericalproblem

playchess……..……..…...…...…...…...◆Buildmodel

问题涉及的对象：theobjectofprobleminvolved:对弈过程中可能出现的棋盘格局；Checkerboardpatternthatmayoccurinthechessprocesscheckerboardpatterns树即是一种数据结构1.1数据结构讨论的范畴◆Buildmodel

问题涉及的对象:对弈过程中可能出现的棋盘格局；棋盘格局之间的关系：由比赛规则决定。对弈的过程就是从树根沿树杈到某个叶子的过程。

Theprocessofchessisfromtheroottoaleafalongthecrotch.

1.1数据结构讨论的范畴棋盘格局之间的关系：Therelationshipamongthecheckerboardpatterns由比赛规则决定。Determinedbytherulesofthegame对弈的过程就是从树根沿树杈到某个叶子的过程。

Theprocessofchessisfromtheroottoaleafalongthecrotch.2）非数值问题酒店管理系统的客房分配问题Roomsallocatedforhotelmanagementsystem◆建模型：buildmodel

问题涉及的对象theobjectofprobleminvolved:：房间；room

房间之间的关系：Therelationshipbetweentherooms线性关系，一对一的关系

每个房间之间的磨损应该是相同的frontrear

a1a2a3an入队列出队列线性结构1.1数据结构讨论的范畴2）非数值问题Roomsallocatedforahotel'æləukeit]◆buildamodel：

问题涉及的对象：room

对象之间的关系：Therelationshipbetweentherooms线性关系，一对一的关系

每个房间之间的磨损应该是相同的frontrear

a1a2a3an入队列出队列Linearlist1.1数据结构讨论的范畴非数值问题terminalexaminations已知研究生选课情况，安排课程考试的日程,要求在尽可能短的时间内完成考试。研究生选课情况表姓名选修课1 选修课2选修课3杨润生算法分析A形式语言B计算机网络E石磊计算机图形学C模式识别D魏庆涛计算机图形学C计算机网络E人工智能F马耀先模式识别D人工智能F算法分析A齐砚生形式语言B人工智能F1.1数据结构讨论的范畴◆建立模型：

问题涉及的对象：

electivecourse

课程之间的关系：同一研究生选修的课程之间有“冲突”关系。(同一个研究生选修的课程不能安排在同一时间内考试)conflictCDEABF顶点：表示课程

同一研究生选修的课程用边连接有边连接的课程不能安排在同一时间考试1.1数据结构讨论的范畴

每一种颜色代表一个考试时间，着上相同颜色的顶点是可以安排在同一时间考试的课程；

用尽可能少的颜色为图的顶点着色，使相邻的顶点着上不同的颜色；DBAEFCFBEACD课程考试可用图的着色法求解问题第一天thefirstday算法分析(A)计算机图形学(C)第二天thesecondday形式语言(B)模式识别（D)第三天计算机网络(E)第四天人工智能(F)◆设计求解问题的方法

求解考试日程的流程

设G表示课程关系图，

V是图G中所有尚未着色的顶点集合。

NEW表示可以用新颜色着色的顶点集合。⑴i=1；V={图中所有顶点的集合}⑵若V非空DO

①置NEW为空集合；②在V中找出所有“不相邻”的顶点，将这些顶点加入NEW,从V中去掉这些顶点。

③i=i+1；⑶若V空,结束。DBAEFC第i天考试课程为NEW中顶点所对应的课程）以某种形式输出NEW中顶点所对应的课程；1.1数据结构讨论的范畴多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECEDgraph每个圆圈代表一条通路黄灯亮的时候，只有DA,DB两条路可通行◆建模型：

问题涉及的对象：每个圆圈（即每条通路）；

圆圈之间的关系：圆圈之间的冲突关系。◆设计求解问题的方法：同上

数值问题numericalproblems*对象objects：len,wide,area

——用数值表示*对象之间的关系Therelationshipamongtheobjects：area=len

wide

——可用方程或函数表示*数据存储datastorage：可用程序设计语言中的实型变量存储数据；*问题求解方法：用某种计算方法求解；

kəm'pærisən]

非数值问题non-numericalproblems*对象objects：课程--用课程名表示*对象之间的关系：课程间有“冲突”关系*数据及数据之间的关系存储*问题求解方法不能用数值表示课程之间的这种关系不能用方程或函数表示二、数值问题与非数值问题的比较acomparisonbetweenthenumericalproblemsandnon-numericalproblems

1.1数据结构讨论的范畴numericalproblems*objects：length,wide,area

——用数值表示*Therelationshipamongobjects：area=len

wide

——可用方程或函数表示*datastorage：可用程序设计语言中的实型变量存储数据；*problemsolving：用某种计算方法求解；non-numericalproblems*objects：course--用课程名表示*Therelationshipamongobjects：课程间有“冲突”关系*datastorageandrelationshipamongobjectsstorage*problemsolving不能用数值表示课程之间的这种关系不能用方程或函数表示二、comparisonbetweennumericalproblemandnon-numericalproblem数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。datastructureisacourse,whichresearchoperationobjectofcomputer,therelationsbetweenthemandoperationaboutnon-numericalproblem1.2researchobjects数值问题是计算数学所要研究的问题。计算数学是研究数值计算方法的设计、分析和有关理论基础的数学分支。

DataStructureisasubjectofstudyingthecomputeroperationalobjects,theirrelationshipsamongthemandoperationinthenon-numericalproblem.P301.2researchobjects数值问题是计算数学所要研究的问题。计算数学是研究数值计算方法的设计、分析和有关理论基础的数学分支。1.3basicconcepts（1）data：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。计算机能处理的数据集和是随着计算机的发展而发展的，

numericaldata：整数、实数等

non-numericaldata：图形、图象、声音、文字等

（一）basicconcepts1.3basicconcepts（1）data：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。Data——thesetofnumbers,characters,whichdescribetheexternalobjects,andallinformationwhichcanbeinputintothecomputerandprocessedbycomputerprograms.SymbolSetwhichcanbeinputintothecomputerandbeidentifiedandprocessedbycomputerprograms.计算机能处理的数据集和是随着计算机的发展而发展的，数值数据：整数、实数等非数值数据：图形、图象、声音、文字等

（一）basicconcepts(2)dataelement—数据中的一个“个体”，an"individual"indata是数据结构中讨论的基本单位。但不是最小单位。Isthebasicunitofdata,butisnotthesmallestUnit;alsocallednodeorrecord.EachdataelementcanbeconsistofseveralDataItems(theminimalunitofData).数据项（dataitem）—数据结构中讨论的最小单位。(theminimalunitofData).

数据元素是数据项的集合例如：一个学生的信息（数据元素）学号姓名性别出生日期政治面貌0001陆宇男1986/09/02团员0002李明男1985/12/25党员0003汤晓影女1986/03/26团员……………(2)dataelement—数据中的一个“个体”,是数据结构中讨论的基本单位。但不是最小单位。dataitem—数据结构中讨论的最小单位。

数据元素是数据项的集合例如：一个学生的信息（数据元素）学号姓名性别出生日期政治面貌0001陆宇男1986/09/02团员0002李明男1985/12/25党员0003汤晓影女1986/03/26团员……………⑶dataobject：是性质相同的数据元素的集合，是数据的一个子集。DataObject——thesetofdataelementswithsameattribute.ItisthesubsetofDataandcanbeeitherfiniteorinfinite.例如：

整数数据对象的集合：N={0,±1,±2,…}字母字符数据对象的集合：

C={‘A’,’B’,…,’Z’}⑶dataobject：是性质相同的数据元素的集合，是数据的一个子集。例如：

整数数据对象的集合：N={0,±1,±2,…}字母字符数据对象的集合：

C={‘A’,’B’,…,’Z’}relationshipsamongdata,dataelementanddataitem包含关系：数据是由数据元素组成，数据元素是由数据项组成。数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。数据结构：相互之间存在一定关系的数据元素的集合。DataStructure——thesetofdataelementswithsomespecialrelationships.按照视点的不同，数据结构分为逻辑结构和存储结构。Accordingtothedifferentviewpoint,datastructureisdividedintologicalstructureandstoragestructure逻辑结构：指数据元素之间逻辑关系的整体。LogicalStructure关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型酒店管理问题中，客房之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？考试计划编排问题中，课程之间的逻辑关系指的是什么？DataStructure——thesetofdataelementswithsomespecialrelationships.P31datastructureisdividedintologicalstructureandstoragestructureLogicalStructure：指数据元素之间逻辑关系的整体。数据的逻辑结构是从具体问题抽象出来的数据模型酒店管理问题中，客房之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？考试计划编排问题中，课程之间的逻辑关系指的是什么？数据的逻辑结构是从具体问题抽象出来的数据模型Logicalstructureofdataisadatamodelwhichisabstractedfromthespecificissues.

二、LogicalStructure数据元素之间的逻辑关系）(1)数据的逻辑结构可归结为以下四类：Set——数据元素间除“同属于一个集合”外，无其它关系Linearlist——one-to-one，如线性表、栈、队列Tree——one-to-manygraph——多many-to-many1.2基本概念非线性结构LogicalStructure1)Set2)Linearlist3)Trees4)GraphsStorageStructure1)SequentialStorage2)LinkedStorage3)IndexedStorage4)HashingStorage(2)数据逻辑结构的形式定义formaldefinitionoflogicalstructure二元组表示法two-tuplesnotation

Data_Structure=(D

,S)其中：

D----数据元素的有限集合。finitesetofdataelement

S----定义在D上的关系的有限集合。

finitesetofrelationshipwhichdefinedinD

S={r},r是D上的一个二元关系risabinaryrelationinD1.2基本概念(2)数据逻辑结构的形式定义二元组表示法

Data_Structure=(D

,S)其中：

D----数据元素的有限集合。

S----定义在D上的关系的有限集合。

S={r},r是D上的一个二元关系1.2基本概念

L=(D,S)

其中：D={a1,a2,a3,...,an}

L=(D,S)

其中：D={a1,a2,a3,...,an}S={r}r={<a1,a2>,<a2,a3>,<a3,a4>…<an-1,an>}例1anai+1ai-1aia2a1……Linearlistset例2anai+1ai-1aia2a1……

T=(D,R)D={A，B，C，D，E，F，G，H，I，J}

R={r}

r={〈A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}

tree例3JIACBDHGFEG1=(V1,E1)V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}

V0

V4

V3

V1

V2

V0

V1

V2

V3G2=(V2,E2)V2={v0v1,v2,v3}E2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}GraphExmp4无向图有无向图P46,5题数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。

Alsoknownasthephysical,Isrepresentationofthedatawithitslogicalstructureinthecomputer.

1.3数据结构的基本概念数据结构的基本概念内存memory存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑关系的整体。存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。

1.3数据结构的基本概念数据结构的基本概念内存存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。三、StorageStructure数据的逻辑结构在计算机存储器中的实现⑴SequentialStorage用一组连续的内存单元依次存放数据元素。通过元素的存储顺序反映数据元素之间的逻辑关系a1a2……ai-1aiai+1……an⑵LinkedStorage用内存中任意一组单元存放数据元素,通过保存元素的存储位置来表示数据元素之间的逻辑关系。a1a2ai-1

aian四、Dataoperationscommonoperations◆建立数据结构◆清除数据结构◆插入一个新数据元素◆删除某个数据元素◆修改某个数据元素◆排序◆检索Insertdeleteupdateselectsort1.2基本概念1.3数据结构的基本概念（小结）数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构（取决于） 算法实现 存储结构 （依赖于）存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系1.2基本概念数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图形结构数据结构的三个方面：1.2基本概念五、datatype

andAbstractDataType1、datatype一个值的集合和定义在这个值集上的一组操作的总称。allthedatacategoriesthateachvariablepossesseddefinedinoneprogramdesignlanguage.例如：整形变量，其值为某个区间上的整数，定义在其上的操作可以为加减乘除和取模等算术运算。

数据类型原子类型（int,float,char）结构类型（数组，结构体）五、datatype

andAbstractDataType1、datatype一个值的集合和定义在这个值集上的一组操作的总称。例如：整形变量，其值为某个区间上的整数，定义在其上的操作可以为加减乘除和取模等算术运算。

datatype原子类型（int,float,char）结构类型（数组，结构体）2、AbstractDataType(ADT)指一个数据结构以及定义在该结构上的一组操作的总称.1.2基本概念2、AbstractDataType(ADT)指一个数据结构以及定义在该结构上的一组操作的总称.amathematicmodelandthesetofalloperationsdefinedonit.（其定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。）1.2基本概念AbstractDataType(ADT)——amathematicmodelandthesetofalloperationsdefinedonit.ADTcanbepresentedbyatriplet(D,S,P),while

Disdataobjects

SissetofrelationshiponD

PisoperationsinDDefinition:ADTname{Dataobjects:<definition>Datarelationships:<definition>Elementaryoperations:<definition>}ADTnameElementaryoperationname(parameterlist)initialcondition:descriptionresultofoperation:descriptionP50ADT可理解为对数据类型的进一步抽象抽象数据类型比数据类型的范畴更广，它不再局限于固有数据类型，还包括用户自己定义的数据类型ADT·逻辑结构·操作集合数据结构·存储结构·算法设计(a)使用视图——ADT的定义(b)设计视图——ADT的设计(c)实现视图——ADT的实现

图1-7

ADT的不同视图类·成员变量·成员函数本书对ADT的定义包括抽象数据类型名、数据元素之间逻辑关系的定义、每种基本操作的接口。形式如下：ADT抽象数据类型名Data

数据元素之间逻辑关系的定义Operation

操作1前置条件：执行此操作前数据所必须的状态输入：执行此操作所需要的输入功能：该操作将完成的功能输出：执行该操作后产生的输出后置条件：执行该操作后数据的状态操作2 …… ……

操作n……1.4算法和算法的分析AlgorithmandAlgorithmAnalysis一、算法（algorithm）的概念

算法是求解问题的操作序列。

AlgorithmistheoperationsequenceforsolvingproblemForexample：求两个正整数m，n中的最大数MAX的算法⑴若m>n则max=m⑵若m<=n则max=n1.4AlgorithmandAlgorithmAnalysis一、difinitionofalgorithmAlgorithmistheoperationsequenceforsolvingaproblem.Forexample：thealgorithmistofindoutthemaximumnumberMAXoftwopositiveintegersmandn.⑴if

m>nthen

max=m⑵if

m<=nthen

max=n求正整数m，n中的最大数的算法Characteristicofalgorithms：1Finiteness对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2Doubtlessness对于每种情况下所应执行的操作，在算法中都有确切的规定。读者不会产生二义性。3feasibility算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之。4

input任何算法都有输入，有些在程序运行过程当中需要输入数据，有些虽然没有输入，但其实已经把输入嵌入了算法当中5output。Whatisagoodalgorithm?1correctness:火车站怎么走往北2readability:易于人的阅读和理解多个人合作软件时候。

3robustness:输入数据非法时候，算法能做出相应反应。

4highEfficiency：TimeandSpace效率指算法的执行时间，存储量是执行算法所需要最大存储空间。1.4算法和算法的分析三、Descriptionofalgorithms

Thereareseveralcommonmethodstodescribealgorithmsasfollows:

NaturalLanguagePseudocodeProgramminglanguageFlowChartPseudocodebasedonC++languageisusedtodescribealgorithmsinourtextbook.本书采用基于C++语言的伪代码来描述。TherearetwomethodtomeasuretheexecutiontimeofaprogramEstimateinadvanceTestaftertheevents1事后统计的方法缺点：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣四、MeasurementofAlgorithmefficiencyTherearetwowaystomeasureexecutiontimeofprograms:TestaftertheeventEstimateinadvance四、Measurementofalgorithmsefficiency1Testaftertheeventsdrawback：必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣后三条和软件及硬件有关，和设计算法没关系，所以我们只考虑前两条。2Estimateinadvance⑴strategy:算法采用的策略⑵scale:问题的规模⑶书写程序的语言⑷编译程序所产生的机器代码的质量⑸机器执行指令的速度weevaluateanalgorithmfromthefollowingtwoaspects:TimeComplexitySpaceComplexity2Estimateinadvance（1）TimeComplexity

theexecutiontimesofthebasicoperation(basicstatement)forsolvingtheproblem.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间复杂度记作:

T(n)=O(f(n))Big-O它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。求解问题的基本操作（基本语句）的执行次数Thestudyofalgorithmefficiencyfocusesonloops.

multiplicationofnordermatrices：C=A×B,Thealgorithmisasfollows：求n阶矩阵的乘法#defineMAX100voidmaxtrixmult(intn,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++){//(1)for(j=1;i<=n;j++){//(2)x=0;//(3)for(k=1;k<=n;k++)//(4)x+=a[i][k]*b[k][j];//(5)c[i][j]=x;//(6)}}}calculatetimecomplexityofthealgorithm?e.g.算法中的基本操作语句为x+=a[i][k]*b[k][j]，其频度为：

所以算法的时间复杂度为算法的时间复杂度是由嵌套最深层语句即基本操作的频度决定的。Setthecoefficientofeachitemto1ExampleofBig-Oderivation5n4+10nlog2n+100log2nn4+nlog2n+log2nKeepthelargestiteminthefunctionanddiscardtheothers.O(n4)ThewaytoderiveBig-OexpressionIneachitem,setthecoefficientoftheitemto1.Keepthelargestiteminthefunctionanddiscardtheothers.Itemsarerankedfromthelowesttohighestasfollows:constant，log2n,n,nlog2n,n2,n3,…,

nk,2n,n!

Calculatetimecomplexityofthefollowingprogramsegment:s=0;for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=i+j;k++)s++;解：该算法的基本操作是语句S++，其频度为：

例

一个没有循环的算法的基本运算次数与问题规模n无关,记作O(1),也称作常数阶。一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系,记作O(n),也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。各种不同数量级对应的值存在着如下关系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)例求阶乘和：sum=1!+2!+3!+……+n!方法1：

floatsum1(intn){floats=0,p=1;inti;for(i=1;i<=n;i++){p=p*i;s=s+p}returns;}timecomplexity：T(n)=O(n)

方法2：

floatsum1(intn){floats=0,p=1;inti,j;for(i=1;i<=n;i++){p=1for(j=1;j<=i;j++)p=p*i;s=s+p;}returns;}timecomplexity：T(n)=O(n2)

T(n)===n-1+n-2+n-3+……+1=例

BubbleSort

algorithmvoidbubble_sort(inta[],intn)