第一章 算法的基本概念(新).ppt

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

1、算法设计与分析算法设计与分析信工计算机系信工计算机系2008上机：办公楼上机：办公楼2楼机房楼机房期末成绩：期末成绩：(平时成绩平时成绩+实验成绩实验成绩)*3040%+期末成绩期末成绩*7060%平时成绩：考勤、书面作业平时成绩：考勤、书面作业答疑信箱：答疑信箱：课程内容：讲解计算机算法的主要设计方法与分课程内容：讲解计算机算法的主要设计方法与分析技巧析技巧课程介绍课程介绍课程介绍课程介绍几个例子几个例子例例1：百鸡问题百鸡问题：“鸡翁一，值钱五；鸡母一，鸡翁一，值钱五；鸡母一，值值 钱三；鸡雏三，值钱一。百钱买百鸡，问鸡钱三；鸡雏三，值钱一。百钱买百鸡，问鸡 翁、母、雏各几何？翁、母、雏各

2、几何？”穷举法穷举法课程介绍课程介绍几个例子几个例子例2：假设正整数假设正整数n、s，s 259 n=5 s=2 24351 -231 贪心法贪心法课程介绍课程介绍几个例子几个例子例3：奥运会排球比赛奥运会排球比赛:预赛：预赛：A组：中国、古巴、日本、美国、波组：中国、古巴、日本、美国、波 兰、委内瑞拉、兰、委内瑞拉、B组：俄罗斯、塞尔维亚、巴西、意大组：俄罗斯、塞尔维亚、巴西、意大 利、哈萨克斯坦、阿尔及利亚利、哈萨克斯坦、阿尔及利亚 1/4决赛、决赛、1/2决赛：古决赛：古 vs 美、中美、中 vs 巴巴分治分治课程介绍课程介绍几个例子几个例子例例4：八后问题：八后问题:在在8*8的棋盘上

3、，每行放置的棋盘上，每行放置 一个皇后，要求它们不能在同一列，一个皇后，要求它们不能在同一列，同一斜线上。同一斜线上。回溯回溯课程介绍课程介绍本课学习的算法本课学习的算法l穷举法穷举法 百鸡问题百鸡问题l递归和分治递归和分治 二分查找、快速排序二分查找、快速排序l贪心法贪心法 最小生成树、最短距离最小生成树、最短距离l回溯回溯 迷宫、八后问题迷宫、八后问题l动态规划动态规划l分支与限界分支与限界第一章第一章 算法的基本概念算法的基本概念 程序程序=算法算法+数据结构数据结构 算法设计与分析是计算机科学与技术的一个算法设计与分析是计算机科学与技术的一个 核心内容核心内容1.1 引言引言算法定义算

4、法定义 定义定义1.1：算法是解某一特定问题的一组有：算法是解某一特定问题的一组有 穷规则的集合。穷规则的集合。算法特征算法特征 有限性、确定性、输入、输出、能行性有限性、确定性、输入、输出、能行性 实用算法对有限性要求运行时间是可接受的。实用算法对有限性要求运行时间是可接受的。1.1 引言引言算法设计的例子算法设计的例子穷举法穷举法 穷举法：穷举法：是从有限集合中，逐一列举集合是从有限集合中，逐一列举集合 的所有元素，对每一个元素逐一判断和处的所有元素，对每一个元素逐一判断和处 理，找出问题的解。理，找出问题的解。例例1.1 百鸡问题百鸡问题：“鸡翁一，值钱五；鸡母一，鸡翁一，值钱五；鸡母一

