算法设计技巧与分析课件

第1章算法分析基本概念路游[e-mail]《算法设计技巧与分析》与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同的设计技术的适用性和效率。考虑问题的高度：数据结构关心的是具体问题，算法不仅于此，它提供一种解决问题的通用方法。RelationswithOtherCourses高级程序设计语言（C,C++）数据结构算法设计与分析数据库系统，编译方法，操作系统…Whatwillwelearn?•算法分析基本概念（Foundation）•算法设计技术–归纳法（Divide）–分治（Conquer）–动态规划（DynamicProgramming）–贪心法（GreedyAlgorithm）–回溯法（BackTracking）•问题的复杂性（ProblemComplexity）Whatcoursesshouldbelearnedpreviously?•离散数学（DiscreteMathematics）•数据结构（DataStructures）•高级程序设计语言（High-levelProgrammingLanguage）教材：•算法设计技巧与分析•AlgorithmsDesignTechniquesandAnalysis•【沙特】M.H.Alsuwaiyel•吴伟昶方世昌等译•朱洪审校•电子工业出版社2004年8月参考书：•算法设计与分析基础•【美】AnanyLevitin著•潘彦译•清华大学出版社2006年6月CourseplanandTest•课时：32•安排：32学时讲授+课后习题•考核出勤+习题30％考试70％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/20华南师范大学计算机学院8•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/20华南师范大学计算机学院9Chapter1BasicConceptsinAlgorithmicAnalysis内容2020/1/20华南师范大学计算机学院101.1引言DonaldE.Knuth:计算机科学就是算法的研究.每个领域:依赖有效算法设计运行时间:由例子到理论时间是衡量算法有效性的最好测度算法的几个方面：输入有限指令集输出(存在?Y/N)2020/1/20华南师范大学计算机学院11算法概念算法是程序设计的精髓，程序设计的实质就是细化构造解决问题的算法，将其解释为计算机语言。算法是在有限步骤内求解某一问题所使用的一组定义明确的指令（规则）。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。2020/1/20华南师范大学计算机学院12算法几点说明1.“算法”的2.“算法”的现代诠释3.学习“算法”的方法几个词：Algorithm、Logarithm、Algorism算法的现代意义十分类似于处方、过程、方法、规程、程序，一个算法就是有穷规则的集合。其中，规则规定了一个解决某一特定类型的问题的运算序列。一个算法应该是可以信赖的，而且学习一个算法直到彻底掌握的最好方法是反复进行试验。因此，遇到一个算法时，应该找出这个算法的一个例子，给出该例子的要点进行试验。2020/1/20华南师范大学计算机学院13•程序是算法用某种程序设计语言的具体实现。•程序可以不满足算法的有限性的性质。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。•操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。程序(Program)2020/1/20华南师范大学计算机学院141.2历史背景20世纪,早期,30年代能否用有效的过程来求解问题受到关注问题分类为:可解、不可解（存在有效过程来求解问题）计算模型：存在模型，用此模型能建立一求解某问题的算法，－－入－－可解的类模型列举：歌德尔的递归函数，Church的Lamda演算，Post的波斯特机，Turing机。Church论断：所有4个模型等效。如果一个问题在某一模型上可解，那么在其他模型上都是可解的。＝“几乎所有”问题都是不可解的。确定一个包含N个变量的多项式方程是否有整数解简单理由陈述：P3Top可判定性－〉可计算性理论，可解性－〉计算理论；有DigitalComputer后，对可解问题的研究的要求越来越多。程序，资源量，尽可能少使用资源（时间，空间）的有效算法的需求。效率：指解决问题所需时间和空间排序一组元素的算法作为研究的实例表明：设计了许多有效算法，解决问题的效率将不会因其他方法而有大的提高。2020/1/20华南师范大学计算机学院15好的算法所具备的意义2020/1/20华南师范大学计算机学院16衡量算法性能的标准•衡量算法性能一般有下面几个标准–正确性–易读性–健壮性–算法的时间和空间性能：高效率和低存储空间我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。2020/1/20华南师范大学计算机学院17算法的表达机制【表达算法的抽象机制】对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数学模型。接着，弄清该问题数学模型在已知条件下的初始状态和要求的结果状态，以及这两个状态之间的隐含关系。然后探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。2020/1/20华南师范大学计算机学院18算法的描述方法自然语言；图表；框图；计算机语言或程序设计语言等。如，汇编、C++、Java。1.3二分搜索•假定元素满足：线序集合•Ａ[1…n]中有ｘ吗？•从头到尾的扫描，比较ｎ次：顺序搜索•顺序搜索适合无序的集合•有序的集合：BinarySearchＰ４•要求能够写出：这个简单的算法，并分析运算量。2020/1/20华南师范大学计算机学院192020/1/20华南师范大学计算机学院201.3-(例)线性查找的时间评估最小查找时间？最好情况,A[1]=X平均查找时间？P(i)=1/n,Tavg(n)=n/2最大查找时间？最坏情况,x不在A[1...n]或x=A[n],复杂度为n2020/1/20华南师范大学计算机学院211.3二分搜索及其时间复杂度•线性搜索•二分搜索同数据结构，略。但要求作为例子或问题求解。及其算法分析比较次数分析•Ｗｈｉｌｅ中，ｊ次循环时剩余元素数目Floor(n/2j-1)•循环停止条件：找到ｘ，或当前查找范围的数组长度为１。•最大搜索次数：满足Floor(n/2j-1)=1时的ｊ值–即：１n/2j-12–也即：2j-1n2j–j-1lognjj=Floor(logn)+12020/1/20华南师范大学计算机学院222020/1/20华南师范大学计算机学院23随堂练习设有序数组：试搜索x=20,以及X=22.1）拟用什么法？为什么？2）试给出用你想要得算法求解的过程。参考：教材binarySearchExample1.12020/1/20华南师范大学计算机学院24二分查找的基本运算量分析？1.4合并两个已排序的表•两个数组A[1…q],B[q+1…r]已是有序，不妨升序•下面的算法将这两个合并为一个有序数组•观察1.1：Merge将n1和n2大小的两个数组合并成一个n＝n1+n2的数组，(n1≤n2)元素的比较次数为n1到n－1之间。特例：如果两个数组的大小为Floor(n/2)和Ceiling(n/2),需要比较的次数在Floor(n/2)到n－1之间。2020/1/20华南师范大学计算机学院252020/1/20华南师范大学计算机学院26基本思想•3个数组•A[p…q],A[q+1…r],B[p…r]•3个指针：s,t,k–s初始化时各自指向A[p]–t初始化时各自指向A[q+1]–k初始化时各自指向B[p],暂存器。–比较A[s],A[t],小的值存入B[k]–小的指针＋1，形成新比较对，存入k＋1–某组已到尾部，将另一组尚未比较的复制到B–B回写到AＭｅｒｇｅ算法2020/1/20华南师范大学计算机学院27观察结论1.2•使用算法Merge将两个数组合并为一个大小为n的有序数组，元素赋值的次数恰好是2n2020/1/20华南师范大学计算机学院282020/1/20华南师范大学计算机学院29例子－－选择排序1.5•基本思想•算法：SelectionSort•观察：比较次数：n（n－1）/2,赋值次数界于0与3（n－1）之间。算法1.4选择selectionsort，算法1.5插入排序insertionsort•算法1.4比较次数，(n－1)+…+1的连续和•复制次数：0到3（n－1）•算法1.5：比较次数n－1到n(n-1)/2之间。元素赋值次数为比较次数加上n－1.2020/1/20华南师范大学计算机学院302020/1/20华南师范大学计算机学院311.5-1.6.选择排序P7，插入排序P8算法时间复杂度的例子•[例1]检索问题的顺序查找算法以元素的比较作为基本操作。考虑成功检索的情况。–最好情况下的时间复杂度：(1)–最坏情况下的时间复杂度：(n)–在等概率前提下，平均情况下的时间复杂度：(n)•[例2]直接插入排序算法以元素的比较作为基本操作。–最好情况下的时间复杂度：(n)–最坏情况下的时间复杂度：(n2)–在等概率前提下，平均情况下的时间复杂度：(n2)2020/1/20华南师范大学计算机学院321.7自底向上合并排序•归并排序–算法基本思想（合并两个有序表ＭＥＲＧＥ为基础，把最初的输入两两排序，逐渐合并为完整的有序表）–简单的以８个数的情形做例子{9,4,5,2,1,7,4,6}由小到大，•考虑的对象按层计数如１１页图1.4–算法：BOTTOMUPSORT–元素赋值次数为2np9–P11,分析2020/1/20华南师范大学计算机学院33Ｐｒｏｏｆ2020/1/20华南师范大学计算机学院34例子－－插入排序1.6•基本思想•算法：InsertionSort•比较次数：n（n－1）/2•赋值次数：比较次数加n－12020/1/20华南师范大学计算机学院35强调例子－－1.7自底向上合并排序•图示，•基本思想，P9•BottomUpSort•实例：•性能分析：P112020/1/20华南师范大学计算机学院361.8时间复杂性－阶的增长•衡量:P12,近似时间。比较，界限–近似时间，相对于同一/不同问题的算法，估计时间相对性–独立于机器，独立于不同语言–技术上的进步，不影响算法的时间测度方法成立–基本运算支撑的大规模输入实例。–P13