《第1章算法计算与分析.ppt》由会员分享，可在线阅读，更多相关《第1章算法计算与分析.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法设计与分析（第计算机算法设计与分析（第3版）版）第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。掌握用掌握用C+语言描述算法的方法。语言描述算法的方法。算法算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：(1)输入输入：有外部提供的量
2、作为算法的输入。：有外部提供的量作为算法的输入。(2)输出输出：算法产生至少一个量作为输出。：算法产生至少一个量作为输出。(3)确定性确定性：组成算法的每条指令是清晰，无歧义的。：组成算法的每条指令是清晰，无歧义的。(4)有限性有限性：算法中每条指令的执行次数是有限的，执：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。行每条指令的时间也是有限的。程序程序(Program)程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因例如操作系统，是一个在无限
3、循环中执行的程序，因而不是一个算法。而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。该子程序得到输出结果后便终止。问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法算法复杂性分析算法复杂性分析 算法复杂性算法复杂性=算法所需要的计算机资源算法所需要的计算机资源算法的时间复杂性算法
4、的时间复杂性T(n)；算法的空间复杂性算法的空间复杂性S(n)。其中其中n是问题的规模（输入大小）。是问题的规模（输入大小）。算法的时间复杂性算法的时间复杂性（1）最坏情况最坏情况下的时间复杂性下的时间复杂性 Tmax(n)=max T(I)|size(I)=n（2）最好情况最好情况下的时间复杂性下的时间复杂性 Tmin(n)=min T(I)|size(I)=n（3）平均情况平均情况下的时间复杂性下的时间复杂性 Tavg(n)=其中其中I是问题的规模为是问题的规模为n的实例，的实例，p(I)是实是实 例例I出现的概率。出现的概率。算法渐近复杂性算法渐近复杂性T(n),as n;(T(n)-t
5、(n)/T(n)0，as n;t(n)是是T(n)的渐近性态，为算法的渐近复杂性。的渐近性态，为算法的渐近复杂性。在数学上，在数学上，t(n)是是T(n)的渐近表达式，是的渐近表达式，是T(n)略去低阶略去低阶项留下的主项。它比项留下的主项。它比T(n)简单。简单。渐近分析的记号渐近分析的记号在下面的讨论中，对所有在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号渐近上界记号OO(g(n)=f(n)|存在正常数存在正常数c和和n0使得对所有使得对所有n n0有：有：0 f(n)cg(n)（2）渐近下界记号渐近下界记号 (g(n)=f(n)|存在正常数存在正常数c和和n0使得对
6、所有使得对所有n n0有：有：0 cg(n)f(n)（3）非紧上界记号非紧上界记号o o(g(n)=f(n)|对于任何正常数对于任何正常数c0，存在正数和存在正数和n0 0使得对所有使得对所有n n0有：有：0 f(n)0，存在正数和存在正数和n0 0使得对所有使得对所有n n0有：有：0 cg(n)f(n)等价于等价于 f(n)/g(n)，as n。f(n)(g(n)g(n)o(f(n)（5）紧渐近界记号紧渐近界记号 (g(n)=f(n)|存在正常数存在正常数c1,c2和和n0使得对所有使得对所有n n0有：有：c1g(n)f(n)c2g(n)定理定理1：(g(n)=O(g(n)(g(n)渐
7、近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义f(n)=(g(n)的确切意义是：的确切意义是：f(n)(g(n)。一般情况下，等式和不等式中的渐近记号一般情况下，等式和不等式中的渐近记号(g(n)表示表示(g(n)中的某个函数。中的某个函数。例如：例如：2n2+3n+1=2n2+(n)表示表示 2n2+3n+1=2n2+f(n)，其中，其中f(n)是是(n)中某个函数。中某个函数。等式和不等式中渐近记号等式和不等式中渐近记号O,o,和和 的意义是类似的。的意义是类似的。渐近分析中函数比较渐近分析中函数比较f(n)=O(g(n)a b;f(n)=(g(n)a b;f(n)=(
8、g(n)a=b;f(n)=o(g(n)a b.渐近分析记号的若干性质渐近分析记号的若干性质（1）传递性：）传递性：f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=O(g(n)，g(n)=O(h(n)f(n)=O(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；f(n)=o(g(n)，g(n)=o(h(n)f(n)=o(h(n)；f(n)=(g(n)，g(n)=(h(n)f(n)=(h(n)；（2）反身性：）反身性：f(n)=(f(n)；f(n)=O(f(n)；f(n)=(f(n).（3）对称性：）对称性：f(n)=(g(n)g(n)=(f(n
9、).（4）互对称性：）互对称性：f(n)=O(g(n)g(n)=(f(n)；f(n)=o(g(n)g(n)=(f(n)；（5）算术运算：）算术运算：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)。规则规则O(f(n)+O(g(n)=O(maxf(n),g(n)的的证明：证明：对于任意对于任意f1(n)O(f(n)，存在正常数，存在正常数c1和自然数和自然数n1，使得对所有，使得对所有n n
10、1，有，有f1(n)c1f(n)。类似地，对于任意类似地，对于任意g1(n)O(g(n)，存在正常数，存在正常数c2和自然数和自然数n2，使得对所有使得对所有n n2，有，有g1(n)c2g(n)。令令c3=maxc1,c2，n3=maxn1,n2，h(n)=maxf(n),g(n)。则对所有的则对所有的 n n3，有，有f1(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).算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数（1）单调函数）单调函数单调递增：单调递
11、增：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的最小整数。的最小整数。取整函数的若干性质取整函数的若干性质 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 为为单调递增函数。单调递增函数。（3）多项式函数）多项式函数 p(n)=a0+a1n+a2n
12、2+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;（5）对数函数）对数函数 log n=log2n;lg n=log10n;ln n=logen;logkn=(log n)k;l
13、og log n=log(log n);for a0,b0,c0|x|1 for x -1,for any a 0,logbn=o(na)（6）阶层函数）阶层函数Stirlings approximation 算法分析中常见的复杂性函数算法分析中常见的复杂性函数小规模数据小规模数据中等规模数据中等规模数据用用c+描述算法描述算法输入输入/输出语句：预处理为输出语句：预处理为#include输入语句：输入语句：用用cin进行输入进行输入 cin语句的一般格式为语句的一般格式为:cin变量变量1变量变量2变量变量n;输入时不用指定数据类型，也可以使用多个提取符，将键盘输输入时不用指定数据类型，也可
14、以使用多个提取符，将键盘输入的数据送到输入流入的数据送到输入流cin中，然后存到内存。中，然后存到内存。输出语句：输出语句：用用cout进行输出进行输出 cout语句的一般格式为：语句的一般格式为：cout表达式表达式1表达式表达式2表达式表达式n 输出时，用户不必通知计算机按何种类型输出，系统会自动输出时，用户不必通知计算机按何种类型输出，系统会自动判别输出数据的类型，使输出的数据按相应的类型输出。判别输出数据的类型，使输出的数据按相应的类型输出。int i=10;float j=8.5;char*str=Windows!;cout i=i endl;cout j=j endl;cout s
15、tr=str endl;int i1,i2,sum;/*变变量定量定义义*/cout i1 i2;/*输输入数据入数据*/sum=i1+i2;/*计计算算i1,i2的和的和*/cout sum=sum 9?100:200;等价于：等价于：if(x9)y=100;else y=200;（1.3)switch语句：语句：switch(expression)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;（2）迭代语句：）迭代语句：（2.1)for 循环：循环：for
16、(init;condition;inc)statement;（2.2)while 循环：循环：while(condition)statement;（2.3)do-while 循环：循环：do statement;while(condition);（3）跳转语句：）跳转语句：（3.1)return语句：语句：return expression;（3.2)goto语句：语句：goto label;label:（4）函数：）函数：例：例：return-type function name(para-list)body of the function int max(int x,int y)retur
17、n xy?x:y;（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)；（6）动态存储分配：）动态存储分配：（6.1）运算符）运算符new：运算符运算符new用于动态存储分配。用于动态存储分配。new返回一个指向所分配空间的指针。返回一个指向所分配空间的指针。例：例：int y；y=new int；y=10；也可将上述各语句作适当合并如下：也可将上述各语句作适当合并如下：int y=new int；y=10；或或 int y=new int(10)；
18、或或 int y；y=new int(10)；（6.2）一维数组）一维数组：为了在运行时创建一个大小可动态变化的一维浮点数组为了在运行时创建一个大小可动态变化的一维浮点数组x，可先，可先将将x声明为一个声明为一个float类型的指针。然后用类型的指针。然后用new为数组动态地分配为数组动态地分配存储空间。存储空间。例：例：float x=new floatn；创建一个大小为创建一个大小为n的一维浮点数组。运算符的一维浮点数组。运算符new分配分配n个浮点数所个浮点数所需的空间，并返回指向第一个浮点数的指针。需的空间，并返回指向第一个浮点数的指针。然后可用然后可用x0，x1，xn-1来访问每个数
19、组元素。来访问每个数组元素。（6.3）运算符）运算符delete：当动态分配的存储空间已不再需要时应及时释放所占当动态分配的存储空间已不再需要时应及时释放所占用的空间。用的空间。用运算符用运算符delete来释放由来释放由new分配的空间。分配的空间。例：例：delete y；delete x；分别释放分配给分别释放分配给 y的空间和分配给一维数组的空间和分配给一维数组x的空间。的空间。（6.4）动态二维数组）动态二维数组：创建类型为创建类型为Type的动态工作数组，这个数组有的动态工作数组，这个数组有rows行行和和cols列。列。template void Make2DArray(Type
20、*&x,int rows,int cols)x=new Type*rows;for(int i=0;irows;i+)xi=new Typecols;当不再需要一个动态分配的二维数组时，可按以下步骤释放它所当不再需要一个动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在占用的空间。首先释放在for循环中为每一行所分配的空间。然后循环中为每一行所分配的空间。然后释放为行指针分配的空间。释放为行指针分配的空间。释放空间后将释放空间后将x置为置为0，以防继续访问已被释放的空间。，以防继续访问已被释放的空间。template void Delete2DArray(Type*&x,int
21、rows)for(int i=0;irows;i+)delete xi;delete x;x=0;算法分析方法算法分析方法例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;（1）Tmax(n)=max T(I)|size(I)=n=O(n)（2）Tmin(n)=min T(I)|size(I)=n=O(1)（3）在平均情况下，假设：）在平均情况下，假设：(a)搜索成功的概率为搜索成功的概率为p(0 p 1)；(b)在数组的每个位置在数组的每个
22、位置i(0 i n)搜索成功的概率相同，均为搜索成功的概率相同，均为 p/n。算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：（1）for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；（3）顺序语句）顺序语句各语句计算时间相加；各语句计算时间相加；（4）if-else语句语句if语句计算时间和语句计算时间和else语句计算时间的较大者。语句计算时间的较大者。templatevoid insertion_sort(Type*a,int n)Type key;/cost
23、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 在最好情况下，在最好情况下，ti=1,for 1 i n;在最坏情况下，在最坏情况下，ti i+1,for 1 i n;对于输入数据对于输入数据ai=n-i,i=0,1,n-1，算法，算法insertion_sort 达到其达到其最坏情形。因此，最坏情形。因此，由此可见，由此可见，Tmax(n)=(n2)最优算法最优算法问题的计算时间下界为问题的计算时间下界为(f(n)，则计算时间复杂性为，则计算时间复杂性为O(f(n)的算法是的算法是最优算法。最优算法。例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为，计算时间复杂性为O(nlogn)的排序算法是最优算法。的排序算法是最优算法。堆排序算法是最优算法。堆排序算法是最优算法。递归算法复杂性分析递归算法复杂性分析 int factorial(int n)if(n=0)return 1;return n*factorial(n-1);