第1章-算法概述.ppt

《第1章-算法概述.ppt》由会员分享，可在线阅读，更多相关《第1章-算法概述.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于本课程l课程目的：计算机算法设计与分析导引以算法设计为主，介绍算法设计的主要方法和基本思以算法设计为主，介绍算法设计的主要方法和基本思想；并简要介绍算法分析概念想；并简要介绍算法分析概念不是程序设计课，也不是数学课不是程序设计课，也不是数学课l授课形式：上课+作业/实验+期末考试l参考资料：Web资源 ,图书资源 ,1第1章 算法概述l本章知识要点：1.1 算法与程序1.2 算法与数据结构1.3 表达算法的抽象机制1.4 描述算法与算法设计1.5 算法分析的基本原则1.6 算法复杂性分析C+程序语言描述算法l计划授课时间：4课时21.1 算法与程序l算法：是满足下述性质的指令序列。输入输入

2、：有零个或多个外部量作为算法的输入。输出输出：算法产生至少一个量作为输出。确定性确定性：组成算法的每条指令清晰、无歧义。有限性有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。l程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)即有限性。即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。31.2 算法与数据结构l描述算法可以有多种方式自然语言方式、表格方式、图示形式等本书将采用C+与自然

3、语言与自然语言相结合的方式l算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。l算法数据结构程序算法数据结构程序41.3 表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：1)高级语言更接近算法语言，易学、易掌握易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；2)高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可可读性好，可维护性强，可靠性高靠性高；3)高级语言不依赖于机器语

4、言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高可植性好、重用率高；4)把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。51.3 表达算法的抽象机制2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：1)算法顶层设计与底层实现分离顶层设计与底层实现分离；2)算法设计与数据结构设计隔开，允许数据结构自由选择；3)数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；4)用抽象数据类型表述的算法具有很好的可维护

5、性可维护性；5)算法自然呈现模块化模块化；6)为自顶向下逐步求精自顶向下逐步求精和模块化模块化提供有效途径和工具；7)算法结构清晰结构清晰，层次分明层次分明，便于算法正确性的证明正确性的证明和复复杂性的分析杂性的分析。61.4 描述算法与算法设计l描述算法可以有多种方式，如自然语言方式、图形表格方式等。在这里，我们将采用C+语言语言来描述算法。C+语言的优点是类型丰富、语句精炼，具有面向对象面向对象和面向过程面向过程的双重优点。用C+来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用C+与自然语言相结合的方式来描述算法。算法设计方法主要有：分治策略、动

6、态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。71.4 描述算法与算法设计l问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法81.5 算法分析的基本原则1.正确性正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：l方法的方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。l程序的程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：l大型程序的正确性证明可以将它分解为小的相

7、互独立的互不相交的模块，分别验证。l小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。91.5 算法分析的基本原则2.工作量工作量时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针101.5 算法分析的基本原则3.占用空间占用空间空间复杂性分析两种占用：l存储程序和输入数据的空间l存储中间结果或操作单元所占用空间额外空间影响空间的主要因素：l存储程序的空间一般是常数(和输入规模无关)l输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小

