算法分析基础

《算法分析基础》由会员分享，可在线阅读，更多相关《算法分析基础（70页珍藏版）》请在金锄头文库上搜索。

1、第1章 算法分析基本概念,曹霑懋 ,算法设计技巧与分析,Chapter 1 Basic Concepts in Algorithmic Analysis 内容,1.1 Introduction l.2 Historical Background 1.3 Binary Search 1.3.1 Analysis of the binary search algorithm 1.4 Merging Two Sorted Lists 1.5 Selectinn Sort 1.6 Insertion Sort 1.7 Bottom-Up Merge Sorting 1.7.1 Analysis of

2、bottom-up merge sorting,2019/2/18,华南师范大学 计算机学院,2,1.8 Time Complexity 1.8.1 Order of growth 1.8.2 The O-notation 1.8.3 The fl-notation l.8.4 The e-notation 1.8.5 MamPles 1.8.6 Complekity classes and the o-notation 1.9 Space Complexity 1.10 Optimal Algorithms,2019/2/18,华南师范大学 计算机学院,3,Chapter 1 Basic C

3、oncepts in Algorithmic Analysis 内容,2019/2/18,华南师范大学 计算机学院,4,1. 1 引言,Donald E. Knuth: 计算机科学就是算法的研究. 每个领域: 依赖 有效算法设计 运行时间: 由例子到理论 时间是衡量算法有效性的最好测度 算法的几个方面： 输入 有限指令集 输出 (存在? Y/N),2019/2/18,华南师范大学 计算机学院,5,算法概念,算法是程序设计的精髓，程序设计的实质就是细化构造解决问题的算法，将其解释为计算机语言。 算法是在有限步骤内求解某一问题所使用的一组定义明确的指令（规则）。通俗点说，就是计算机解题的过程。在这

4、个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下五个重要的特征： 有穷性： 一个算法必须保证执行有限步之后结束； 确切性： 算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。,2019/2/18,华南师范大学 计算机学院,6,算法 几点说明,1. “算法”的,2. “算法”的现代诠释,3. 学习“算法”的方

5、法,几个词：Algorithm、Logarithm、Algorism,算法的现代意义十分类似于处方、过程、方法、规程、程序，一个算法就是有穷规则的集合。其中，规则规定了一个解决某一特定类型的问题的运算序列。,一个算法应该是可以信赖的，而且学习一个算法直到彻底掌握的最好方法是反复进行试验。 因此，遇到一个算法时，应该找出这个算法的一个例子，给出该例子的要点进行试验。,2019/2/18,华南师范大学 计算机学院,7,程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的有限性的性质。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一

6、个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,程序(Program),2019/2/18,华南师范大学 计算机学院,8,1.2 历史背景,20世纪,早期, 30年代 能否用有效的过程来求解问题受到关注 问题分类为:可解、不可解（存在有效过程来求解问题） 计算模型：存在模型，用此模型能建立一求解某问题的算法，入可解的类 模型列举：歌德尔的递归函数，Church的Lamda演算，Post的波斯特机，Turing机。 Church论断：所有4个模型等效。如果一个问题在某一模型上可解，那么在其他模型上都是可解的。“几乎所有”问题都是不可解的。 确定一个包含N个变量

7、的多项式方程是否有整数解 简单理由陈述：P3Top 可判定性可计算性理论， 可解性计算理论； 有Digital Computer后，对可解问题的研究的要求越来越多。 程序，资源量，尽可能少使用资源（时间，空间）的有效算法的需求。 效率：指解决问题所需时间和空间 排序一组元素的算法作为研究的实例表明：设计了许多有效算法，解决问题的效率将不会因其他方法而有大的提高。,2019/2/18,华南师范大学 计算机学院,9,好的算法所具备的意义,2019/2/18,华南师范大学 计算机学院,10,衡量算法性能的标准,衡量算法性能一般有下面几个标准 正确性 易读性 健壮性 算法的时间和空间性能：高效率和低存

8、储空间 我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。,2019/2/18,华南师范大学 计算机学院,11,算法的表达机制,【表达算法的抽象机制】对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数学模型。 接着，弄清该问题数学模型在已知条件下的初始状态和要求的结果状态，以及这两个状态之间的隐含关系。 然后探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。,2019/2/18,华南师范大学 计算机学院,12,算法的描述方法,自然语言； 图表； 框图； 计算机语言或程序设计语言等。 如，汇编、C+、Java。,1.3 二

