第1章 算法分析的基本概念和方法

《第1章 算法分析的基本概念和方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法分析的基本概念和方法内容提要一、算法及其特性二、算法的时间空间复杂度三、算法分析(AlgorithmAnalysis)1.分析算法时间复杂度的基本步骤2.算法时间复杂度的有关概念3.分析、求解算法复杂度的方法四、最优算法(optimalalgorithm)知识要点算法分析的概念复杂度渐近表示的记号：O,,平均时间复杂度，最坏时间复杂度，最好时间复杂度最优算法分析算法复杂度的基本方法分析算法时间复杂度的步骤基本运算执行频数的统计方法数学知识：求和公式、定积分近似求和、递归方程的求解学习要求掌握算法复杂度的基本概念熟悉算法复杂度分析的基本方法1.1．算法及

2、其特性一、算法(algorithm)算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。二、算法的五个特性确定性能行性有穷性输入输出1.1．算法及其特性衡量算法性能一般有下面几个标准：确定性易读性健壮性算法的时间和空间性能：高效率和低存储空间本课程中主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准，而且主要侧重于时间方面。三、衡量算法性能的标准1.2.算法的时间空间复杂度算法的时间复杂度：在算法运行期间所花费的时间。通常用渐进形式表示。比如，T(n)=O(n2)、(n2)或(n2)一、算法的时间复杂度(TimeComplexity)

3、1.2.算法的时间空间复杂度算法的空间复杂度：在算法运行期间所需要的内存空间，通常指除开容纳输入数据之外的附加空间（auxiliaryspace,orworkspace）。通常用渐进形式表示。比如，S(n)=O(n2)、(n2)或(n2)二、算法的空间复杂度(SpaceComplexity)1.2.算法的时间空间复杂度算法分析是指对于计算机算法的时间和空间复杂度进行定量的分析。为了确切起见，假定执行算法的计算机是满足如下条件的“通用型”计算机：顺序处理机：每次执行程序中的一条指令；RAM足够大；在固定的时间内可把一个数从一个单元取出或者存入。下面将学习算法分析的

4、主要内容：分析算法时间复杂度的基本步骤算法时间复杂度的有关概念分析、求解算法复杂度的数学知识三、算法分析(AlgorithmAnalysis)1.3.分析复杂度的基本步骤对算法的分析必须脱离具体的计算机结构和程序设计语言。因此，比较两个算法的好坏，看其中所需的运算时间的长短是由算法所需的运算次数决定的。任何一个算法都可能有几种运算，因此，我们抓住其中影响算法运行时间最大的运算作为基本运算。如在一个字表中寻找Z的问题，把Z和表中元素的比较作为基本运算。两个实数矩阵相乘的问题中，则把两个实数相乘作为基本运算。一、选取一种运算作为基本运算(basicoperation)1

5、.3.分析复杂度的基本步骤一个计算步骤，如果其时间耗费总是不超过某个常量，而与输入和算法无关，则称之为元运算。元运算(elementaryoperation)常见的元运算算术运算：加、减、乘、除；比较和逻辑运算；赋值运算，包括指针赋值（比如，在遍历表或树时的指针赋值）；等等。1.3.分析复杂度的基本步骤同一个问题对不同的输入，基本运算的次数亦可能不同。因此，我们引进问题大小（即规模，size）的概念。例如，在一个姓名表中寻找给定的Z的问题，问题的大小可用表中姓名的数目表示。对于两个实数矩阵相乘的问题，其大小可用矩阵的阶来表示。而对于遍历一棵二叉树的问题，其大小是用树

6、中结点数来表示等等。这样，一个算法的基本运算的次数就可用问题的大小n的函数f(n)来表示。二、表示出在算法运行期间基本运算执行的总频数1.3.分析复杂度的基本步骤在一个算法中，出现的频数最高（在相差一个常数因子的意义上）的元运算称为基本元算。基本运算(basicoperation)常见的基本运算当分析查找和排序的算法时，如果元素的比较是元运算，则可作为基本运算；在矩阵乘法的算法中，数的乘法可作为基本运算；当遍历链表时，给指针赋值或者更新指针的操作可作为基本运算；在图的遍历中，可以将访问节点的操作为基本运算；等等。1.3.分析复杂度的基本步骤在实际中精确地求一个算法的

7、基本运算次数f(n)等于多少，往往不容易，甚至有时根本不可能，有些即使求出结果很长，很繁琐，不易比较，需要简化。这时候我们可以不精确地估计f(n)。此外，我们分析算法的时间目的主要在于，能区分不同算法的优劣，在n很小时候，差别不大，随着n的逐渐增大，差别越来越大，是个极限行为。基于上述原因，引进下面渐近表示的方法。复杂度渐近表示可以将简洁地表示出复杂度的数量级别。三、渐近时间复杂度(asymptotictimecomplexity)1.3.分析复杂度的基本步骤设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c>0和一个自然数n0，使得对于任意