5、，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡 翁、母、雏各几何？翁、母、雏各几何？”这里讨论更一般的这里讨论更一般的n钱买钱买n鸡问题鸡问题.穷举法实例穷举法实例解：设鸡翁、鸡母、鸡雏分别为解：设鸡翁、鸡母、鸡雏分别为a,b,c只。只。测试集合：测试集合：0an 0bn 0cn 判断条件：判断条件：a+b+c=n 5*a+3*b+c/3=n 且且 c%3=0 算法描述如下：算法描述如下：穷举法实例穷举法实例百鸡问题百鸡问题 输入：输入：n 输出：满足问题的解数目输出：满足问题的解数目k,公鸡、母鸡、小鸡的公鸡、母鸡、小鸡的 只数只数g、m、s void c

6、hilden_question(int n,int&k,int g,int m,int s);穷举法实例穷举法实例百鸡问题百鸡问题void childen_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(!(c%3)&a+b+c=n&5*a+3*b+c/3=n)gk=a;mk=b;sk=c;k+;执行时间：循环次数，执行时间：循环次数，执行时间：循环次数，执行时间：循环次数，(n+1)*(n+1)*(n+1)(n+1)*(n+1)*(n+1)

7、算法算法算法算法1.11.1 测试集合：测试集合：0an/5 0bn/3 c=n-a-b 判断条件：判断条件：5*a+3*b+c/3=n 且且 c%3=0 算法描述如下算法描述如下(算法算法1.2)：穷举法实例穷举法实例百鸡问题百鸡问题void childen_question(int n,int&k,int g,int m,int s)1 int a,b,c;2 int n1=n/5,n2=n/3;k=0;3 for(a=0;a=n1;a+)4 for(b=0;b=n2;b+)5 6 c=100-a-b;7 if(!(c%3)&5*a+3*b+c/3=n)8 9 gk=a;mk=b;sk=c

8、;10 k+;11 12 运行时间：循环次数，运行时间：循环次数，运行时间：循环次数，运行时间：循环次数，(n/5+1)*(n/3+1)(n/5+1)*(n/3+1)算法算法算法算法1.21.2 例例1.2 货郎担问题货郎担问题：某售货员要到若干个城：某售货员要到若干个城市销售货物，已知各城市之间的距离，要市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行线路使每求售货员选择出发的城市及旅行线路使每个城市仅经过一次，最后回到原出发城市，个城市仅经过一次，最后回到原出发城市，而总路程最短。而总路程最短。穷举法实例穷举法实例货郎担问题货郎担问题解：解：假设假设n个城市，分别用个城市，

9、分别用1到到n的数字编号，的数字编号，问题归结为在有向网中问题归结为在有向网中(顶点表示城市顶点表示城市,弧上弧上 权重表示距离权重表示距离)，寻找一条路径最短，寻找一条路径最短，n个城个城 市仅经过一次的回路市仅经过一次的回路(哈密尔顿回路哈密尔顿回路)。测试集合：测试集合：1,n的排列对应一条回路的排列对应一条回路,如如2356n12 全部排列构成测试集合全部排列构成测试集合 穷举法实例穷举法实例货郎担问题货郎担问题判断条件：判断条件：选择排列中路径和最小的回路。选择排列中路径和最小的回路。假设用邻接矩阵假设用邻接矩阵c存储网，算法描述如下：存储网，算法描述如下：输入：城市数输入：城市数n

10、,c输出：最短距离输出：最短距离min，旅行路线，旅行路线tvoid salesman_problem(int n,float&min,int t,float c);穷举法实例穷举法实例货郎担问题货郎担问题void salesman_problem(int n,float&min,int t,float c);int pn,i=1,m=n!;float cost;min=MAX_FLOAT_NUM;while(i=m)产生产生n个城市的第个城市的第i个排列于个排列于p;cost=回路回路p的权重和；的权重和；if(cost min)min=cost;p复制至复制至t;i+;运行时间：循环次数，