9、分搜索,假定元素满足：线序集合 1n 中有吗？ 从头到尾的扫描，比较次： 顺序搜索 顺序搜索适合无序的集合 有序的集合：BinarySearch 要求能够写出：这个简单的算法，并分析运算量。,2019/2/18,华南师范大学 计算机学院,13,2019/2/18,华南师范大学 计算机学院,14,1.3- (例) 线性查找的时间评估,最小查找时间？ 最好情况, A1=X 平均查找时间？P(i)=1/n, Tavg(n)=n/2 最大查找时间？最坏情况, x 不在A1.n或x=An, 复杂度为n,2019/2/18,华南师范大学 计算机学院,15,1. 3 二分搜索及其时间复杂度,线性搜索 二分搜

10、索 同数据结构，略。但要求作为例子或问题求解。,及其算法分析,比较次数分析,中，次循环时剩余元素数目Floor(n/2j-1) 循环停止条件：找到，或 当前查找范围的数组长度为。 最大搜索次数：满足Floor(n/2j-1)=1 时的值 即：n/2j-1 2 也即： 2j-1n 2j j-1 log n j j=Floor(log n)+1,2019/2/18,华南师范大学 计算机学院,16,2019/2/18,华南师范大学 计算机学院,17,随堂练习,设 有序数组：,试搜索x=20, 以及 X =22. 1）拟用什么法？为什么？ 2）试给出用你想要得算法求解的过程。,参考：教材binaryS

11、earch Example 1.1,2019/2/18,华南师范大学 计算机学院,18,二分查找的基本运算量分析,？,1.10 最优算法,定义： 排序问题中的 ,2019/2/18,华南师范大学 计算机学院,19,2019/2/18,华南师范大学 计算机学院,20,1.11-14. 算法分析(Algorithm Analysis),算法分析：对于算法的时间和空间复杂度进行定量分析。 分析算法时间复杂度的基本步骤 元运算考察 可以做基本运算的有那些，选基本运算 基本运算的总量评估 借助数学公式，比如循环嵌套就是乘法原理，递归调用对应递归公式等 求解,2019/2/18,华南师范大学 计算机学院,

12、21,简例估计算法运行时间,算法时间复杂度的有关概念：，平均 分析、求解算法复杂度的基本方法 设计计算过程如下： （为讨论方便，每行前加一行号） (1) for i:=1 to n (2) for j:=1 to n (3) x:=x+1 试问在程序运行中各步执行的次数各为多少？ 上例中的赋值操作 基本运算 时间复杂性可粗略地表示为f(n)=O(n2)。 要更多地了解关于算法的复杂性，就必须弄清楚如下两个问题：(1)用怎样的一个量来表达一个算法的复杂性； (2)对于给定的一个算法，怎样具体计算它的复杂性。,2019/2/18,华南师范大学 计算机学院,22,分析时间复杂度的基本步骤,一、选取一

13、种元运算作为基本运算 二、表示出在算法运行期间基本运算执行的总频数 三、渐近时间复杂度（asymptotic time complexity）,2019/2/18,华南师范大学 计算机学院,23,思考与练习：指出下面程序段中语句标*的频度和该程序段的时间复杂性。,(1)* y:=sin(x); (2) for i:=1 to n-1 do * y:=y+1; for j:=0 to 2*n do * x:=x+1; (3) x:=1;y:=1; for k:=1 to n do * x:=x+1; for i:=1 to n do for j:=1 to n do *y:=y+1; (4) i

14、:=1; while (in if Ai=x then retun(i) 可否改造（4）？,2019/2/18,华南师范大学 计算机学院,24,算法复杂性,算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。 计算机的资源，最重要的是时间和空间（即存储器）资源。 因而，算法的复杂性有时间复杂性和空间复杂性之分。 对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标； 另一方面，当给定的问题已有多种算法时，选

15、择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。 算法的复杂性分析的意义：对算法的设计或选用有着重要的指导意义和实用价值。 对算法的分析，以确定或判断算法的优劣，通常以时间复杂性来衡量，时间复杂性越低，对应的算法就越优。,2019/2/18,华南师范大学 计算机学院,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出现的概率。,2019/2/18,华南师范大学 计算机学院,26,3.算法渐近复杂性 T(n) , as n; (T(n) - t(n) )/ T(n) 0 ，as n