计算机算法设计与分析第1章算法概述.ppt

四川师范大学 计算机科学学院 刘芳,计算机算法设计与分析 Design and Analysis of Computer Algorithm,刘 芳四川师范大学计算机学院邮箱：电话：,四川师范大学 计算机科学学院 刘芳 2,课程基本情况,课程性质：学科专业主干课程（计算机科学与技术专业）专业拓展应用提高课程（软件工程专业）学时与学分48理论学时（3学分）32实验学时（1学分）考核方式平时成绩:30%期末成绩:70%,四川师范大学 计算机科学学院 刘芳 3,参考书籍,算法分析与设计，美Michael T.Goodrich Roberto Tamassia 著，人民邮电出版社计算机算法基础，余祥宣等著，华中科技大学出版社计算机算法导引设计与分析：卢开澄编著，清华大学出版社计算机算法设计与分析，苏德富著，电子工业出版社计算机算法设计与分析导论（第三版 影印版），S.Baase and，高等教育出版社,四川师范大学 计算机科学学院 刘芳 4,课程的学习目的与任务,目的与任务：本课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度。知道计算机领域中解决不同问题的一系列标准算法；具备设计新算法和分析其效率的能力，锻炼逻辑思维能力和想象力，并了解算法理论的发展。运用算法知识解决各自学科的实际问题，培养独立科研的能力和理论联系实践的能力。,四川师范大学 计算机科学学院 刘芳 5,第1章 算法概述,学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。,四川师范大学 计算机科学学院 刘芳 6,第1章 算法概述,1.1 算法1.1.1 问题求解的基本流程1.1.2 什么是算法1.1.3 算法和程序1.1.4 算法设计方法1.1.5 算法分析方法1.2 算法复杂性分析1.2.1 算法的复杂性分析1.2.2 算法复杂性的渐近分析,四川师范大学 计算机科学学院 刘芳 7,问题求解的基本流程,问题求解(Problem Solving),四川师范大学 计算机科学学院 刘芳 8,1.1.2 什么是算法,算法算法是一系列解决问题的清晰的指令，对符合一定规范的输入，在有限时间内获得所要求的输出。基本特征：确定性/有穷性/可行性/输入/输出其他属性：健壮性/可读性经济性,四川师范大学 计算机科学学院 刘芳 9,算法和程序,算法的重要性：程序算法数据结构 计算机语言和开发工具只是编程的工具，掌握工具固然重要，但更重要的是掌握方法！开发工具会不断地更新，新的计算机语言会不断地出现，今天学会的东西可能明天就会过时；但基本的算法却不会有太大改变。掌握了程序设计的算法，无论再学习何种语言和开发工具都可以很快地上手。资料阅读,四川师范大学 计算机科学学院 刘芳 10,1.1.3 算法和程序,几个观点：程序设计算法不是数学概念中的狭隘算法，而是计算机领域中对问题的思考方式及解决步骤，是一种思路和逻辑性的体现。很多算法已经被包含到了语言和工具中，还有必要学习算法吗？,四川师范大学 计算机科学学院 刘芳 11,1.1.3 算法和程序,程序程序是算法用某种程序设计语言的具体实现。算法与程序算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性程序中可以包含死循环；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。,四川师范大学 计算机科学学院 刘芳 12,1.1.4 算法设计方法,常见的算法设计方法分治法动态规划法贪心法回溯法分支限界法线性规划与网络流,四川师范大学 计算机科学学院 刘芳 13,1.1.5 算法分析方法,算法的“好”与“不好”正确性时间效率空间效率是否存在更好的算法下界最优,四川师范大学 计算机科学学院 刘芳 14,1.1.6 算法分析方法,分析方法1：实验分析过程：输入样本的准备插入一些计数器计算基本操作的执行次数记录程序的运行时间计算机时钟精度小的问题将是0分时系统时间包括其他开销,四川师范大学 计算机科学学院 刘芳 15,1.1.6 算法分析方法,分析方法1：实验分析局限性实验只能在有限的测试输入集上进行；相同的硬件和软件环境下执行两个算法的运行时间的实验，否则难以比较两个算法的效率；需要实现并执行一个算法，才能以实验的方式研究它的运行时间。,四川师范大学 计算机科学学院 刘芳 16,1.1.6 算法分析方法,分析方法2：理论（数学）分析（优势）可以考虑所有可能的输入；允许独立于软硬件环境来评估任意两个算法的相对效率；无需真正实现算法和执行算法，通过研究算法的高级描述就能进行算法分析。其目标是：将每个算法与一个函数f(n)关联起来，而f(n)能够根据输入大小n表征算法的运行时间。,四川师范大学 计算机科学学院 刘芳 17,1.1.6 算法分析方法,分析方法2：理论（数学）分析（劣势）数学分析是不够的可能数学上无法分析求解特别是平均性能的分析,四川师范大学 计算机科学学院 刘芳 18,1.2 算法复杂性分析,算法复杂性 算法所需要的计算机资源算法的时间复杂性算法的空间复杂性注意：对算法的分析，必须脱离具体的计算机结构和程序设计语言。关于算法的复杂性，有两个问题要弄清楚：用怎样的一个量来表达一个算法的复杂性；对于给定的一个算法，怎样具体计算它的复杂性。,四川师范大学 计算机科学学院 刘芳 19,1.2算法复杂性的分析,算法的复杂性 C=F(N,I,A),时间复杂性T=T(N,I,A)或T=T(N,I),空间复杂性S=S(N,I,A)或S=S(N,I),N:问题的规模 I:输入数据 A:算法本身,四川师范大学 计算机科学学院 刘芳 20,1.2.1 算法时间复杂性的分析,1.将时间复杂性函数T（N，I）具体化设一台抽象计算机提供的元运算有k种,分别记作：O1,2,Ok，而这些元运算每执行一次所需时间分别为t1,t2,tk,设算法A中用到Oi的次数为 ei,i=1,k,则 ei=ei(N,I)则：,四川师范大学 计算机科学学院 刘芳 21,1.2.1 算法复杂性的分析,2.三种情况下的时间复杂性,四川师范大学 计算机科学学院 刘芳 22,1.2.1 算法复杂性的分析,四川师范大学 计算机科学学院 刘芳 23,例如：,最坏情况时间,最好情况时间,平均情况时间？,6ms,四川师范大学 计算机科学学院 刘芳 24,1.2.1 算法复杂性的分析,一般来说最好情况的时间复杂性对于问题的任意确定的规模N达到了Tmin(N)的合法输入难以确定平均情况的时间复杂性规模 N 的每一个输入的概率也难以预测或确定。我们有时也按平均情况计量时间复杂性，但那是在对P(I)做了一些人为的假设（比如等概率）之后才进行的，所做的假设是否符合实际总是缺乏根据。,四川师范大学 计算机科学学院 刘芳 25,因此在最好情况和平均情况下的时间复杂性分析还仅仅是停留在理论上。实践表明：可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。,四川师范大学 计算机科学学院 刘芳 26,例1：查找算法的时间复杂性分析,问题：已知不重复且已经按从小到大排好的m个整数的数组A1.m（为简单起见，设m=2 k，k是一个确定的非负整数）。对于给定的整数c，要求寻找一个下标j，使得A j=c；若找不到，则返回1。,四川师范大学 计算机科学学院 刘芳 27,顺序查找算法的时间复杂性分析,算法1-1：（顺序查找）int search_sq(int Am+1,int c)int j,result;j=1;while(jm,分析:问题的规模为m,设元运算及执行时间为：赋值:a判断:t加法:s 并设c在A中（即c为合法输入）,四川师范大学 计算机科学学院 刘芳 28,顺序查找算法的时间复杂性分析,最好情况int search_sq(int Am+1,int c)int j,result;j=1;a while(jm,最好情况：int search_sq(int Am+1,int c)int j,result;j=1;while(jm,因此：最好情况Tmin(m)=2a+3t,四川师范大学 计算机科学学院 刘芳 29,顺序查找算法的时间复杂性分析,最坏情况int search_sq(int Am+1,int c)int j,result;j=1;a while(jm,最坏情况：int search_sq(int Am+1,int c)int j,result;j=1;while(jm,因此：最坏情况Tmax(m)=（m+1)a+(2m+1)t+(m-1)s,四川师范大学 计算机科学学院 刘芳 30,顺序查找算法的时间复杂性分析,平均情况至于Tavg(m)，必须对Dm上的概率分布做出假设才能计量。为简单起见，做最简单的假设：Dm上的概率分布是均等的，即 P(i)=1/m。则：,四川师范大学 计算机科学学院 刘芳 31,顺序查找算法的时间复杂性分析,平均情况第i个合法输入int search_sq(int Am+1,int c)int j,result;j=1;a while(jm,四川师范大学 计算机科学学院 刘芳 32,顺序查找算法的时间复杂性分析,平均情况,由于：,而且:,四川师范大学 计算机科学学院 刘芳 33,二分查找算法的时间复杂性分析,算法1-2：二分查找算法。int B_Search(int Am+1,int c)int Low,mid,high;bool found;low=1,high=m;found=false;while(!found,四川师范大学 计算机科学学院 刘芳 34,1.2.1 算法复杂性的分析,分析:问题规模为m元运算执行时间设为:赋值a,判断t,加/减法s,除法d容易理解：在最坏的情况下最多只要测A中的 logm+1(这里的log以2为底，下同)个分量，就可以判断c是否在A中。,四川师范大学 计算机科学学院 刘芳 35,1.2.1 算法复杂性的分析,算法1-2：二分查找算法。Int B_Search(int Am+1,int c)int Low,mid,high;bool found;low=1,high=m;found=false;3a while(!found,因此：最坏情况Tmax(m)=7a+5t+2s+d+(2a+2s+4t+d)logm,四川师范大学 计算机科学学院 刘芳 36,1.2.2 算法复杂性的渐近性态,1.渐近时间复杂性设T(n)为算法A的时间复杂性函数，则它是n的单增函数,如果存在一个函数,称 是T(n)当 n 时的渐近性态或 渐近时间复杂性。,使得当n,有,四川师范大学 计算机科学学院 刘芳 37,在数学上T(n)与 有相同的最高阶项，可取 为略去T(n)的低阶项后剩余的主项.当n充分大时我们用 代替T(n)作为算法复杂性的度量,从而简化分析。例如T(n)=3 n 2+4 n log n+7,则 可以是3n2若进一步假定算法中所有不同元运算的单位执行时间相同，则可不考虑 所包含的系数或常数因子，只表征出以影响算法运行时间的主要因素。,1.2.2 算法复杂性的渐进性态,四川师范大学 计算机科学学院 刘芳 38,渐近分析的记号,1.大O表示法(算法运行时间的上限)若存在正常数c和自然数n0 使得当 n n0 时,有f(n)cg(n)，则称函数 f(n)在n充分大时有上界,且 g(n)是它的一个上界,记为 f(n)=O(g(n),也称 f(n)的阶不高于g(n)的阶。,f(n)=O(g(n),四川师范大学 计算机科学学院 刘芳 39,因此:当说一个算法具有(g(n)的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。所以从计算时间来说，f(n)的数量级就是g(n)。当然，在确定f(n)的数量级时总是希望求出最小的g(n)，使得f(n)=(g(n)。,四川师范大学 计算机科学学院 刘芳 40,例如：3NO(N)N1024O(N)2N2 11N10O(N2)N2O(N3)N3O(N2)又如算法1-1中Tmin(m)2a 3t Tmin(m)O(1)Tmax(m)(m 1)a(2m 1)t(m1)s Tmax(m)O(m),四川师范大学 计算机科学学院 刘芳 41,运算法则O(f(n)+O(g(n)=O(maxf(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)f(n)=O(f(n),四川师范大学 计算机科学学院 刘芳 42,算法的渐近复杂性的阶常见的有:O(1)，O(logn），O(n)，O(nlogn)，O(n2)，O(n3)O(2n)，O(n!)，O(nn),四川师范大学 计算机科学学院 刘芳 43,算法的渐近复杂性的阶对于算法的效率有着决定性的意义:例如：,四川师范大学 计算机科学学院 刘芳 44,在某一 时间内不同算法所能处理的输入量上界,由于算法时间复杂性的量级不同，它们在相同的时间内所能解决问题的大小相差时极其悬殊的。,四川师范大学 计算机科学学院 刘芳 45,计算机速度提高10倍和1万倍的效果,四川师范大学 计算机科学学院 刘芳 46,多项式复杂度的算法如果一算法的最坏情形时间复杂度T(n)=(nk),则称该算法为多项式复杂度的算法。计算机科学家普遍认为：一个多项式复杂度的算法是有效算法，即：对于一个有效算法，哪怕输入量很大，计算机仍然可以处理得了。,四川师范大学 计算机科学学院 刘芳 47,渐近分析的记号,2.大W表示法(算法运行时间的下限）如果$正常数c和自然数n0使得当 n n0 时,有f(n)cg(n)则称函数f(n)在n充分大时有下限,且 g(n)是它的一个下限,记为f(n)=W(g(n),也称f(n)的阶不低于g(n)的阶。,四川师范大学 计算机科学学院 刘芳 48,例如：f(n)=n4+2n2令：C=1，f(n)Cn3 对于无穷多个n成立故：f(n)=(n3),四川师范大学 计算机科学学院 刘芳 49,一些结论：,指数复杂度的算法如果一算法的最坏情形时间复杂度T(n)=(an),a1,则称该算法为指数复杂度的算法。这类算法可认为计算上不可行的算法。有效算法T(n）O(nk)运行时间同阶的算法，常数因子小的算法，优于常数因子大的算法。时间复杂性渐近阶的确定，与n0及常数c的选取有关，当规模很小时，复杂性阶低的算法，不一定比复杂性阶高的算法更有效。,四川师范大学 计算机科学学院 刘芳 50,最佳算法一个问题的计算复杂度的下界，是这个问题所固有的，若一个算法的复杂性已达到了该问题复杂度的下界，算法不可能进一步改进，称达到下界的算法为最佳算法。或这样来定义最佳算法：已知问题的任何算法的运行时间是，则对以时间 求解问题的任何算法，都认为是最优算法。,四川师范大学 计算机科学学院 刘芳 51,渐近分析的记号,3.表示法定义：f(n)=(g(n)当且仅当 f(n)=O(g(n)且f(n)=(g(n)称函数f(n)与g(n)同阶。也可以这样定义：对于定义在自然数集上两个非负函数f(n)、g(n)，如果存在正的常数C0、C1和自然数n0，使得当nn0时有：C0 g(n)f(n)C1 g(n)则称函数 f(n)与 g(n)同阶，记为：f(n)=(g(n)。,四川师范大学 计算机科学学院 刘芳 52,四川师范大学 计算机科学学院 刘芳 53,例1：对函数,结论：对任何正常数k，都有：,四川师范大学 计算机科学学院 刘芳 54,例2：对常函数f(n)4096。令：n0=0；c=4096，使得对g(n)=1对所有的n满足：,四川师范大学 计算机科学学院 刘芳 55,注意：判断f(n)、g(n)阶的方法除了使用定义，还可使用极限法。,四川师范大学 计算机科学学院 刘芳 56,例1：f(n)=n2/2g(n)=307n2f(n)与g(n)同阶，即 f(n)=(g(n),四川师范大学 计算机科学学院 刘芳 57,例2：f(n)=log(n)g(n)=n故f(n)=O(g(n),四川师范大学 计算机科学学院 刘芳 58,例3：f(n)=n3+2 n2+1g(n)=2n2故f(n)=(g(n),四川师范大学 计算机科学学院 刘芳 59,渐近分析的记号,4.o表示法对于任意给定的c0，都存在正整数n0，使得当nn0时有f(n)cg(n),则称函数f(n)当n充分大时的阶比g(n)低，记为f(n)=o(g(n)。例如4nlogn+7=o(3n2+4nlogn+7)。,四川师范大学 计算机科学学院 刘芳 60,5.表示法对于任意给定的0，都存在正整数n0，使得当nn0时有f(n)/g(n),则称函数f(n)当n充分大时的阶比g(n)高，记为f(n)=(g(n)。,四川师范大学 计算机科学学院 刘芳 61,本章小结,重点与难点：算法与程序算法的时间复杂性分析算法的复杂性算法的复杂性的渐近性态算法复杂性在渐近意义下的阶的四种记号的定义,