算法分析基础

第1章算法分析基本概念曹霑懋[e-mail]《算法设计技巧与分析》Chapter1BasicConceptsinAlgorithmicAnalysis内容•1.1Introduction•l.2HistoricalBackground•1.3BinarySearch•1.3.1Analysisofthebinarysearchalgorithm•1.4MergingTwoSortedLists•1.5SelectinnSort•1.6InsertionSort•1.7Bottom-UpMergeSorting•1.7.1Analysisofbottom-upmergesorting•2020/1/19华南师范大学计算机学院2•1.8TimeComplexity•1.8.1Orderofgrowth•1.8.2TheO-notation•1.8.3Thefl-notation•l.8.4Thee-notation•1.8.5MamPles•1.8.6Complekityclassesandtheo-notation•1.9SpaceComplexity•1.10OptimalAlgorithms2020/1/19华南师范大学计算机学院3Chapter1BasicConceptsinAlgorithmicAnalysis内容2020/1/19华南师范大学计算机学院41.1引言DonaldE.Knuth:计算机科学就是算法的研究.每个领域:依赖有效算法设计运行时间:由例子到理论时间是衡量算法有效性的最好测度算法的几个方面：输入有限指令集输出(存在?Y/N)2020/1/19华南师范大学计算机学院5算法概念算法是程序设计的精髓，程序设计的实质就是细化构造解决问题的算法，将其解释为计算机语言。算法是在有限步骤内求解某一问题所使用的一组定义明确的指令（规则）。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。2020/1/19华南师范大学计算机学院6算法几点说明1.“算法”的2.“算法”的现代诠释3.学习“算法”的方法几个词：Algorithm、Logarithm、Algorism算法的现代意义十分类似于处方、过程、方法、规程、程序，一个算法就是有穷规则的集合。其中，规则规定了一个解决某一特定类型的问题的运算序列。一个算法应该是可以信赖的，而且学习一个算法直到彻底掌握的最好方法是反复进行试验。因此，遇到一个算法时，应该找出这个算法的一个例子，给出该例子的要点进行试验。2020/1/19华南师范大学计算机学院7•程序是算法用某种程序设计语言的具体实现。•程序可以不满足算法的有限性的性质。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。•操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。程序(Program)2020/1/19华南师范大学计算机学院81.2历史背景20世纪,早期,30年代能否用有效的过程来求解问题受到关注问题分类为:可解、不可解（存在有效过程来求解问题）计算模型：存在模型，用此模型能建立一求解某问题的算法，－－入－－可解的类模型列举：歌德尔的递归函数，Church的Lamda演算，Post的波斯特机，Turing机。Church论断：所有4个模型等效。如果一个问题在某一模型上可解，那么在其他模型上都是可解的。＝“几乎所有”问题都是不可解的。确定一个包含N个变量的多项式方程是否有整数解简单理由陈述：P3Top可判定性－〉可计算性理论，可解性－〉计算理论；有DigitalComputer后，对可解问题的研究的要求越来越多。程序，资源量，尽可能少使用资源（时间，空间）的有效算法的需求。效率：指解决问题所需时间和空间排序一组元素的算法作为研究的实例表明：设计了许多有效算法，解决问题的效率将不会因其他方法而有大的提高。2020/1/19华南师范大学计算机学院9好的算法所具备的意义2020/1/19华南师范大学计算机学院10衡量算法性能的标准•衡量算法性能一般有下面几个标准–正确性–易读性–健壮性–算法的时间和空间性能：高效率和低存储空间我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。2020/1/19华南师范大学计算机学院11算法的表达机制【表达算法的抽象机制】对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数学模型。接着，弄清该问题数学模型在已知条件下的初始状态和要求的结果状态，以及这两个状态之间的隐含关系。然后探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。2020/1/19华南师范大学计算机学院12算法的描述方法自然语言；图表；框图；计算机语言或程序设计语言等。如，汇编、C++、Java。1.3二分搜索•假定元素满足：线序集合•Ａ[1…n]中有ｘ吗？•从头到尾的扫描，比较ｎ次：顺序搜索•顺序搜索适合无序的集合•有序的集合：BinarySearchＰ４•要求能够写出：这个简单的算法，并分析运算量。2020/1/19华南师范大学计算机学院132020/1/19华南师范大学计算机学院141.3-(例)线性查找的时间评估最小查找时间？最好情况,A[1]=X平均查找时间？P(i)=1/n,Tavg(n)=n/2最大查找时间？最坏情况,x不在A[1...n]或x=A[n],复杂度为n2020/1/19华南师范大学计算机学院151.3二分搜索及其时间复杂度•线性搜索•二分搜索同数据结构，略。但要求作为例子或问题求解。及其算法分析比较次数分析•Ｗｈｉｌｅ中，ｊ次循环时剩余元素数目Floor(n/2j-1)•循环停止条件：找到ｘ，或当前查找范围的数组长度为１。•最大搜索次数：满足Floor(n/2j-1)=1时的ｊ值–即：１n/2j-12–也即：2j-1n2j–j-1lognjj=Floor(logn)+12020/1/19华南师范大学计算机学院162020/1/19华南师范大学计算机学院17随堂练习设有序数组：试搜索x=20,以及X=22.1）拟用什么法？为什么？2）试给出用你想要得算法求解的过程。参考：教材binarySearchExample1.12020/1/19华南师范大学计算机学院18二分查找的基本运算量分析？1.10最优算法－•定义：•排序问题中的Ｂｏｔｔｏｍｕｐｓｏｒｔ•Ｈｅａｐｓｏｒｔ•ｐ２０2020/1/19华南师范大学计算机学院192020/1/19华南师范大学计算机学院201.11-14.算法分析(AlgorithmAnalysis)•算法分析：对于算法的时间和空间复杂度进行定量分析。–分析算法时间复杂度的基本步骤–元运算考察–可以做基本运算的有那些，选基本运算–基本运算的总量评估–借助数学公式，比如循环嵌套就是乘法原理，递归调用对应递归公式等求解2020/1/19华南师范大学计算机学院21简例－－估计算法运行时间算法时间复杂度的有关概念：Ｏ，，，平均分析、求解算法复杂度的基本方法设计计算过程如下：（为讨论方便，每行前加一行号）(1)fori:=1ton(2)forj:=1ton(3)x:=x+1......试问在程序运行中各步执行的次数各为多少？上例中的赋值操作基本运算时间复杂性可粗略地表示为f(n)=O(n2)。要更多地了解关于算法的复杂性，就必须弄清楚如下两个问题：(1)用怎样的一个量来表达一个算法的复杂性；(2)对于给定的一个算法，怎样具体计算它的复杂性。2020/1/19华南师范大学计算机学院22分析时间复杂度的基本步骤一、选取一种元运算作为基本运算二、表示出在算法运行期间基本运算执行的总频数三、渐近时间复杂度（asymptotictimecomplexity）2020/1/19华南师范大学计算机学院23思考与练习：指出下面程序段中语句标[*]的频度和该程序段的时间复杂性。(1)[*]y:=sin(x);(2)fori:=1ton-1do[*]y:=y+1;forj:=0to2*ndo[*]x:=x+1;(3)x:=1;y:=1;fork:=1tondo[*]x:=x+1;fori:=1tondoforj:=1tondo[*]y:=y+1;(4)i:=1;while(in&&x!=A[i])do[*]i:=i+1;ifA[i]=xthenretun(i)可否改造（4）？2020/1/19华南师范大学计算机学院24算法复杂性算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。算法的复杂性分析的意义：对算法的设计或选用有着重要的指导意义和实用价值。对算法的分析，以确定或判断算法的优劣，通常以时间复杂性来衡量，时间复杂性越低，对应的算法就越优。2020/1/19华南师范大学计算机学院25算法的复杂性分析–附加5个说明1.算法复杂性概述算法复杂性=算法所需要的计算机资源。算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题实例（Instance)的规模（输入大小）。2.算法的时间复杂性（1）最坏情况下的时间复杂性Tmax(n)=max{T(I)|size(I)=n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)|size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。nIsizeITIp)()()(2020/1/19华南师范大学计算机学院263.算法渐近复杂性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。4.渐近复杂性分析的记号Ο：渐近上界记号（ab）Ω：渐近下界记号（ab）θ：渐近同阶记号（a=b）2020/1/19华南师范大学计算机学院275.渐近运算规则O(f(n))+O(g(n))=O(max{f(n),g(n)})；O(f(n))+O(g(n))=O(f(n)+g(n))；O(f(n))*O(g(n))=O(f(n)*g(n))；O(cf(n))=O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=O(f(n))。2020/1/19华南师范大学计算机学院281.8.2渐近表示的记号—O-记号定义１.2Ｐ１５设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个自然数n0，使得对于nn0，均f(n)cg(n),则称f(n)=O(g(n))。（充分性）如果f(n)/g(n)关于ｎ极限存在，那么就有f(n)=O(g(n))。2020/1/19华南师范大学计算机学院29１.8.3渐近表示的记号—•-记号设f(n)和g(n)均是从自然数集到非负实数集上的函数。如