第1章-算法概述课件

算法设计与分析算法设计与分析第第1章章 算法概述算法概述理解研究算法的目的理解研究算法的目的理解算法的概念和算法的基本要素理解算法的概念和算法的基本要素掌握算法在最坏情况、最好情况和平均情掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念况下的计算复杂性概念掌握算法复杂性的渐近性态的数学表述掌握算法复杂性的渐近性态的数学表述2024/7/112算法设计与分析算法分析的研究内容算法分析的研究内容研究计算机程序研究计算机程序性能性能和资源利用和资源利用在程序设计方面，什么比性能更重要？在程序设计方面，什么比性能更重要？正确性正确性功能性功能性可维护性可维护性稳定性，健壮性稳定性，健壮性可重用性，模块化可重用性，模块化安全性安全性用户友好用户友好2024/7/113算法设计与分析为什么要研究算法？为什么要研究算法？通过算法程序员可以定量的分析程序的执通过算法程序员可以定量的分析程序的执行效率。行效率。Scalability算法可以帮助我们区分什么是算法可以帮助我们区分什么是“可行的可行的”feasible，什么是，什么是“不可能的不可能的”impossible。描述程序行为的语言描述程序行为的语言程序的执行程序的执行速度速度是追求的目标是追求的目标!2024/7/114算法设计与分析1.1 算法与程序算法与程序算法的定义：算法的定义：解决问题的一种方法或一个解决问题的一种方法或一个过程。过程。算法的基本要素：算法的基本要素：输入：有零个或多个外部量作为算法的输入。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。行每条指令的时间也有限。2024/7/115算法设计与分析举例举例：排序问题排序问题排序：排序：将无序数值序列排列成按值非递减将无序数值序列排列成按值非递减序列。序列。问题定义：问题定义：输入：数值序列输入：数值序列输出：数值序列输出：数值序列且且a1a2 an。31,41,59,26,41,58 26,31,41,41,58,59 2024/7/116算法设计与分析插入排序插入排序templatevoid INSERTION-SORT(Type A,int n)1 int i,j;Type key;2 for(j=1;j=0&Aikey)7 Ai+1=Ai;8 i=i-1;9 Ai+1=key;10 0jn-1AKey已排好序的已排好序的5246130123452024/7/117算法设计与分析插入排序插入排序2524613012345key(a)4254613012345key(b)6245613012345key(c)1245613012345key(d)3124563012345key(e)123456012345(f)2024/7/118算法设计与分析算法的时间效率算法的时间效率templatevoid INSERTION-SORT(Type A,int n)1 int i,j;Type key;2 for(j=1;j=0&Aikey)7 Ai+1=Ai;8 i=i-1;9 Ai+1=key;10 2024/7/119算法设计与分析影响算法时间效率的因素影响算法时间效率的因素影响一个算法的时间效率的因素有哪些？影响一个算法的时间效率的因素有哪些？问题的规模问题的规模以及以及给定的输入给定的输入。最好情况最好情况&最坏情况？最坏情况？举例举例：排序排序34,14,17,8,54,73与与排序排序8,14,17,34,54,73与与排序排序73,54,34,17,14,52024/7/1110算法设计与分析算法与程序的关系算法与程序的关系什么是程序？与算法是什么关系？什么是程序？与算法是什么关系？程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。算法算法 程序程序+数据结构=2024/7/1111算法设计与分析算法和程序算法和程序证明正确性证明正确性分析分析算法算法设计程序设计程序理解问题理解问题精确解或近似解选择数据结构精确解或近似解选择数据结构算法设计策略算法设计策略设计设计算法算法算法描述方式与算法设计方法算法描述方式与算法设计方法描述算法可以有多种方式：自然语言、数描述算法可以有多种方式：自然语言、数学语言、流程图、表格方式、学语言、流程图、表格方式、图示形式、图示形式、程序设计语言等。程序设计语言等。在此将采用在此将采用C+与自然与自然语言相结合语言相结合的方式来描述算法。的方式来描述算法。算法设计方法主要有：算法设计方法主要有：分治策略分治策略、动态规动态规划划、贪心法贪心法、回溯法回溯法、分支限界分支限界、概率算、概率算法等。法等。2024/7/1113算法设计与分析1.2 算法的复杂性分析算法的复杂性分析算法复杂性是只依赖于算法要解的算法复杂性是只依赖于算法要解的问题的问题的规模规模、算法的输入算法的输入和和算法本身算法本身的函数。的函数。C=F(N,I,A)算法算法复杂性复杂性函数函数算法要解算法要解问题的规模问题的规模算法算法的输入的输入算法算法本身本身2024/7/1114算法设计与分析时间复杂性时间复杂性Worst-case:(usually)最坏情况最坏情况 T(n)=maximum time of algorithm on any input of size n.Average-case:(sometimes)平均情况平均情况 T(n)=expected time of algorithm over all inputs of size n.Need assumption of statistical distribution of inputs.Best-case:(bogus)最好情况最好情况 Cheat with a slow algorithm that works fast on some input.2024/7/1115算法设计与分析举例举例：顺序查找顺序查找templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;137-34 51 21 18 45查找查找512024/7/1116算法设计与分析与机器无关的时间效率与机器无关的时间效率（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)在数组的每个位置在数组的每个位置i(0 i n)搜索成功搜索成功的概率相同，均为的概率相同，均为 p/n。2024/7/1117算法设计与分析一般地，一般地，关键操作关键操作的执行次数的执行次数与问题的规模有关，与问题的规模有关，是是n的函数。的函数。在很多情况下，它是算法中执行次数最多的操作在很多情况下，它是算法中执行次数最多的操作（程序步程序步），关键操作通常是位于算法），关键操作通常是位于算法最内层循最内层循环环的的程序步程序步。for(i=0;in;i+)/n+1 for(j=0;jn;j+)/n(n+1)cij=0;/n2 for(k=0;kn;k+)/n2(n+1)cij+=aik*bkj;/n3 矩阵乘法矩阵乘法2024/7/1118算法设计与分析2.复杂性的渐近分析复杂性的渐近分析比较两种不同的复杂性比较两种不同的复杂性3n+2和和3n+202n和和cn讨论当讨论当n时，算法时，算法的时间复杂性，即复杂性的时间复杂性，即复杂性的渐近性态的渐近性态2024/7/1119算法设计与分析1)渐近性态渐近性态设设T(n)为为算法算法A的的时间复杂性函数时间复杂性函数，则它是，则它是n的单的单调递增函数，如果存在一个函数调递增函数，如果存在一个函数 使得当使得当n，有：，有：称称 是是T(n)当当n时的时的渐近性态渐近性态或或 渐近复杂性渐近复杂性。在数学上，在数学上，T(n)与与 有相同的最高阶项，可取有相同的最高阶项，可取 为为略去略去T(n)的的低阶项后剩余的主项低阶项后剩余的主项。T(n)=3n2+4nlogn+7，则 是多少？2024/7/1120算法设计与分析2)渐近性态的阶渐近性态的阶设设f(N)和和g(N)是定义在是定义在正整数集上的正函数正整数集上的正函数。大大O表示法表示法（算法运行时间的上限）（算法运行时间的上限）描述一个函数数量级的描述一个函数数量级的渐近上界渐近上界。定义定义：如果存在如果存在正常数正常数c和和自然数自然数N0，使得对于所，使得对于所有的有的NN0时，有时，有f(N)cg(N)，即函数，即函数f至多是至多是g的的c倍。称倍。称函数函数 f(N)在在N充分大时有充分大时有上界上界，且，且g(N)是它是它的一个上界函数，记为的一个上界函数，记为f(N)=O(g(N)，也称，也称f(N)的的阶至多是阶至多是g(N)的的阶阶，g也称为也称为f的的阶函数阶函数。2024/7/1121算法设计与分析这两个函数当整型自变量这两个函数当整型自变量n趋向于无穷大时，两者趋向于无穷大时，两者的比值是一个不等于的比值是一个不等于0的常数。的常数。即，即，f(N)的增长最的增长最多与多与g(N)的增长一样快，则称的增长一样快，则称O(g(N)是是f(N)的的上界上界。n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况无关紧要况无关紧要f(n)cg(n)2024/7/1122算法设计与分析g通常取单项形式：通常取单项形式：1、logn、n、nlogn、n2、n3、2n、n!。例如例如，3n=O(n)，n+1024=O(n)，2n2+11n-10=O(n2)，对于多项式情形的复杂性函数，对于多项式情形的复杂性函数，阶函数一般阶函数一般取多项式的取多项式的最高项最高项。（1）f(n)=2n+3=O(？)（2）f(n)=10n2+4n+2=O(？)（3）f(n)=n!=O(？)2024/7/1123算法设计与分析结论结论对于给定的对于给定的f，可以有无数个，可以有无数个g与之对应。与之对应。例如例如，f(n)=2n+3，g可以是：可以是：n,n2,n3,。应当选择应当选择最小的函数最小的函数g作为作为f的上界。这个的上界。这个上界的阶越低则评估就上界的阶越低则评估就越精确越精确，结果就越，结果就越有价值有价值。2024/7/1124算法设计与分析运算法则运算法则1.O(f)+O(g)=O(max(f,g)2.O(f)+O(g)=O(f+g)3.O(f)O(g)=O(fg)4.如果如果g(n)=O(f(n)，则，则O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n)=O(f(n)2024/7/1125算法设计与分析如果存在正常数如果存在正常数c和自然数和自然数N0，使得对于所有的，使得对于所有的NN0时，有时，有f(N)cg(N)，则称函数，则称函数f(N)在在N充充分大时有分大时有下限下限，且，且g(N)是它的一个下限，记为是它的一个下限，记为f(N)=(g(N)，也称，也称f(N)的阶不低于的阶不低于g(N)的阶的阶。在在N充分大时，在相差一个非零常数倍的情况下，充分大时，在相差一个非零常数倍的情况下，g是是f的的下界函数下界函数。大大表示法表示法（算法运行时间的下限）（算法运行时间的下限）2024/7/1126算法设计与分析f(N)的增长至少象的增长至少象g(N)那样快，表示解一个特定问那样快，表示解一个特定问题的任何算法的题的任何算法的时间下界。时间下界。n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况无关紧要况无关紧要f(n)cg(n)2024/7/1127算法设计与分析结论结论记号可以看作是记号可以看作是n的函数的集合。称一个算法具的函数的集合。称一个算法具有有(g(n)的运行时间，是指当的运行时间，是指当n足够大时，该算足够大时，该算法的实际运行至少需要法的实际运行至少需要g(n)的某个常数倍的时间的某个常数倍的时间量量。（1）f(n)=2n+3=(n)（2）f(n)=10n2+4n+2=(n2)2024/7/1128算法设计与分析设有函数设有函数f(n)和和g(n)是定义在非负整数集合上的是定义在非负整数集合上的正函数，如果存在正常数正函数，如果存在正常数c1、c2和和n0，使得对所，使得对所有有nn0时，有时，有c1g(n)f(n)c2g(n)，则称函数的，则称函数的阶阶是是(g(n)，记作，记作f(n)=(g(n)。f(n)=(g(n)，当且仅当，当且仅当f(n)=O(g(n)且且f(n)=(g(n)，称函数，称函数f(n)与与g(n)同阶同阶。表示法表示法（算法运行时间的准确界）（算法运行时间的准确界）2024/7/1129算法设计与分析因此，如果存在因此，如果存在 ，则：，则：即意味着：即意味着：f(n)=(g(n)，其中，是其中，是c大于大于0的常的常数。数。n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况无关紧要况无关紧要f(n)c2g(n)c1g(n)2024/7/1130算法设计与分析常见的多项式阶有常见的多项式阶有:O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)常见的指数阶有常见的指数阶有:2024/7/1131算法设计与分析课后练习课后练习1.算法分析题：算法分析题：1-1 求下列函数的渐近表达式：求下列函数的渐近表达式：1-2 试论试论O(1)和和O(2)的区别。的区别。1-3 按照渐近阶从低到高的顺序排列以下表按照渐近阶从低到高的顺序排列以下表达式：达式：2024/7/1132算法设计与分析课后练习课后练习1-4 假设某算法在输入规模为假设某算法在输入规模为n时的计算时间为时的计算时间为T(n)=32n。在某台计算机上实现并完成该算法的时间为。在某台计算机上实现并完成该算法的时间为t秒。秒。现有另一台计算机，其运行速度为第一台的现有另一台计算机，其运行速度为第一台的64倍，那么倍，那么在这台新机器上用同一算法在在这台新机器上用同一算法在t秒内能解输入规模多大的秒内能解输入规模多大的问题？问题？若上述算法的计算时间改进为若上述算法的计算时间改进为T(n)=n2，其余条件不变，其余条件不变，则在新机器上用则在新机器上用t秒时间能解输入规模为多大的问题？秒时间能解输入规模为多大的问题？若上述算法的计算时间进一步改为若上述算法的计算时间进一步改为T(n)=8，其余条件不变，其余条件不变，那么在新机器上用那么在新机器上用t秒时间能解输入规模多大的问题？秒时间能解输入规模多大的问题？2024/7/1133算法设计与分析课后练习课后练习1-6 对于下列各组函数对于下列各组函数f(n)和和g(n)，确定，确定f(n)=O(g(n)或或f(n)=(g(n)或或f(n)=(g(n)，并简述理由。，并简述理由。2024/7/1134算法设计与分析写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits35谢谢大家荣幸这一路，与你同行ItS An Honor To Walk With You All The Way讲师：XXXXXX XX年XX月XX日