算法分析基础ppt课件.ppt

第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 bottom-up merge sorting 2024/5/10 周五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 AlgorithmsChapter 1 Basic Concepts in Algorithmic Analysis 内容2024/5/10 周五3精品1.1 引言 Donald E.Knuth:计算机科学就是算法的研究.每个领域:依赖 有效算法设计运行时间:由例子到理论时间是衡量算法有效性的最好测度算法的几个方面：输入有限指令集输出 (存在?Y/N)2024/5/10 周五4精品算法概念算法是程序设计的精髓，程序设计的实质就是细化构造解决问题的算法，将其解释为计算机语言。算法算法是在有限有限步骤内求解某一问题所使用的一组定义明确的指令（规则）。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征：有穷性：有穷性：一个算法必须保证执行有限步之后结束；确切性：确切性：算法的每一步骤必须有确切的定义；输入：输入：一个算法有0个或多个输入，以刻画运算对象的初始情况；输出：输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；可行性：可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。2024/5/10 周五5精品 算法 几点说明 1.“算法”的 2.“算法”的现代诠释 3.学习“算法”的方法 几个词：Algorithm、Logarithm、Algorism 算法的现代意义十分类似于处方、过程、方法、规程、程序，一个算法就是有穷规则的集合一个算法就是有穷规则的集合。其中，规则规则规定了一个解决某一特定类型的问题的运算序列。一个算法应该是可以信赖的，而且学习一个算法直到彻底掌握的最好方法是反复进行试验。因此，遇到一个算法时，应该找出这个算法的一个例子，给出该例子的要点进行试验。2024/5/10 周五6精品程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性的性质。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。程序(Program)2024/5/10 周五7精品1.2 历史背景 20世纪,早期,30年代 能否用有效的过程来求解问题受到关注问题分类为:可解、不可解（存在有效过程来求解问题）计算模型：存在模型，用此模型能建立一求解某问题的算法，入可解的类模型列举：歌德尔的递归函数，Church的Lamda演算，Post的波斯特机，Turing机。Church论断：所有4个模型等效。如果一个问题在某一模型上可解，那么在其他模型上都是可解的。“几乎所有”问题都是不可解的。确定一个包含N个变量的多项式方程是否有整数解简单理由陈述：P3Top可判定性可计算性理论，可解性计算理论；有Digital Computer后，对可解问题的研究的要求越来越多。程序，资源量，尽可能少使用资源（时间，空间）的有效算法的需求。效率：指解决问题所需时间和空间排序一组元素的算法作为研究的实例表明：设计了许多有效算法，解决问题的效率将不会因其他方法而有大的提高。2024/5/10 周五8精品好的算法所具备的意义2024/5/10 周五9精品衡量算法性能的标准衡量算法性能一般有下面几个标准衡量算法性能一般有下面几个标准正确性易读性健壮性算法的时间和空间性能：高效率和低存储空间 我们这里主要讨论算法的时间和空间性能，并以此作为衡量算法性能的重要标准。而且我们主要侧重于时间方面。2024/5/10 周五10精品 算法的表达机制【表达算法的抽象机制表达算法的抽象机制】对于一个明确的数学问题，设计它的算法，总是先选用该问题的一个数学模型。接着，弄清该问题数学模型在已知条件下的初始状态和要求的结果状态，以及这两个状态之间的隐含关系。然后探索从数据模型的已知初始状态到达要求的结果状态所需的运算步骤。2024/5/10 周五11精品 算法的描述方法算法的描述方法自然语言；图表；框图；计算机语言或程序设计语言等。如，汇编、C+、Java。2024/5/10 周五12精品1.3 二分搜索二分搜索假定元素满足：线序集合1n 中有吗？从头到尾的扫描，比较次：顺序搜索顺序搜索适合无序的集合有序的集合：BinarySearch要求能够写出：这个简单的算法，并分析运算量。2024/5/10 周五13精品1.3-(例)线性查找的时间评估最小查找时间？最小查找时间？最好情况最好情况,A1=X,A1=X平均查找时间？平均查找时间？P(i)=1/n,TP(i)=1/n,Tavgavg(n)=n/2(n)=n/2最大查找时间？最坏情况最大查找时间？最坏情况,x,x 不在不在A1.nA1.n或或x=An,x=An,复杂度为复杂度为n n2024/5/10 周五14精品1.3 二分搜索及其时间复杂度 线性搜索二分搜索 同数据结构，略。但要求作为例子或问题求解。同数据结构，略。但要求作为例子或问题求解。及其算法分析及其算法分析2024/5/10 周五15精品比较次数分析中，次循环时剩余元素数目Floor(n/2j-1)循环停止条件：找到，或当前查找范围的数组长度为。最大搜索次数：满足Floor(n/2j-1)=1 时的值即：n/2j-1 2也即：2j-1n 2jj-1 log n j j=Floor(log n)+12024/5/10 周五16精品随堂练习设有序数组：试搜索x=20,以及 X=22.1）拟用什么法？为什么？2）试给出用你想要得算法求解的过程。参考：教材binarySearch Example 1.12024/5/10 周五17精品二分查找的基本运算量分析？2024/5/10 周五18精品1.10 最优算法定义：排序问题中的2024/5/10 周五19精品 1.11-14.算法分析(Algorithm Analysis)算算法法分分析析：对于算法的时间和空间复杂度进行定量分析。分析算法时间复杂度的基本步骤元运算考察可以做基本运算的有那些，选基本运算基本运算的总量评估借助数学公式，比如循环嵌套就是乘法原理，递归调用对应递归公式等求解2024/5/10 周五20精品简例估计算法运行时间算法时间复杂度的有关概念：，平均分析、求解算法复杂度的基本方法设计计算过程如下：（为讨论方便，每行前加一行号）(1)for i:=1 to n(2)for j:=1 to n(3)x:=x+1.试问在程序运行中各步执行的次数各为多少？上例中的赋值操作基本运算时间复杂性可粗略地表示为f(n)=O(n2)。要更多地了解关于算法的复杂性，就必须弄清楚如下两个问题：(1)用怎样的一个量来表达一个算法的复杂性；(2)对于给定的一个算法，怎样具体计算它的复杂性。2024/5/10 周五21精品分析时间复杂度的基本步骤分析时间复杂度的基本步骤一、选取一种选取一种元运算元运算作为作为基本运算基本运算二、表示出在算法运行期间二、表示出在算法运行期间基本运算基本运算执行的总频数执行的总频数三、渐近时间复杂度（三、渐近时间复杂度（asymptotic time complexity）2024/5/10 周五22精品思考与练习思考与练习：指出下面程序段中语句标*的频度和该程序段的时间复杂性。(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:=1;while(i0和一个自然数n0，使得 对于n n0，均 f(n)cg(n),则称 f(n)=O(g(n)。（充分性）如果 f(n)/g(n)关于极限存在，那么就有f(n)=O(g(n)。2024/5/10 周五28精品.8.3.8.3渐近表示的记号渐近表示的记号 -记号记号 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在常数c0和一个自然数n0，使得对于任意的n n0，均有 f(n)cg(n),则 f(n)=(g(n)。2024/5/10 周五29精品1.8.4 1.8.4 渐近表示的记号渐近表示的记号 -记号记号 设f(n)和g(n)均是从自然数集到非负实数集上的函数。如果存在一个自然数n0和两个正常数c1，c2，使得对于任意的n n0，均有 c1g(n)f(n)c2 g(n),则 f(n)=(g(n)。2024/5/10 周五30精品1.8.6 复杂性类与o符号，定义.5无穷小 o注意，用表示f(n)是g(n)的无穷小关系，教材页复杂性类的层次。2024/5/10 周五31精品o 关系 趋于无穷大时，趋于无穷大时，0)。则有f(n)=O(nk)f(n)=(nk)：f(n)=(nk)由此可见，复杂度的渐近表示可以简洁地表示出复杂度的数量级别。渐近表示渐近表示 Examples Examples2024/5/10 周五33精品 1.8-9.算法的时间和空间复杂度时间复杂度时间复杂度（Time Complexity）算法运行期间所花费的时间。通常用渐进形式表示比如，T(n)=(n2)、(n2)或 (n2)空间复杂度空间复杂度（Space Complexity）在算法运行期间所需要的内存空间。一般指，容纳输入数据之外的附加空间（auxiliary space,or work space）。通常用渐进形式表示比如，S(n)=(n2)、(n2)或(n2)2024/5/10 周五34精品1.5-.6.算法时间复杂度的例子例例1 检索问题的顺序查找算法检索问题的顺序查找算法 以元素的比较作为基本操作。考虑成功检索的情况。最好情况下的时间复杂度：(1)最坏情况下的时间复杂度：(n)在等概率前提下，平均情况下的时间复杂度：(n)例例2 直接插入排序算法直接插入排序算法 以元素的比较作为基本操作。最好情况下的时间复杂度：(n)最坏情况下的时间复杂度：(n2)在等概率前提下，平均情况下的时间复杂度：(n2)2024/5/10 周五35精品1.7（例）合并两个已排序的表归并排序算法基本思想（合并两个有序表为基础，把最初的输入两两排序，逐渐合并为完整的有序表）简单的以个数的情形做例子9,4,5,2,1,7,4,6由小到大，考虑的对象按层计数如页图考虑的对象按层计数如页图1.4算法：BOTTOMUPSORT元素赋值次数为2n p9P11,分析2024/5/10 周五36精品算法2024/5/10 周五37精品2024/5/10 周五38精品基本思想3个数组Apq,Aq+1r,Bpr3个指针：s,t,ks初始化时各自指向Apt初始化时各自指向Aq+1k初始化时各自指向Bp,暂存器。比较As,At,小的值存入Bk小的指针1，形成新比较对，存入k1某组已到尾部，将另一组尚未比较的复制到BB回写到A2024/5/10 周五39精品例子选择排序 1.5基本思想算法：SelectionSort观察：比较次数：n（n1）/2,赋值次数界于0与3（n1）之间。2024/5/10 周五40精品例子插入排序1.6基本思想算法：InsertionSort比较次数：n（n1）/2赋值次数：比较次数加n12024/5/10 周五41精品强调例子1.7自底向上合并排序 图示，基本思想，P9BottomUpSort实例：性能分析：P112024/5/10 周五42精品1.8 时间复杂性 阶的增长衡量:P12,近似时间。比较，界限近似时间，相对于同一/不同问题的算法，估计时间相对性独立于机器，独立于不同语言技术上的进步，不影响算法的时间测度方法成立基本运算支撑的大规模输入实例。P13图1.5：表示运行时间的典型函数的增长情况P14 表1.1：不同大小输入的时间量级运行时间比较元运算：元运算：对任何计算步骤，其代价总是一个时间常量为上对任何计算步骤，其代价总是一个时间常量为上界，而不管输入数据或执行的算法，总称这样的计算步骤界，而不管输入数据或执行的算法，总称这样的计算步骤为元运算，为元运算，（基本操作）算术运算：，算术运算：，/比较和逻辑运算比较和逻辑运算赋值运算，包括遍历表或树的指针赋值赋值运算，包括遍历表或树的指针赋值 2024/5/10 周五43精品2024/5/10 周五44精品1.8 时间复杂性2 表示BigO，定义1.2：f(n),g(n)从自然数集合到非负实数集合的两个函数，如果存在一个自然数n0和c0,使得 n=n0,f(n)0,使得 n=n0,c1g(n)=f(n)=c2g(n)则称f（n）为(g(n)。由极限理论，存在，则 其不发散到无穷，蕴涵 f（n）(g(n)。SELECTIONSORT,(n2）BOTTOMUPSORT,(n log n）2024/5/10 周五47精品讨论：P17 Top Paragraph 2024/5/10 周五48精品预习归纳法贪婪法 动态规划法 分治法的定义复习：求和公式（，.，），递归方程求解 2024/5/10 周五49精品1.9 空间复杂性S(n)space。T(n)time complexity在上述意义下：S(n)可以对应T(n)求法例1.171.21 Page:20时间与空间的依存：权衡。时间，空间的反比关系。矛盾，兑换一增一减存在限度。2024/5/10 周五50精品1.10 最优算法阅读，品一品两段 排序算法中最优的是？最优算法的定义是？2024/5/10 周五51精品1.11 如何估计算法运行时间 P21 运行时间常常和循环及类似结构的执行次数成正比。比如：搜索，排序，矩阵例.22 Count1例.23 Count2例.24 Count3例.25 PSUMP23 计算基本运算的频度：选个频度最高或常数倍的元运算作为评估时间的基本运算P26 使用递推关系，如T(n)=2T(n/2)+n2024/5/10 周五52精品1.12 最坏情况和平均情况的分析Theta 不是总可以达到例1.29平均情况，必须知道输入出现的概率复杂冗长 例1.30,1.31 2024/5/10 周五53精品1.13 平摊分析情形：算法中有一种运算反复执行时，其运行时间不停变动。该运算大多数时候运行快，少数情况下费时，同时假定求确界可能，但困难，引入平摊分析平摊分析中，算出算法在整个执行中所需时间的平均值。称该运算的平摊运行时间。2024/5/10 周五54精品例1.32 注意到页的第段的分析段的分析2024/5/10 周五55精品1.14 输人大小和问题实例算法性能的测度通常是它算法性能的测度通常是它输入的大小输入的大小、顺、顺序、分布等的函数。序、分布等的函数。常用常用输入大小输入大小的测度：，个情的测度：，个情形形 排序，搜索问题：数组或表中元素的数目排序，搜索问题：数组或表中元素的数目图的算法中：图中的边或顶点数目，或二者一起图的算法中：图中的边或顶点数目，或二者一起矩阵中：输入矩阵的维数矩阵中：输入矩阵的维数计算几何中计算几何中数论和密码学中数论和密码学中 2024/5/10 周五56精品 算法分析的数学准备1.单调函数单调递增：m n f(m)f(n);单调递减：m n f(m)f(n);严格单调递增：m n f(m)f(n);严格单调递减：m f(n).2.取整函数 x ：不大于x的最大整数；x ：不小于x的最小整数。2024/5/10 周五57精品取整函数的若干性质：x-1 x x x 0，有：n/a /b =n/ab ;n/a /b =n/ab ;a/b (a+(b-1)/b;a/b (a-(b-1)/b;f(x)=x ,g(x)=x 为单调递增函数。2024/5/10 周五58精品3.多项式函数p(n)=a0+a1n+a2n2+adnd；ad0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;k d p(n)=O(nk);k d p(n)=(nk);k d p(n)=o(nk);k 0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman =am+n;a1 an为单调递增函数;a1 nb=o(an)ex 1+x;|x|1 1+x ex 1+x+x2;ex=1+x+(x2),as x0;2024/5/10 周五60精品5.对数函数 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)kl;log log n=log(log n);for a0,b0,c02024/5/10 周五61精品2024/5/10 周五62精品|x|1 for x -1,for any a 0,logbn=o(na)6.阶乘函数2024/5/10 周五63精品2024/5/10 周五64精品小规模数据小规模数据2024/5/10 周五65精品中等规模数据中等规模数据2024/5/10 周五66精品随堂练习、要点及作业 p32.随堂练习1.10 例子.16 2.171.131.15(C).2024/5/10 周五67精品（秋）Exercise1.131.281.312024/5/10 周五68精品（秋）准备一个提交本，一个课堂练习本，充分利用书的空白Exercise 1.15 练习 p321.1 a,b,c in class1.2 a,b,c 1.3 a,b1.41.6(In class)1.7 1.10(in class)1.111.13(in class)1.14 a,c 1.15 b,d in class1.161.33 复习阶段自习题1.341.352024/5/10 周五69精品数学预备知识自学由于内容和以前的专业基础重复，相信大家具备基础如有不足，你怎么办呢？2024/5/10 周五70精品