程序设计算法概述.ppt

算法概述算法概述算法概述算法概述杨秋妹杨秋妹杨秋妹杨秋妹程序程序=数据结构数据结构+算法算法乘汽车旅行的人总希望找出到目的地的乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，在图上标出每对十字路口之间的距离，如何找出这一最短行程？如何找出这一最短行程？建立解题模型建立解题模型数据结构数据结构解决方法解决方法什么是算法什么是算法算算法法是是一一个个有有穷穷的的解解决决问问题题的的指指令令序序列列。每每条条指指令令都都必必须须有有清清楚楚的的含含义义并并且且在在有有穷长的时间内用有穷的动作完成。穷长的时间内用有穷的动作完成。一个算法无论接受任何输入，都必须在一个算法无论接受任何输入，都必须在有穷步内停止。有穷步内停止。排序问题排序问题输入：由输入：由n个数构成的一个序列个数构成的一个序列输出：对输入序列的一个排列（重排）输出：对输入序列的一个排列（重排），使得，使得a1=a2=an算法：插入排序，冒泡排序，快速排序，算法：插入排序，冒泡排序，快速排序，合并排序等合并排序等算法的几个特性算法的几个特性算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。满足性质：满足性质：(1)输入：有零个或多个外部提供的量作为算法的输入。输入：有零个或多个外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。行每条指令的时间也是有限的。什么是程序什么是程序程序是算法用某种程序设计语言的具体程序是算法用某种程序设计语言的具体实现实现程序可以不满足算法的有穷性程序可以不满足算法的有穷性算法的描述算法的描述自然语言；自然语言；程序设计语言；程序设计语言；类程序语言类程序语言常用的算法设计方法常用的算法设计方法递归法（递归法（Recursion）分治法分治法(Divide-and Conquer)、贪心法贪心法(Greedy)动态规划动态规划(Dynamic Programming)、回溯（回溯（Backtracking）分支限界法（分支限界法（Branch and Bound）近似算法近似算法(Approximation)算法的设计目标算法的设计目标算法应易于理解、编程和调试算法应易于理解、编程和调试算法应尽可能有效地利用计算机的资源，算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行特别地，应尽可能快地运行好算法的判断标准好算法的判断标准1.正确性正确性2.健壮性健壮性3.时间复杂性时间复杂性4.空间复杂性空间复杂性5.可读性可读性6.灵活性（灵活性（Flexibility）、可重用性）、可重用性(Reuseabale)等等算法复杂度分析算法复杂度分析算法复杂度分析算法复杂度分析算法复杂性算法复杂性体现在运行该算法所需要的计算机资源体现在运行该算法所需要的计算机资源多少上多少上所需资源越多，该算法的复杂性越高所需资源越多，该算法的复杂性越高所需资源越少，该算法的复杂性越低所需资源越少，该算法的复杂性越低时间复杂性：算法执行需要的时间资源时间复杂性：算法执行需要的时间资源空间复杂性：算法执行需要的空间资源空间复杂性：算法执行需要的空间资源百鸡问题百鸡问题公元公元5世纪末世纪末,我国古代数学家张丘建在我国古代数学家张丘建在他所撰写的他所撰写的算经算经中，提出了这样的中，提出了这样的一个问题：一个问题：“鸡翁一，值钱五；鸡母一，鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？问鸡翁、母、雏各几何？”a：公鸡数：公鸡数 b：母鸡数：母鸡数 c：小鸡数：小鸡数a+b+c=1005a+3b+c/3=100c%3=0void chicken_question(int n,int&k,int g,int m,int s)int a,b,c;k=0;for(a=0;a=n;a+)for(b=0;b=n;b+)for(c=0;c=n;c+)if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+;算法有三重循环算法有三重循环内循环体的执行次数为内循环体的执行次数为(n+1)(n+1)(n+1)void chicken_problem(int n,int&k,int g,int m,int s)int i,j,a,b,c;k=0;i=n/5;j=n/3;for(a=0;a=i;a+)for(b=0;b=j;b+)c=n-a-b;if(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+;算法有两重循环算法有两重循环内循环体执行次数为内循环体执行次数为(n/5+1)(n/3+1)货郎担问题货郎担问题货郎担问题是一个经典问题。某售货员货郎担问题是一个经典问题。某售货员要到若干个城市销售货物，已知各城市要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最次，最后回到原出发城市，而总路程最短。短。用图的顶点代表城市，边的权重表示城用图的顶点代表城市，边的权重表示城市间的距离，这个问题可以转化为求一市间的距离，这个问题可以转化为求一个图的最短哈密顿回路个图的最短哈密顿回路哈密顿回路可以定义为哈密顿回路可以定义为n1个相邻节点个相邻节点vi0,vin-1,vi0的一个序列的一个序列可以通过生成可以通过生成n1个中间城市的组合来个中间城市的组合来得到所有的旅行路线，计算这些路线的得到所有的旅行路线，计算这些路线的长度，然后求得最短的线路长度，然后求得最短的线路算法时间复杂度算法时间复杂度 O（n！）！）nn!nn!nn!nn!5120s 9362ms131.72h1711.27year6720s 103.62s1424h18203year75.04ms1139.9s1515day 193857year840.3ms12479s16242day2077146year对于所设计的算法，如何说明它是有效对于所设计的算法，如何说明它是有效的？的？如果对于同一问题，有多个不同的解法，如果对于同一问题，有多个不同的解法，如何知道哪一个算法更有效？如何知道哪一个算法更有效？算法复杂性分析目的在于选择合适的算算法复杂性分析目的在于选择合适的算法和改进算法法和改进算法实验测量法（实际执行时间、执行指实验测量法（实际执行时间、执行指令的条数）令的条数）把算法用某种程序设计语言实现并在计把算法用某种程序设计语言实现并在计算机上运行，计算实际运行时间算机上运行，计算实际运行时间如何进行算法时间效率分析如何进行算法时间效率分析例：让一台更快的、运行插入排序的计例：让一台更快的、运行插入排序的计算机（计算机算机（计算机A）与一台较慢的、运行）与一台较慢的、运行合并排序的计算机（计算机合并排序的计算机（计算机B）进行比较。）进行比较。两者都要对一个大小为一百万个数的数两者都要对一个大小为一百万个数的数组进行排序。假设计算机组进行排序。假设计算机A每秒能执行每秒能执行10亿条指令，而计算机亿条指令，而计算机B每秒只能执行每秒只能执行一千万条指令。一千万条指令。计算机计算机A花费的时间：花费的时间：2*（106）2条指令条指令/109条指令条指令/秒秒2000秒秒计算机计算机B花费的时间：花费的时间：50*106lg106条指令条指令/107条指令条指令/秒秒100秒秒影响实验测量时间的因素影响实验测量时间的因素程序的输入长度程序的输入长度编译程序生成目标代码的质量编译程序生成目标代码的质量计算机指令的质量和速度计算机指令的质量和速度算法本身的优劣算法本身的优劣实验测量法（实际执行时间、执行指实验测量法（实际执行时间、执行指令的条数）令的条数）缺点：缺点：必须先运行根据算法编制的的程序；必须先运行根据算法编制的的程序；所得的时间统计量依赖于计算机的硬件、软所得的时间统计量依赖于计算机的硬件、软件等环境因素，容易掩盖算法本身的优劣。件等环境因素，容易掩盖算法本身的优劣。事前分析事前分析(估计估计)法法忽略机器性能对运行时间的影响忽略机器性能对运行时间的影响使用问题输入规模为参数的函数来衡量使用问题输入规模为参数的函数来衡量选定输入规模选定输入规模规模越大，需要的运行时间越长规模越大，需要的运行时间越长使用以算法输入规模使用以算法输入规模n为参数的函数为参数的函数T（n）研究算法效率）研究算法效率运行时间的度量单位运行时间的度量单位找出算法中最重要的操作找出算法中最重要的操作基本操作，基本操作，计算它们的运行次数计算它们的运行次数基基本本操操作作通通常常是是算算法法最最内内层层循循环环中中最最费费时的操作时的操作例：例：A A是一个由是一个由n n个不同元素的实数数组，给出个不同元素的实数数组，给出求其最大和最小元素的算法和时间复杂性求其最大和最小元素的算法和时间复杂性void void MinMax(doubleMinMax(double A,A,intint n,double n,double max,double min)max,double min)double max,min;double max,min;max=min=A0;max=min=A0;for(k=1;k=n-1;k+)for(k=1;kmax)max=max)max=AkAk;if(if(AkAkmin)min=min)min=AkAk;T（n）2（n1）评价算法运行时间的标准评价算法运行时间的标准最好时间复杂度最好时间复杂度算法对具有长度为算法对具有长度为n的任何输入的最短运行时的任何输入的最短运行时间间最坏时间复杂度最坏时间复杂度算法对具有长度为算法对具有长度为n的任何输入的最长运行时的任何输入的最长运行时间间平均时间复杂度平均时间复杂度在平均输入下，算法的运行时间。通常假设给在平均输入下，算法的运行时间。通常假设给定长度的各种输入概率相同。定长度的各种输入概率相同。例例:A是一个由是一个由n个不同元素的实数数组，个不同元素的实数数组，给出确定给定实数给出确定给定实数K是否在是否在A中的算法及中的算法及其时间复杂性其时间复杂性SequentialSearch(A0n-1,K)i=0while i n and Ai!=K doi=i+1if i maxvalmaxval=Aireturn maxval n-1 T(n)=1=n-1 i=1=O(n)分析非递归算法效率的通分析非递归算法效率的通用方案用方案决定用哪个（哪些）参数作为输入规模的度量决定用哪个（哪些）参数作为输入规模的度量找出算法的基本操作找出算法的基本操作检查基本操作的执行次数是否只依赖输入规模，检查基本操作的执行次数是否只依赖输入规模，如果还依赖其他特性则应区分最差、平均及最如果还依赖其他特性则应区分最差、平均及最优效率优效率建立算法基本操作执行次数的求和公式建立算法基本操作执行次数的求和公式对求和公式求解，至少应确定其增长次数对求和公式求解，至少应确定其增长次数递归算法的分析递归算法的分析一个过程在运行时直接或间接地调用自一个过程在运行时直接或间接地调用自己，则该过程称为递归程序己，则该过程称为递归程序例：计算阶乘函数例：计算阶乘函数F（n）F(n)if n=0 return 1else return F(n-1)*n时间复杂度递归公式时间复杂度递归公式(乘法步数乘法步数)T(n)=T(n-1)+1(n0)T(0)=0T(n)=n=O(n)例：归并排序例：归并排序msort(int x,int aux,int s,int t)/*将将xs.t归并排序为归并排序为auxs.t*/if(s=t)auxs=xs;else m=(s+t)/2;msort(x,aux,s,m);msort(x,aux,m+1,t);merge(aux,x,s,m,t);时间复杂度递归公式时间复杂度递归公式T(n)=2T(n/2)+n(n0)T(1)=1T(n)=O(nlogn)分析递归算法效率的通用分析递归算法效率的通用方案方案决定用哪个（哪些）参数作为输入规模的度量决定用哪个（哪些）参数作为输入规模的度量找出算法的基本操作找出算法的基本操作检查基本操作的执行次数是否只依赖输入规模，检查基本操作的执行次数是否只依赖输入规模，如果还依赖其他特性则应区分最差、平均及最如果还依赖其他特性则应区分最差、平均及最优效率优效率对算法基本操作的执行次数建立一个递推关系对算法基本操作的执行次数建立一个递推关系式以及相应的初始条件式以及相应的初始条件求解递归关系式，至少确定其增长次数求解递归关系式，至少确定其增长次数基本的效率类型基本的效率类型常数、对数、线性、常数、对数、线性、nlogn、平方、平方、立方、指数、阶乘立方、指数、阶乘运行时间为运行时间为n的多项式的算法称为好算法的多项式的算法称为好算法nlognnNlognn2N32nn!103.3103.3*10 1021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*104106109104131041.3*1051081012105171051.7*10610101015算法设计的几个原则算法设计的几个原则如果一个程序只用一、两次，那么书写如果一个程序只用一、两次，那么书写和调试所用的时间比运行程序时间大得和调试所用的时间比运行程序时间大得多，因而算法应易于理解和正确实现多，因而算法应易于理解和正确实现如果一个算法只对小的输入运行，运行如果一个算法只对小的输入运行，运行时间增长率比运行时间前面的常数因子时间增长率比运行时间前面的常数因子显得不重要，可选常数因子小，而增长显得不重要，可选常数因子小，而增长率大的算法率大的算法例：有两个算法运行时间分别为例：有两个算法运行时间分别为T1（n）100n2，T2（n）5n3，问哪个算法比较好？问哪个算法比较好？一个复杂而有效的算法可能不利于维护，一个复杂而有效的算法可能不利于维护，有时应选择简单而相对低效的算法有时应选择简单而相对低效的算法时间复杂度小的算法，空间复杂度可能时间复杂度小的算法，空间复杂度可能很大很大对数值算法而言，精度和稳定性与时间对数值算法而言，精度和稳定性与时间高效性一样重要高效性一样重要练习练习试分析下面的程序段所需计算时间的上试分析下面的程序段所需计算时间的上界和下界。界和下界。while(n 1)if(odd(n)n=3*n+1;elsen=n/2;