还剩17页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
算法设计与分析第1章绪论算法理论研究的是算法的设计技术和算法的分析技术,前者是指面对一个问题,如何设计一个有效的算法,后者则是对已设计的算法,如何评价或者判断其优劣二者是相互依存的,设计出的算法需要检验和评价,对算法的分析反过来又将改进算法的设计
1.1算法的基本概念算法的概念在计算机科学领域几乎无处不在,在各种计算机软件系统的实现中,算法设计往往处于核心地位例如,操作系统是现代计算机系统中不可缺少的系统软件,操作系统的各个任务都是一个单独的问题,每个问题由操作系统中的一个子程序根据特定的算法来实现用什么方法来设计算法,如何判定一个算法的优劣,所设计的算法需要占用多少时间资源和空间资源,在实现一个软件系统时,都是必须予以解决的重要问题
1.
1.1为什么要学习算法用计算机求解任何问题都离不开程序设计,而程序设计的核心是算法设计普通来说,对程序设计的研究可以分为四个层次算法、方法学、语言和工具,其中算法研究位于最高层次算法对程序设计的指导可以延续几年甚至几十年,它不依赖于方法学、语言和工具的发展与变化例如,用于数据存储和检索的Hah算法产生于20世纪50年代,用于排序的快速排序算法发明于20世纪60年代,但他们至今仍被人们广为使用,可是程序设计方法已经从结构化发展到面向对象,程序设计语言也变化了几代,至于编程工具很难维持三年不变所以,对于从事计算机专业的人士来说,学习算法是非常必要的⑴样本的规模一种可借鉴的方法是先从一个较小的样本规模开始,如果有必要再加大样本规模⑵样本的范围普通来说,输入样本的范围不要小得没故意义,也不要过分大止匕外,还要设计一个能在所选择的样本范围内产生输入数据的程序⑶样本的模式输入样本可以符合一定的模式,也可随机产生根据一个模式改变输入样本的好处是可以分析这种改变带来的影响,例如,如果一个样本的规模每次都会翻倍,可以通过计算T2n/Tn,考察该比率揭示的算法性能是否符合一个基本的效率类型如果对于相同规模的不同输入实例,实验数据和实验结果会有很大不同,则需要考虑是否包括同样规模的多个不同输入实例例如排序算法,对于同样数据集合的不同初始罗列,算法的时间性能会有很大差别
174.对输入样本运行算法对应的程序,记录得到的实验数据作为实验结果的数据需要记录下来,通常用表格或者散点图记录实验数据,散点图就是在笛卡儿坐标系中用点将数据标出以表格呈现数据的优点是直观、清晰,可以方便地对数据进行计算,以散点图呈现数据的优点是可以确定算法的效率类型例如表
1.1是对某算法采用计数法得到的实验数据,图L7是一个典型的散点图表
1.1表格法记录实验数据规模次数100011,966200024,303执行次数或者时间300039,992400053,010500067,272600078,692700091,2748000113,0639000129,799问题规模n图
1.7典型的散点图
5.分析得到的实验数据根据实验得到的数据,结合实验目的,对实验结果进行分析,并根据实验结果不断调整实验的输入样本,经过对照分析,得出具体算法效率的有关结论算法的数学分析和实验分析的基本区别是数学分析不依赖于特定输入,缺点是合用性不强,特别对算法做平均性能分析时实验分析能够适用于任何算法,但缺点是其结论依赖于实验中使用的特定输入实例和特定的计算机系统实际应用中,可以采用数学分析和后验分析相结合的方式来分析算法此时,描述算法效率的函数是在理论上确定的,而其中一些必要的参数则是针对特定计算机或者程序根据实验数据得来
6.3实验项目一一求最大公约数
1.实验题目求两个自然数m和n的最大公约数
2.实验目的⑴复习数据结构课程的相关知识,实现课程间的平滑过渡;18⑵掌握并应用算法的数学分析和后验分析方法;⑶理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同
3.实验要求⑴至少设计出三个版本的求最大公约数算法;⑵对所设计的算法采用大0符号进行时间复杂性分析;⑶上机实现算法,并用计数法和计时法分别测算算法的运行时间;⑷通过分析对照,得出自己的结论
4.实现提示设m和n是两个自然数,m和n的最大公约数记为gcdm,n,是能够同时被m和n整除的最大整数下面给出求最大公约数三个版本的算法思想,注意算法中没有对输入数据进行校验算法
1.4连续整数检测
1.t二min{m,n};
2.m除以t,如果余数为0,则执行步骤3,否则,执行第4步;
3.n除以t,如果余数为0,返回t的值作为结果,否则,执行第4步;
4.t=t-L转第2步;例如,要计算gcd66,12,首先令t=12,因为66除以12余数不为0,将t减1,而12除以11余数不为0,再将t减1,重复上述过程,直到t=6,止匕时12除以6的余数为0并且66除以6的余数为0,则gcd66,12=6算法L5——欧几里德算法l.r=m%n;
2.循环直到r=
02.1m=n;
2.2n=r;
2.3厂m%n;
3.输出n;例如,要计算gcd66,12,因为66除以12的余数为6,再将12除以6,余数为0,贝U gcd66,12=6算法
1.6——分解质因数
1.将m分解质因数;
2.将n分解质因数;
3.提取m和n中的公共质因数;
4.将m和n中的公共质因数相乘,乘积作为结果输出;19例如,要计算gcd66,12,首先分解质因数66=2某3某11,12=2某2某3,然后提取二者的公共质因数2某3,则gcd66,12=2某3=6严格地说,算法
1.6还不能称为一个真正意义上的算法,因为其中求质因数的步骤没有明确定义(该步骤应该得到一个质因数的数组),如何提取m和n中的公共质因数也没有定义清晰,请读者将这个算法补充完整阅读材料一一人工神经网络与BP算法人工神经网络(ArtificialNeuralNetwork,简称ANN)是一个以有向图为拓扑结构的动态系统,它通过对连续或者断续的输入作状态响应而进行信息处理人工神经网络技术与计算机技术的结合,为人类进一步研究摹拟人类智能及了解人脑思维的神奇开辟了一条新途径人类对人工神经网络的研究可以追溯到1943年,心理学家W.S.McCuloch和数理逻辑学家W.Pitt最早提出的人工神经网络模型——M-P模型,这是第一个用数理语言描述人脑的信息处理过程的模型,从此开创了神经科学理论研究的新纪元;1969年,人工智能的创始人之一M.Minky和S.Papert出版了有较大影响的《感知器》一书,指出感知器功能上的局限性,该论点极大地影响了人工神经网络的研究,至此进入了人工神经网络发展史上长达10年的低潮期进入80年代后,随着计算机科学、生物技术和光电技术等领域学科的迅速发展,人工神经网络的研究进入到了一个新的大发展阶段1982年美国生物学家、物理学家J.Hopfield提出了Hopfield网络模型;1985年D.E.Rumelhart和J.LMcclelland提出了误差反向传播算法(Back-PropagationA1gorithm,简称BP算法),成为至今为止影响较大的一种网络学习方法;1992年,Holland用摹拟生物进化的方式提出了遗传算法,用来求解复杂优化问题;1995年Mitra把人工神经网络与含糊逻辑理论、生物细胞学说以及概率论相结合提出了含糊神经网络,使得神经网络的研究取得了突破性发展人工神经网络是由许多人工神经元按一定规则连接构成的,其互连模式有许多的种类,常见的一种分类是前馈网络和反馈网络1988年,以美国学者Rumelhart、Hinton和William等为首,提出了基于BP算法的多层前向神经网络,成功地解决了多层神经网络中隐含层神经元连接权值的学习问题该网络模型一经问世,即将受到众多学者的关注,并取得了很大发展目前,该网络是最常用、最流行、最成熟的人工神经网络其学习方式采用误差反向传播算法,具有很强的非逻辑归纳特性理论研究表明一个三层的前馈神经网络能够摹拟任何复杂的非线性系统图1是三层前向神经网络拓扑结构图20YllWijY12WjkY13jk输入层隐含层输出层图1三层前向神经网络拓扑结构图说明Yil为输入层结点i的输入,Yk3为输出层结点k的输出,YJ2为隐含层结点j的输出,Tk为输出层结点k对应的教师信号,Wij为结点i和结点j间的连接权值,Wjk为结点j和结点k间的连接权值,k为输出层结点k的阀值,j为隐含层结点j的阈值BP算法的主要思想是,学习过程由信号的正向传播与误差的逆向传播两个过程组成,正向传播时,模式作用于输入层,经隐含层处理后,传向输出层若输出层未能得到期望的输出,则转入误差的逆向传播阶段,将输出误差按某种形式,通过隐含层向输入层逐层返回,并“分摊”给各层的所有单元,从而获得各层单元的参考误差(称误差信号),以作为修改各单元间权值的依据这种信号正向传播与误差逆向传播的各层权矩阵的修改过程,是周而复始地进行的,权值不断修改的过程也就是网络的学习或者称训练过程此过程向来进行到网络输出的误差逐渐减小到可接受的程度或者达到设定的学习次数为止设隐含层和输出层的激活采用s型函数;f某1le某由于BP算法要求网络的输入输出函数具有可微分性,而S型函数具有此特性从形式上看,S型函数的输出曲线两端平整,中间部份变化激烈;从生理学角度看,一个人对远远低于或者高于他智力和知识水平的问题,往往很难产生强烈的思维反应;从数学角度看,S型函数具有可微分性,且具有饱和非线性,可以增加网络的非线性映射能力,因此S型函数更接近于生物神经元的信号输出形式,所以选用S型函数作为BP网络的输出函数误差函数网络的实际输出向量Yk与教师信号向量Tk的误差采用二乘误差函数;1NE TkYk22K1BP算法的普通框架如下
211.初始化网络权值Wt和阈值t;其中,Wt和t为较小的随机数,t为学习次数,初始值为0;
2.输入一个学习样本某k,Tk,其中k=l,2,,n,n为样本数;
3.计算隐含层各结点的输出值;
4.计算输出层结点的输出值;
5.计算输出层结点和隐含层结点之间权值的修正量;
6.计算隐含层结点和输入层结点之间权值的修正量;
7.基于步骤5的修正量来修正输出层和隐含层连接权值矩阵和阈值向量;
8.基于步骤6的修正量来修正隐含层和输入层连接权值矩阵和阈值向量;
9.判断全部学习样本是否未取完,若取完,则转步骤2,否则
9.1计算误差函数;
9.2若小于规定的误差上限,则算法结束;
9.3若已达到学习次数,则算法结束;否则t=t+l,转步骤2;人工神经网络具有以分布方式存储知识、并行方式处理、较强的容错能力,并且它具有可以逼近任意的非线性函数以及有很强的自学习、自适应及联想记忆功能等特征,吸引了众多研究人员的兴趣,并在相关领域取得了显著的发展例如自动化领域中的系统识别和神经控制器以及智能检测,经济领域中的市场预测和信贷分析,工程领域中的汽车工程、军事工程、水利工程、化学工程,信息领域中的信号处理、模式识别、数据压缩,医学领域中的生物活动分析、医学专家系统等参考文献口]周春光等.计算智能.吉林大学出版社,2001[2]李晓峰.人工神经网络BP算法的改进与应用.四川大学学报.20002习题
11.在欧几里德提出的欧几里德算法中即最初的欧几里德算法用的不是除法而是减法请用伪代码描述这个版本的欧几里德算法
2.图论诞生于七桥问题出生于瑞士的伟大数学家A欧拉LeonhardEuler,1707—1783提出并解决了D该问题七桥问题是这样描述的一个人是否能在C一次步行中穿越哥尼斯堡现在叫加里宁格勒,在波罗的海南岸城中全部的七座桥后回到起点,且每座桥只经过一次,右面是这条河以及河上的两个B岛和七座桥的草图请将该问题的图模型抽象出来,第2题图并判断此问题是否有解
3.计算Jr值的问题能精确求解吗?设计求解冗值的算法
4.设计算法求数组中相差最小的两个元素称为最接近数的差要求分别给出伪代22码和C++描述
5.对于下列函数,请指出当问题规模增加到4倍时,函数值会增加多少?1log2n2n3n4n25n362n
6.考虑下面的算法,回答下列问题〃n1该算法求的是什么?intSteryintn为非负整数{2该算法的基本语句是什么?S=0;3基本语句执行了多少次?fori=l;i〈=n;i++4该算法的效率类型是什么?S=S+i某i;returns;5对该算法进行改进,分析改进算法的效率;}6如果算法不能再改进了,请证明这一点
7.使用扩展递归技术求解下列递推关系式1Tn4nllnl2Tn3Tnlnl2Tn3nnl
8.考虑下面的递归算法,回答下列问题intQintn//n为正整数1该算法求的是什么?{2写出n二3时的执行过程;if n—1returnl;elereturnQ n-1+2某n-l;3建立该算法的递推关系式并求解;}4将该算法转换为非递归算法
9.欧几里德算法在输入规模为n时的平均效率,是根据算法执行的平均除法次数Davgn来度量的,Davgn是gcdn,1,gcdn,2,,gcdn,nT和gcdn,n的除法次数的平均值例如Davg5=1+2+3+2+D/5=
1.8画出Davgn的散点图,并指出可能的效率类型
10.如果Tln=Ofn,T2n=0gn,证明1T1n+T2n=ma某{0fn,0gn}2T1n某T某n=0fn某0gn
11.国际象棋是很久以前由一个印度人Shahi发明的,当他把该发明献给国王时,国王很高兴,就许诺可以给这个发明人任何他想要的奖赏Shahi要求以这种方式给他一些粮食棋盘的第1个方格内只放1粒麦粒,第2格2粒,第3格4粒,第4格8粒,,以此类推,直到64个方格全部放满这个奖赏的最终结果会是什么样呢?
12.有4个人打算过桥,这个桥每次最多只能有两个人同时通过他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们惟独一只手电筒这就意味着两个人过桥后必须有一个人将手电筒带回来每一个人走路的速度是不同的甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥至少要用多长期?
13.欧几里德游戏开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经浮现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了请问,你是选择先行动还是后行动?为什么?23学习算法还能够提高人们分析问题的能力算法可以看做是解决问题的一类特殊方法一一它不是问题的答案,而是经过精确定义的
①、用来获得答案的求解过程因此,无论是否涉及计算机,特定的算法设计技术都可以看做是问题求解的有效策略著名的计算机科学家科努思Donald-Knuth是这样论述这个问题的“受过良好训练的计算机科学家知道如何处理算法,如何构造算法、操作算法、理解算法以及分析算法,这些知识远不只是为了编写良好的计算机程序而准备的算法是一种普通性的智能工具,一定有助于我们对其他学科的理解,不管是化学、语言学、音乐还是此外
①算法固有的精确性限制了它所能够解决的问题种类,比如说,我们无法找到一个使人生活快乐的算法,也不能找到一个使人富有和出名的算法的学科为什么算法会有这种作用呢?我们可以这样理解人们常说,一个人惟独把知识教给别人,才干真正掌握它实际上,一个人惟独把知识教给计算机,才干真正掌握它,也就是说,将知识表述为一种算法比起简单地按照常规去理解事物,用算法将其形式化会使我们获得更加深刻的理解”算法研究的核心问题是时间速度问题人们可能有这样的疑问既然计算机硬件技术的发展使得计算机的性能不断提高,算法的研究还有必要吗?计算机的功能越强大,人们就越想去尝试更复杂的问题,而更复杂的问题需要更大的计算量现代计算技术在计算能力和存储容量上的革命仅仅提供了计算更复杂问题的有效工具,无论硬件性能如何提高,算法研究始终是推动计算机技术发展的关键下面看几个例子
1.检索技术20世纪50~60年代,检索的对象是规模比较小的数据集合例如,编译系统中的标识符表,表中的记录个数普通在几十至数百这样的数量级70^80年代,数据管理采用数据库技术,数据库的规模在K级或者M级,检索算法的研究在这个时期取得了巨大的发展90年代以来,Internet引起计算机应用的急速发展,海量数据的处理技术成为研究的热点,而且数据驻留的存储介质、数据的存储方法以及数据的传输技术也发生了许多变化,这些变化使得检索算法的研究更为复杂也更为重要了近年来,智能检索技术成为基于Web信息检索的研究热点使用搜索引擎进行Web信息检索时,时常看到一些搜索引擎前50个搜索结果中几乎有一半来自同一个站点的不同页面,这是检索系统缺乏智能化的一种表现此外,在传统的Web信息检索服务中,信息的传输是按“Pull”的模式进行的,即用户找信息而采用“Puh”的方式,是信息找用户,用户不必进行任何信息检索,就能方便地获得自己感兴趣的信息,这就是智能信息推送技术这些新技术的每一项重要进步都与算法研究的突破有关
2.压缩与解压缩随着多媒体技术的发展,计算机的处理对象由原来的字符发展到图象、图形、音频、视频等多媒体数字化信息,这些信息数字化后,其特点就是数据量非常庞大,同时,多媒体所需的高速传输速度也是计算机总线所不能承受的因此,对多媒体数据的存储和传输都要求对数据进行压缩声音文件的MP3压缩技术说明了压缩与解压缩算法研究的巨大成功,一个播放34分钟歌曲的〜MP3文件通常只需3MB摆布的磁盘空间
3.信息安全与数据加密2来盗用你的信用卡!”这的确是一个可怕的情景所以,在电子商务中,信息安全是最关键的问题,保证信息安全的一个方法就是对需要保密的数据进行加密在这个领域,数据加密算法的研究是绝对必须的,其必要性与计算机性能的提高无关算法及其重要特性算法(Algorithm)被公认为是计算机科学的基石通俗地讲,算法是解决问题的方法,严格地说,算法是对特定问题求解步骤的一种描述,是指令的有限序列,止匕外,算法还必须满足下列五个重要特性⑵输出一个算法有一个或者多个输出既然算法是为解决问题而设计的,那末算法实现的最终目的就是要获得问题的解没有输出的算法是无意义的⑶有穷性一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都在有穷时间内完成⑷确定性算法中的每一条指令必须有切当的含义,不存在二义性并且,在任何条件下,对于相同的输入只能得到相同的输出⑸可行性算法描述的操作可以通过已经实现的基本操作执行有限次来实现问题输出输入算法(确定性、有穷性、可行性)图
1.1算法的概念概念回顾算法和程序不同程序(Program)是对一个算法使用某种程序设计语言的具体实现,原则上,算法可以用任何一种程序设计语言来实现算法的有穷性意味着不是所有的计算机程序都是算法
1.
1.3算法的描述方法算法设计者在构思和设计了一个算法之后,必须清晰准确地将所设计的求解步骤记录下来,即描述算法常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等下面以欧几里德算法(用展转相除法求两个自然数m和n的最大公约数)为例进行介绍3⑴自然语言用自然语言描述算法,最大的优点是容易理解,缺点是容易浮现二义性,并且算法通常都很冗长欧几里德算法用自然语言描述如下
①输入m和n;
②求m除以n的余数r;
③若r等于0,则n为最大公约数,算法结束;否则执行第
④步;
④将n的值放在m中,将r的值放在n中;
⑤重新执行第
②步⑵流程图用流程图描述算法,优点是直观易懂,缺点是严密性不如程序设计语言,灵便性不如自然语言欧几里德算法用流程图描述如图L2所示在计算机应用早期,使用流程图描述算法占有统治地位,但实践证明,除了一些非常简单的算法以外,这种描述方法使用起来非常不方便如今,只能在早期有关算法的教材中找到它的踪影了⑶程序设计语言用程序设计语言描述的算法能由计算机直接执行,而缺点是抽象性差,使算法设计者拘泥于描述算法的具体细节,忽略了“好”算法和正确逻辑的重要性,止匕外,还要求算法设计者掌握程序设计语言及其编程技巧开始欧几里德算法用C++语言书写的程序如下#includeintr=m%n;whiler!=0{m=n;n=r;r=m%n;}returnn;}voidmainO{cout伪代码Peudocode是介于自然语言和程序设计语言之间的方法,它采用某一程序设计语言的基本语法,操作指令可以结合自然语言来设计至于算法中自然语言4输入m和nr二m%nYNnFnn=r输出n结束图
1.2用流程图描述算法r二0的成份有多少,取决于算法的抽象级别,抽象级别高的伪代码自然语言多一些计算机科学家从来没有对伪代码的书写形式达成过一种共识,只是要求了解任何一种现代程序设计语言的人都能很好地理解欧几里德算法采用符合C++语法的伪代码描述如下算法L1——欧几里德算法
1.r=m%n;
2.循环直到r=
02.1m=n;
2.2n=r;
2.3r=m%n;
3.输出n;伪代码不是一种实际的编程语言,但在表达能力上类似于编程语言,同时极小化了描述算法的不必要的技术细节,是比较合适的描述算法的方法,被称为“算法语言”或者“第一语言”
1.
1.4算法设计的普通过程算法是问题的解决方案,这个解决方案本身并非问题的答案,而是能获得答案的指令序列不言而喻,由于实际问题千奇百怪,问题求解的方法千变万化,所以,算法的设计过程是一个灵便的充满智慧的过程,它要求设计人员根据实际情况具体问题具体分析可以肯定的是,发明(或者发现)算法是一个非常有创造性和值得付出的过程
②在设计算法时,遵循下列步骤可以在一定程度上指导算法的设计
1.理解问题在面对一个算法任务时,算法设计者往往不能准确地理解要求他做的是什么,对算法希翼实现什么惟独一个大致的想法就匆忙地落笔写算法,其后果往往是写出的算法漏洞百出在设计算法时需要做的第一件事情就是彻底理解要解决的问题,子细阅读问题的描述,手工处理一些小例子对设计算法来说,这是一项重要的技能准确地理解算法的输入是什么?要求算法做的是什么?即明确算法的入口和出口,这是设计算法的切入点
2.预测所有可能的输入算法的输入确定了该算法所解问题的一个实例普通而言,对于问题P,总有其相应的实例集L则算法A若是问题P的算法,意味着把P的任一实例input£1作为算法A的输入,都能得到问题P的正确输出
②这个普通过程并非一个绝招,能为任意的问题设计算法,一个公认的事实是一一这样的绝招是不存在的
53.通用分治递推式递归算法分析的第三种技术是利用通用分治递推式cTnkaTnbcnn1n1其中a,b,c,k都是常数这个递推式描述了大小为n的原问题分成若干个大小为n/b的子问题,其中a个子问题需要求解,而cnk是合并各个子问题的解需要的工作量下面使用扩展递归技术对通用分治递推式进行推导,并假定n二bmnT naTcnkbnnaaT2c cnkbbaT1ammmlknncmlaccnkbbkkkncaniiinibi OcamibikiOmbkmcaiOamibk这个求和是一个几何级数,其值依赖于比率ra,注意至Uam=alogbn=n1ogba,有以下三种情况1,由于am=nlogba,所以T n=0nlogba IriOm2r=lrimllogbnl,0由于am=nlogba=nk,所以Tn=0nklogbno1rlriiOmrmlImmkmk3rlrOrm,所以,T n=0ar=0b=0norliOmi对通用分治递推式的推导概括为下面的主定理0n Iogba Tn0nk Iogbn kOn abkabkabkl
61.
2.5算法的后验分析前面我们介绍了如何对非递归算法和递归算法进行数学分析,这些分析技术能够在数量级上对算法进行精确度量但是,数学不是万能的,实际上,许多貌似简单的算法很难用数学的精确性和严格性来分析,特别在做平均效率分析时算法的后验分析(Poteriori)也称算法的实验分析,它是一种事后计算的方法,通常需要将算法转换为对应的程序并上机运行其普通步骤如下
1.明确实验目的在对算法做实验分析时,可能会有不同的目的,例如,检验算法效率理论分析的正确性;比较相同问题的不同算法或者相同算法的不同实现间的效率,等等,实验的设计依赖于实验者要寻求什么答案
2.决定度量算法效率的方法,为实验准备算法的程序实现实验目的有时会影响,甚至会决定如何对算法的效率进行度量普通来说,有以下两种度量方法⑴计数法在算法中的适当位置插入一些计数器,来度量算法中基本语句(或者某些关键语句)的执行次数⑵计时法记录某个特定程序段的运行时间,可以在程序段的开始处和结束处查询系统时间,然后计算这两个时间的差对于某些典型的算法(例如TSP问题),研究人员已经制定了一系列输入实例作为测试的基准,但大多数情况下,需要实验人员自己确定实验的输入样本普通来说,通常需要确定。