11、运行时间：循环次数，运行时间：循环次数，运行时间：循环次数，n!n!算法算法算法算法1.31.3表1.1 算法1.3的执行时间随n的增长而增长的情况nn!nn!nn!nn!5120ss9362ms131.72h1711.27year6720ss103.62s1424h18203year75.04ms1139.9s1515day193857year840.3ms12479.0s16242day2077146year注：表注：表1.1假设算法假设算法1.3中中while循环体执行一次需循环体执行一次需1s。对某类特定问题，穷举法只适用于规模较小的情况。对某类特定问题，穷举法只适用于规模较小的情况。

12、穷举法实例穷举法实例货郎担问题货郎担问题（1）如何设计算法；）如何设计算法；（2）如何评价算法的效率）如何评价算法的效率 时间复杂性：时间复杂性：算法的执行时间算法的执行时间 空间复杂性：空间复杂性：算法所需的存储空间算法所需的存储空间 算法设计目标：算法设计目标：时间复杂性、空间复杂性低时间复杂性、空间复杂性低 练习练习1.1：P29 1、31.1 引言引言 算法的复杂性分析算法的复杂性分析1.2 算法的时间复杂性算法的时间复杂性 算法的输入规模和运行时间的阶算法的输入规模和运行时间的阶 算法的执行时间随问题规模的增大而增大，故算法的执行时间随问题规模的增大而增大，故 常用关于问题规模常用关

13、于问题规模n的函数估算算法在大规模问的函数估算算法在大规模问题时的运行时间。题时的运行时间。运行时间运行时间T(n)的估算的估算p运行时间运行时间T(n)的估算的估算 假设初等操作计算模型：所有操作数都具有相同假设初等操作计算模型：所有操作数都具有相同的固定字长；所有操作的时间花费都是一个常数的固定字长；所有操作的时间花费都是一个常数时间间隔。如算术运算；比较和逻辑运算；赋值时间间隔。如算术运算；比较和逻辑运算；赋值运算等。运算等。例例1.3 估算算法估算算法1.1的运行时间的运行时间T1(n)。void childen_question(int n,int&k,int g,int m,int

14、 s)int a,b,c;k=0;/1/1 for(a=0;a=n;a+)/2(n+2)/2(n+2)for(b=0;b=n;b+)/2(n+2)(n+1)/2(n+2)(n+1)for(c=0;c0 T1*(n)的阶是3。实际中，通常用渐进时间复杂性衡量一个算法的实际中，通常用渐进时间复杂性衡量一个算法的 时间复杂性。时间复杂性。练习练习1.2：估算算法估算算法1.2的的T2(n)和和T2*(n)，并说，并说 明明T2*(n)的阶。的阶。渐进时间复杂性渐进时间复杂性T*(n)19n2/15+164n/15+30常用的有常用的有:logn、n、nlogn、n2、n3、2n 当当n足够大时，足够

15、大时，logn n nlogn n2 n3 0;i-)value=value*x+Ai-1;return value;算法算法算法算法1.41.4按初等操作计算模型分析算法按初等操作计算模型分析算法1.41.4的执行时间：的执行时间：算法算法1.4的循环次数是的循环次数是n次，与次，与T(n)的阶相同，均为的阶相同，均为分析复杂性时，只需分析算法中的循环次数的阶。分析复杂性时，只需分析算法中的循环次数的阶。时间复杂性分析时间复杂性分析 循环次数统计例循环次数统计例练习练习1.2:1.2:分析下列算法的时间复杂性分析下列算法的时间复杂性.输入：数组输入：数组A，元素个数，元素个数n输出：按递增顺