8、如果额外空间相对于输入规模是常数，称为原地工作的算法。111.5 算法分析的基本原则4.简单性简单性含义：算法简单，程序结构简单。好处：l容易验证正确性l便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。3n+1问题问题While(n1)if(odd(n)n=3n+1;else n=n/2;在最坏情况下，该算法的计算时间下界为(logn).但其计算时间上界至今未知。即该算法是否在有限时间内结束？日本学者米田信夫验证了1013内的自然数。这就是Collatz猜想。121.5 算法分析的基本原则5.最优性最优性含义：指求解某类问题中效率最高的算法 两种最优性l最坏情况

9、最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。l平均情况平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。寻找最优算法的途径(以最坏情况下的最优性为例)l设计算法A，求W(n)。相当于对问题给出最坏情况下的一个上界。l寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算。相当于对问题给出最坏情况下所需基

10、本运算次数的一个下界。l如果W(n)=F(n)，则A是最优的。l如果W(n)F(n)，A不是最优的或者F(n)的下界过低。改进A或设计新算法A使得W(n)F(n)。重复以上两步，最终得到W(n)=F(n)为止。131.5 算法分析的基本原则例：在n个不同的数中找最大的数。基本运算：比较算法：Find Max输入：数组L，项数 n 1 1输出：L中的最大项MAX1)MAXL(1);i2;2)while in do3)if MAX0，存在正数和n0 0使得对所有n n0有：0 f(n)0，存在正数和n0 0使得对所有n n0有：0 cg(n)f(n)l等价于 f(n)/g(n)，as n。lf(n

11、)(g(n)g(n)o(f(n)23l（5）紧渐近界记号紧渐近界记号 l(g(n)=f(n)|存在正常数c1,c2和n0使得对所有n n0有：c1g(n)f(n)c2g(n)l 定理定理1：(g(n)=O(g(n)(g(n)24渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义lf(n)=(g(n)的确切意义是：f(n)(g(n)。l一般情况下，等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。l例如：2n2+3n+1=2n2+(n)表示l 2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某个函数。l等式和不等式中渐近记号O,o,和的意义是类似的。25渐

12、近分析中函数比较渐近分析中函数比较lf(n)=O(g(n)a b;lf(n)=(g(n)a b;lf(n)=(g(n)a=b;lf(n)=o(g(n)a b.26渐近分析记号的若干性质渐近分析记号的若干性质l（1）传递性：）传递性：lf(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；lf(n)=O(g(n)，g(n)=O(h(n)f(n)=O(h(n)；lf(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；lf(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；lf(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；27l（2）反身性：）反身

13、性：lf(n)=(f(n)；lf(n)=O(f(n)；lf(n)=(f(n).l（3）对称性：）对称性：lf(n)=(g(n)g(n)=(f(n).l（4）互对称性：）互对称性：lf(n)=O(g(n)g(n)=(f(n)；lf(n)=o(g(n)g(n)=(f(n)；28l（5）算术运算：）算术运算：lO(f(n)+O(g(n)=O(maxf(n),g(n)；lO(f(n)+O(g(n)=O(f(n)+g(n)；lO(f(n)*O(g(n)=O(f(n)*g(n)；lO(cf(n)=O(f(n)；lg(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。29l规则O(f(n)+O(g

14、(n)=O(maxf(n),g(n)的证明：证明：l对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)c1f(n)。l类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，使得对所有n n2，有g1(n)c2g(n)。l令c3=maxc1,c2，n3=maxn1,n2，h(n)=maxf(n),g(n)。l则对所有的 n n3，有lf1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c32 maxf(n),g(n)=2c3h(n)=O(maxf(n),g(n).30算法渐近复杂性分析中常用函

15、数算法渐近复杂性分析中常用函数l（1）单调函数）单调函数l单调递增：m n f(m)f(n);l单调递减：m n f(m)f(n);l严格单调递增：m n f(m)f(n);l严格单调递减：m f(n).l（2）取整函数）取整函数l x ：不大于x的最大整数；l x ：不小于x的最小整数。31取整函数的若干性质取整函数的若干性质l x-1 x x x 0，有：l n/a /b =n/ab ;l n/a /b =n/ab ;l a/b (a+(b-1)/b;l a/b (a-(b-1)/b;l f(x)=x ,g(x)=x 为单调递增函数。32l（3）多项式函数）多项式函数l p(n)=a0+a

16、1n+a2n2+adnd；ad0;l p(n)=(nd);l f(n)=O(nk)f(n)多项式有界；l f(n)=O(1)f(n)c;l k d p(n)=O(nk);lk d p(n)=(nk);lk d p(n)=o(nk);lk 0:l a0=1;l a1=a;l a-1=1/a;l(am)n=amn;l(am)n=(an)m;l aman =am+n;l a1 an为单调递增函数;l a1 nb=o(an)34lex 1+x;l|x|1 1+x ex 1+x+x2;l ex=1+x+(x2),as x0;35l（5）对数函数）对数函数l log n=log2n;l lg n=log1

17、0n;l ln n=logen;l logkn=(log n)kl;l log log n=log(log n);l for a0,b0,c03637l|x|1 lfor x -1,lfor any a 0,logbn=o(na)38l（6）阶层函数）阶层函数lStirlings approximation 3940算法分析中常见的复杂性函数算法分析中常见的复杂性函数41小规模数据小规模数据42中等规模数据中等规模数据43用用c+描述算法描述算法44l（1）选择语句：）选择语句：l（1.1)if 语句：语句：l（1.2)？语句：？语句：l if(expression)statement;els

18、e statement;exp1?exp2:exp3 y=x9?100:200;等价于：if(x9)y=100;else y=200;45（1.3)switch语句：语句：switch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;46（2）迭代语句：）迭代语句：l（2.1)for 循环：循环：l for(init;condition;inc)statement;l（2.2)while 循环：循环：l while(condition)st

19、atement;l（2.3)do-while 循环：循环：l dol statement;l while(condition);47（3）跳转语句：）跳转语句：l（3.1)return语句：语句：l return expression;l（3.2)goto语句：语句：l goto label;l l label:48（4）函数：）函数：l例：例：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;49（5）模板）模板template：template Type ma

20、x(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0)；50（6）动态存储分配：）动态存储分配：l（6.1）运算符）运算符new：l运算符new用于动态存储分配。lnew返回一个指向所分配空间的指针。l例：int x；y=new int；y=10；l也可将上述各语句作适当合并如下：lint y=new int；y=10；l或 int y=new int(10)；l或 int y；y=new int(10)；51（6.2）一维数组）一维数组：l为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个flo

21、at类型的指针。然后用new为数组动态地分配存储空间。l例：例：lfloat x=new floatn；l创建一个大小为n的一维浮点数组。运算符new分配n个浮点数所需的空间，并返回指向第一个浮点数的指针。l然后可用x0，x1，xn-1来访问每个数组元素。52（6.3）运算符）运算符delete：l当动态分配的存储空间已不再需要时应及时释放所占用的空间。l用运算符delete来释放由new分配的空间。l例：例：ldelete y；ldelete x；l分别释放分配给y的空间和分配给一维数组x的空间。53（6.4）动态二维数组）动态二维数组：l创建类型为Type的动态工作数组，这个数组有rows

22、行和cols列。template void Make2DArray(Type*&x,int rows,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;54l当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在for循环中为每一行所分配的空间。然后释放为行指针分配的空间。l释放空间后将x置为0，以防继续访问已被释放的空间。template void Delete2DArray(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0

23、;55算法分析方法算法分析方法l例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;56l（1）Tmax(n)=max T(I)|size(I)=n=O(n)l（2）Tmin(n)=min T(I)|size(I)=n=O(1)l（3）在平均情况下，假设：l (a)搜索成功的概率为p(0 p 1)；l (b)在数组的每个位置i(0 i n)搜索成功的概率相同，均为 p/n。57算法分析的基本法则算法分析的基本法则l非递归算法：非递归算法：l（1

24、）for/while 循环l循环体内计算时间*循环次数；l（2）嵌套循环l循环体内计算时间*所有循环次数；l（3）顺序语句l各语句计算时间相加；l（4）if-else语句lif语句计算时间和else语句计算时间的较大者。58templatevoid insertion_sort(Type*a,int n)Type key;/cost times for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum of(ti-1)aj+1=key;/c7 n-1 59l在最好情况下，ti=1,for 1 i n;l在最坏情

25、况下，ti i+1,for 1 i n;60l对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，l由此可见，Tmax(n)=(n2)61最优算法最优算法l问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。l例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。l堆排序算法是最优算法。62递归算法复杂性分析递归算法复杂性分析l int factorial(int n)l l if(n=0)return 1;l return n*factorial(n-1);l 63精品课件精品课件！64精品课件精品课件！65HomeworklP51.算法分析题 1-1,1-2,1-4,1-6,1-92.算法实现题 1-1,1-3,1-4,1-566