算法第1章 算法概述.ppt

1,计算机算法设计与分析,（第4版王晓东编著）,2,课程简介,算法设计与分析是计算机科学技术、软件工程及相关专业的重要课程之一培养分析问题和解决问题的能力掌握算法设计的基本方法熟悉算法分析的基本技术为软件系统开发奠定扎实的理论基础,3,算法是计算机科学的重要研究领域之一应用领域不断扩大现代软件系统的核心“算法和数据结构”被列为计算学科的九个主题的第一个我国多数高校越来越重视算法课程的教学分离算法与数据结构课程(程序=算法+数据结构）数据结构关注的是数据的逻辑结构、存储结构以及基本操作算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。以算法设计策略为知识单元系统介绍算法的设计方法与分析技巧,4,主要参考书,王晓东编著，计算机算法设计与分析（C语言版）（第4版），电子工业出版社，2013-5，38.00王晓东编著，计算机算法设计与分析（C语言版）（第3版），电子工业出版社，2004-7-1，25.50王晓东，算法设计与实验题解，电子工业出版社，2013-5，（与C语言版第4版对应）王晓东编著，算法设计与分析（Java语言版），清华大学出版社，2003第1版，29.80T.H.Cormen,C.E.Leisersen,R.L.RivestandC.Stein.IntroductiontoAlgorithms.TheMITPress,secondedition,NewYork,McGraw-Hill,2001.（麻省理工学院出版社）（美）AnanyLevitin著，算法设计与分析基础（影印版），清华大学出版社，2003年第1版，39.00,5,计算机专业学生能力培养,学科人才的4大能力,计算思维能力算法的设计与分析能力程序的设计与实现能力计算机系统的认知、分析、开发与应用能力,学术型,综合型,工程型,6,计算机专业系列课程,公共基础系列基础理论系列思维能力程序设计与算法的训练系列编程能力软件系统系列算法能力(系统级的再认识与再提高)开发能力硬件技术系列实践系列,与课程有机结合，构成整体，协调实现培养学科方法的应用、实践的体验与探索,7,体系结构网络通讯,主干课程体系层次结构图,8,第1章算法概述,学习要点:理解算法的概念理解什么是程序，程序与算法的区别和内在联系掌握算法的计算复杂性概念掌握算法渐近复杂性分析方法及应用技术掌握用C+语言描述算法的方法,9,算法(Algorithm),算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入(2)输出：算法产生至少一个量作为输出(3)确定性：组成算法的每条指令是清晰、无歧义的(4)有限性：算法中每条指令的执行次数是有限的，每条指令的执行时间也是有限的。,10,程序(Program),程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序，通过特定的算法来实现。该子程序得到输出结果后便终止。,11,问题求解(ProblemSolving),理解问题,问题建模与符号描述选择数据结构算法设计策略,设计算法,12,算法复杂性分析,算法复杂性=算法运行所需的计算机资源的量算法的时间复杂性T(n)所需的时间资源的量，其中n是问题的规模（输入大小）算法的空间复杂性S(n)所需的空间资源的量主要讨论时间复杂性,空间复杂性分析相对比较简单,计量方法相似.,13,算法的时间复杂性,最坏情况下的时间复杂性：Tmax(n)=maxT(I)|size(I)=n最好情况下的时间复杂性：Tmin(n)=minT(I)|size(I)=n平均情况下的时间复杂性：Tavg(n)=其中I是问题的规模为n的实例，p(I)是实例I出现的概率。,14,算法渐近复杂性,通常，T(n),asn;If(T(n)-t(n)/T(n)0，asn，则称t(n)是T(n)的渐近性态，或为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项，比T(n)简单。分析算法复杂性的目的：比较求解同一问题的两个不同算法的效率。因此，只要得到不同t(n)的阶即可。,15,渐近分析的记号,设对所有n，存在正函数f(n)0，g(n)0。渐近上界记号OO(g(n)=f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n),记为f(n)O(g(n)，或说f(n)的阶不高于g(n)的阶asn。渐近下界记号(g(n)=f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n),记为f(n)(g(n)，或说f(n)的阶不低于g(n)的阶asn。,16,非紧上界记号oo(g(n)=f(n)|对于任何正常数0，存在正数n00使得对所有nn0有：0f(n)0，存在正数n00使得对所有nn0有：0cg(n)0;p(n)=(nd);f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;kdp(n)=O(nk);kdp(n)=(nk);kdp(n)=o(nk);k0:(am)n=amn;(am)n=(an)m;aman=am+n;a1an为单调递增函数;a1nb=o(an)ex1+x;|x|11+xex1+x+x2;ex=1+x+(x2),asx0;,22,（5）对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=(logn)k;loglogn=log(logn);fora0,b0,c0,23,24,|x|1forx-1,foranya0,logbn=o(na),25,（6）阶层函数Stirlingsapproximation,26,27,算法分析中常见的复杂性函数,28,小规模数据,29,中等规模数据,30,用c+描述算法,31,（1）选择语句：（1.1)if语句：（1.2)？语句：,if(expression)statement;elsestatement;,exp1?exp2:exp3y=x9?100:200;等价于：if(x9)y=100;elsey=200;,32,（1.3)switch语句：,switch(expression)case1:statementsequence;break;case2:statementsequence;break;default:statementsequence;,33,（2）迭代语句：,（2.1)for循环：for(init;condition;inc)statement;（2.2)while循环：while(condition)statement;（2.3)do-while循环：dostatement;while(condition);,34,（3）跳转语句：,（3.1)return语句：returnexpression;（3.2)goto语句：gotolabel;label:,35,（4）函数：,例：,return-typefunctionname(para-list)bodyofthefunction,intmax(intx,inty)returnxy?x:y;,36,（5）模板template：,templateTypemax(Typex,Typey)returnxy?x:y;inti=max(1,2)；doublex=max(1.0,2.0)；,37,（6）动态存储分配：,（6.1）运算符new：运算符new用于动态存储分配new返回一个指向所分配空间的指针例：inty；y=newint；y=10；也可将上述各语句作适当合并如下：inty=newint；y=10；或inty=newint(10)；或inty；y=newint(10)；,38,（6.2）一维数组：,为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。例：floatx=newfloatn；创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。然后可用x0，x1，xn-1来访问每个数组元素。,39,（6.3）运算符delete：,当动态分配的存储空间已不再需要时应及时释放所占用的空间。用运算符delete来释放由new分配的空间。例：deletey；deletex；分别释放分配给y的空间和分配给一维数组x的空间。,40,（6.4）动态二维数组：,创建类型为Type的动态工作数组，这个数组有rows行和cols列。,templatevoidMake2DArray(Type*,41,当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放空间后将x置为0，以防继续访问已被释放的空间。,templatevoidDelete2DArray(Type*,42,算法分析方法,例：顺序搜索算法,templateintseqSearch(Type*a,intn,Typek)for(inti=0;in;i+)if(ai=k)returni;return-1;,43,（1）Tmax(n)=maxT(I)|size(I)=n=O(n)（2）Tmin(n)=minT(I)|size(I)=n=O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p(0p1)；(b)在数组的每个位置i(0in)搜索成功的概率相同，均为p/n。,44,算法分析的基本法则,非递归算法：（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。,45,templatevoidinsertion_sort(Type*a,intn)Typekey;/costtimesfor(inti=1;i=0/c7n-1,46,在最好情况下，ti=1,for1in;在最坏情况下，tii+1,for1in;,47,对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort