第1章 算法概述精选文档.ppt

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

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

2、页，共六十五页1.1 算法与程序l算法：是满足下述性质的指令序列。输入输入：有零个或多个外部量作为算法的输入。输出输出：算法产生至少一个量作为输出。确定性确定性：组成算法的每条指令清晰、无歧义。有限性有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。l程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)即有限性。即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。4本讲稿第四页，共六十五页1

3、.2 算法与数据结构l描述算法可以有多种方式自然语言方式、表格方式、图示形式等本书将采用C+与自然语言与自然语言相结合的方式l算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。l算法数据结构程序算法数据结构程序5本讲稿第五页，共六十五页1.3 表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：1)高级语言更接近算法语言，易学、易掌握易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；2)高级语言为程序员提供了结构化程序设

4、计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠可读性好，可维护性强，可靠性高性高；3)高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高可植性好、重用率高；4)把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。6本讲稿第六页，共六十五页1.3 表达算法的抽象机制2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：1)算法顶层设计与底层实现分离顶层设计与底层实现分离；2)算法设计与数据结构

5、设计隔开，允许数据结构自由选择；3)数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；4)用抽象数据类型表述的算法具有很好的可维护性可维护性；5)算法自然呈现模块化模块化；6)为自顶向下逐步求精自顶向下逐步求精和模块化模块化提供有效途径和工具；7)算法结构清晰结构清晰，层次分明层次分明，便于算法正确性的证明正确性的证明和复杂性的复杂性的分析分析。7本讲稿第七页，共六十五页1.4 描述算法与算法设计l描述算法可以有多种方式，如自然语言方式、图形表格方式等。在这里，我们将采用C+语言语言来描述算法。C+语言的优点是类型丰富、语句精炼，具有面向对象面向对象和面面向过程向过程的双重优点

6、。用C+来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用C+与自然语言相结合的方式来描述算法。算法设计方法主要有：分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。8本讲稿第八页，共六十五页1.4 描述算法与算法设计l问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法9本讲稿第九页，共六十五页1.5 算法分析的基本原则1.正确性正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：l方法的

7、方法的正确性证明算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。l程序的程序的正确性证明证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：l大型程序的正确性证明可以将它分解为小的相互独立的互不相交的模块，分别验证。l小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。10本讲稿第十页，共六十五页1.5 算法分析的基本原则2.工作量工作量时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针11本讲稿第十一页，共六十

8、五页1.5 算法分析的基本原则3.占用空间占用空间空间复杂性分析两种占用：l存储程序和输入数据的空间l存储中间结果或操作单元所占用空间额外空间影响空间的主要因素：l存储程序的空间一般是常数(和输入规模无关)l输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数，称为原地工作的算法。12本讲稿第十二页，共六十五页1.5 算法分析的基本原则4.简单性简单性含义：算法简单，程序结构简单。好处：l容易验证正确性l便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。3n+1问题问题While(n1)if(odd(n)n=3n+1;el

9、se n=n/2;在最坏情况下，该算法的计算时间下界为(logn).但其计算时间上界至今未知。即该算法是否在有限时间内结束？日本学者米田信夫验证了1013内的自然数。这就是Collatz猜想。13本讲稿第十三页，共六十五页1.5 算法分析的基本原则5.最优性最优性含义：指求解某类问题中效率最高的算法 两种最优性l最坏情况最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。l平均情况平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比

10、A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。寻找最优算法的途径(以最坏情况下的最优性为例)l设计算法A，求W(n)。相当于对问题给出最坏情况下的一个上界。l寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算。相当于对问题给出最坏情况下所需基本运算次数的一个下界。l如果W(n)=F(n)，则A是最优的。l如果W(n)F(n)，A不是最优的或者F(n)的下界过低。改进A或设计新算法A使得W(n)F(n)。重复以上两步，最终得到W(n)=F(n)为止。14本讲稿第十四页，共六十五页1.5 算法分析的基本原则例：在n个不

11、同的数中找最大的数。基本运算：比较算法：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)(g(n)g(n)o(f(n)24本讲稿第二十四页，共六十五页l（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)

12、25本讲稿第二十五页，共六十五页渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义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,和的意义是类似的。26本讲稿第二十六页，共六十五页渐近分析中函数比较渐近分析中函数比较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.27本讲稿

13、第二十七页，共六十五页渐近分析记号的若干性质渐近分析记号的若干性质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)；28本讲稿第二十八页，共六十五页l（2）反身性：）反身性：lf(n)=(f(n)；lf(n)=O(f(n)；lf(n)=(f(n).l（3）对称性：）对称性：lf(n

14、)=(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)；29本讲稿第二十九页，共六十五页l（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)。30本讲稿第三十页，共六十五页l规则O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：证明：l对于任

15、意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).31本讲稿第三十一页，共六十五页算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数

16、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的最小整数。32本讲稿第三十二页，共六十五页取整函数的若干性质取整函数的若干性质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 为单调递增函数。33本讲稿第三十三页，共六十五页l（3）多项式函数）多项式

17、函数l p(n)=a0+a1n+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)35本讲稿第三十五页，共六十五页lex 1+x;l|x|1 1+x ex 1+x+x2;l ex=1+x+(x2),as x0;36本讲稿第三十六页，共六

18、十五页l（5）对数函数）对数函数l log n=log2n;l lg n=log10n;l ln n=logen;l logkn=(log n)kl;l log log n=log(log n);l for a0,b0,c037本讲稿第三十七页，共六十五页38本讲稿第三十八页，共六十五页l|x|1 lfor x -1,lfor any a 0,logbn=o(na)39本讲稿第三十九页，共六十五页l（6）阶层函数）阶层函数lStirlings approximation 40本讲稿第四十页，共六十五页41本讲稿第四十一页，共六十五页算法分析中常见的复杂性函数算法分析中常见的复杂性函数42本讲稿

19、第四十二页，共六十五页小规模数据小规模数据43本讲稿第四十三页，共六十五页中等规模数据中等规模数据44本讲稿第四十四页，共六十五页用用c+描述算法描述算法45本讲稿第四十五页，共六十五页l（1）选择语句：）选择语句：l（1.1)if 语句：语句：l（1.2)？语句：？语句：l if(expression)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价于：if(x9)y=100;else y=200;46本讲稿第四十六页，共六十五页（1.3)switch语句：语句：switch(expression)case 1:statement

20、 sequence;break;case 2:statement sequence;break;default:statement sequence;47本讲稿第四十七页，共六十五页（2）迭代语句：）迭代语句：l（2.1)for 循环：循环：l for(init;condition;inc)statement;l（2.2)while 循环：循环：l while(condition)statement;l（2.3)do-while 循环：循环：l dol statement;l while(condition);48本讲稿第四十八页，共六十五页（3）跳转语句：）跳转语句：l（3.1)return

21、语句：语句：l return expression;l（3.2)goto语句：语句：l goto label;l l label:49本讲稿第四十九页，共六十五页（4）函数：）函数：l例：例：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;50本讲稿第五十页，共六十五页（5）模板）模板template：template Type max(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0

22、)；51本讲稿第五十一页，共六十五页（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)；52本讲稿第五十二页，共六十五页（6.2）一维数组）一维数组：l为了在运行时创建一个大小可动态变化的一维浮点数组x，可先将x声明为一个float类型的指针。然后用new为数组动态地分配存储空间。l例：例：lfloa

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

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

25、x;x=0;56本讲稿第五十六页，共六十五页算法分析方法算法分析方法l例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;57本讲稿第五十七页，共六十五页l（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。58本

26、讲稿第五十八页，共六十五页算法分析的基本法则算法分析的基本法则l非递归算法：非递归算法：l（1）for/while 循环l循环体内计算时间*循环次数；l（2）嵌套循环l循环体内计算时间*所有循环次数；l（3）顺序语句l各语句计算时间相加；l（4）if-else语句lif语句计算时间和else语句计算时间的较大者。59本讲稿第五十九页，共六十五页templatevoid 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-;/c

27、6 sum of(ti-1)aj+1=key;/c7 n-1 60本讲稿第六十页，共六十五页l在最好情况下，ti=1,for 1 i n;l在最坏情况下，ti i+1,for 1 i n;61本讲稿第六十一页，共六十五页l对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，l由此可见，Tmax(n)=(n2)62本讲稿第六十二页，共六十五页最优算法最优算法l问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。l例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。l堆排序算法是最优算法。63本讲稿第六十三页，共六十五页递归算法复杂性分析递归算法复杂性分析l int factorial(int n)l l if(n=0)return 1;l return n*factorial(n-1);l 64本讲稿第六十四页，共六十五页HomeworklP51.算法分析题 1-1,1-2,1-4,1-6,1-92.算法实现题 1-1,1-3,1-4,1-565本讲稿第六十五页，共六十五页