16、序排列的数组输出：按递增顺序排列的数组A时间复杂性分析时间复杂性分析 循环次数统计例循环次数统计例void swap(int&x,int&y)int temp;temp=x;x=y;y=temp;基本操作频度的统计基本操作频度的统计 计算步的统计计算步的统计(自学，简单了解）自学，简单了解）void bubble(int A,int n)int i,k;for(k=n-1;k0;k+)for(i=0;iAi+1)swap(Ai,Ai+1);时间复杂性分析时间复杂性分析 循环次数统计例循环次数统计例(n(n2 2)有些算法的运行时间除与问题规模有关外，还与输有些算法的运行时间除与问题规模有关外，

17、还与输入元素的初始排列顺序有关。因此，有入元素的初始排列顺序有关。因此，有3种分析方法：种分析方法：最好情况：最好情况：最好情况：最好情况：依据输入元素顺序，算法所达到的最短运依据输入元素顺序，算法所达到的最短运行时间。行时间。最坏情况：最坏情况：最坏情况：最坏情况：依据输入元素顺序，算法所达到的最长运依据输入元素顺序，算法所达到的最长运行时间。行时间。平均情况：平均情况：平均情况：平均情况：算法的运行时间取算法所有可能输入的平算法的运行时间取算法所有可能输入的平均运行时间。均运行时间。最好情况、最坏情况、平均情况分析最好情况、最坏情况、平均情况分析练习练习1.41.4：分析下列算法的最好情况

18、、最坏情况、分析下列算法的最好情况、最坏情况、平均情况的时间复杂性平均情况的时间复杂性.输入：输入：数组数组A，元素个数，元素个数n输出：输出：按递增顺序排列的数组按递增顺序排列的数组A最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例void insert_sort(int A,int n)int a,i,j;for(i=1;i=0&Aja)Aj+1=Aj;j-;Aj+1=a;最好情况：最好情况：最坏情况：最坏情况：最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例平均情况：平均情况：假设元素在各位置的插入概率相等。假设元素在各位置的插入概率相等。设前设前

19、i-1个元素排好序，现插入第个元素排好序，现插入第i个元素。个元素。第第i个元素的插入位置有个元素的插入位置有i个，对应的比较次数为个，对应的比较次数为i-1、i-1、i-2、1。因此插入第。因此插入第i个元素的平均比较个元素的平均比较次数为：次数为：最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例最好情况、最坏情况、平均情况分析例直插算法要插入第直插算法要插入第2,3,.,n个元素，因此平均个元素，因此平均比较总次数为：比较总次数为：平均情况下的时间复杂性是平均情况下的时间复杂性是(n(n2 2)。1.4 算法的空间复杂性分析算法的空间复

20、杂性分析算法的空间复杂性，指的是为解一个问题实例而需算法的空间复杂性，指的是为解一个问题实例而需要的存储空间。有两种分析方法：要的存储空间。有两种分析方法：算法所需的工作空间算法所需的工作空间 不包含存储输入数据、程序代码和常数的空间，不包含存储输入数据、程序代码和常数的空间，仅包含算法函数体内新生成的变量空间。仅包含算法函数体内新生成的变量空间。算法在运行时所占用的内存空间的总和（自学，算法在运行时所占用的内存空间的总和（自学，简单了解）简单了解）例：例：分析分析练习练习1.4中算法的空间复杂性中算法的空间复杂性。解：需要为3个变量a,i,j分配空间，因此算法的空间 复杂性是(1)。1.4

21、算法的空间复杂性分析算法的空间复杂性分析1.5 最优算法最优算法对解同一问题的多个算法，最优算法是指具有最小时对解同一问题的多个算法，最优算法是指具有最小时间复性的算法。间复性的算法。具有最优复杂性的算法都称为最优算法。具有最优复杂性的算法都称为最优算法。最优算法中的各算法按高阶系数判断最短执行时间。最优算法中的各算法按高阶系数判断最短执行时间。本章重点本章重点掌握简单的算法设计掌握简单的算法设计穷举法穷举法掌握复杂性度量的掌握复杂性度量的了解复杂性的偏序关系了解复杂性的偏序关系掌握用循环计数法和基本操作频度法分析算法的时掌握用循环计数法和基本操作频度法分析算法的时间复杂性，包括最坏、最好、平均情况分析间复杂性，包括最坏、最好、平均情况分析了解工作空间法分析算法的空间复杂性了解工作空间法分析算法的空间复杂性