算法设计与分析

1算法设计与分析-----计算机非数值算法2先修课程离散数学数据结构高级程序语言3参考资料[1]计算机算法设计与分析（第3版），王晓东，电子工业出版社配套：“算法设计与实验题解”，王晓东，电子工业出版社[2]算法设计与分析基础（IntroductiontoDesignandAnalysisofAlgorithms），潘彦译（[美]AnanyLevitin），清华大学出版社[3]算法设计技巧与分析（AlgorithmsDesignTechniquesandAnalysis），吴伟昶等译（[沙特]M.H.Alsuwaiyel），电子工业出版社[4]计算机算法基础（第2版），余祥宣、邹海明等，华中科技大学出版社课件(webcc)4上机：教学楼D506机房期末总评成绩：平时成绩40%+期末（闭卷）成绩*60%平时成绩：考勤、书面作业(含实验)课程介绍迟交作业，酌情扣分抄袭作弊，将导致记零分处理以及…！办公电话：26535255Email:[e-mail]课程内容：介绍计算机非数值算法的主要设计方法与分析技巧5课程介绍—几个例子例1：百鸡问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”穷举法6课程介绍—几个例子例2：假设正整数n、s，sn。设计算法对任一给定n位数，删除其中的s位后，使得剩下的位组成的新数最小。例：n=6s=3783259---259n=5s=224351---231贪心法7课程介绍—几个例子例3：奥运会排球比赛:预赛：A组：中国、古巴、日本、美国、波兰、委内瑞拉、B组：俄罗斯、塞尔维亚、巴西、意大利、哈萨克斯坦、阿尔及利亚1/4决赛、1/2决赛：古vs美、中vs巴分治法8课程介绍—几个例子例4：八后问题:在8*8的棋盘上，每行放置一个皇后，要求它们不能在同一列，同一斜线上。回溯法9课程介绍—本课程学习的算法穷举法—百鸡问题递归和分治—二分查找、快速排序贪心法—最小生成树、最短距离回溯—迷宫、八后问题动态规划分支与限界常用算法10教学内容与进度第1章算法引论3学时；第2章常用的数学工具3学时；第4章递归与分治5学时；实验1第5章贪心算法4学时；第6章动态规划6学时；实验2第7章回溯法5学时；实验3第8章分支限界法5学时；第12-13章NP完全问题及计算复杂性3学时常用算法11教学内容第12-13章简单介绍了NP完全性理论和计算复杂性，这是当前计算机算法领域的热门研究课题，具有很高的理论价值。P类和NP类问题NP完全问题计算模型复杂性类型之间的关系12第一章算法的基本概念程序=算法+数据结构算法设计与分析是计算机科学与技术的一个核心内容….131.1引言算法设计与分析在《计算机科学与技术》专业中的地位为什么要学习算法?–理论角度:“算法不仅是计算机科学的一个分支,它更是计算机科学的核心。而且,可以毫不夸张地说,它和绝大多数的科学̀、商业和技术都是相关的。”_«算法:计算的灵魂»,DavidHarel–实践角度:–开发分析能力:14计算机专业课程群建设自然科学基础课程群计算机科学理论课程群计算机硬件课程群软件基础课程群15*组合数学*形式语言与自动机*模糊数学*数理逻辑算法设计与分析Ⅰ*可计算性理论*算法分析Ⅱ计算复杂性理论离散数学其中：*为研究生课程计算机科学理论基础计算机科学理论课程群数据结构161.1引言算法设计与分析在《计算机科学与技术》专业中的地位为什么要学习算法?–理论角度–实践/工程角度:了解计算机领域中不同问题的一系列标准算法;具备设计新算法和分析其效率的能力。多、快、好、省与少、慢、差、费–开发分析能力:“算法是一种一般性的智能工具，一定有助于我们对其他学科的理解，…为什么算法会有这种作用呢？我们可以这样理解：人们常说，一个人只有把知识教给“计算机”，才能“真正掌握它，也就是说，将知识表述为一种算法，…比起简单地按照常规去理解事物，用算法将其形式化会使我们获得更加深刻的理解。”_DonaldKnuth，1974图灵奖的获得者。171.1引言算法定义定义1.1：算法问题求解的有效策略.是解某一特定问题的一组有穷规则的集合。算法特征有限性、确定性、输入、输出、能行性实用算法对有限性要求运行时间是可接受的。18算法设计与分析的步骤若一问题是可解的,则求解的全过程由以下阶段构成(算法设计与分析的步骤):1.问题的陈述2.选择模型或设计模型=选择模型或设计模型3.设计算法(选择)和确认=设计算法(选择)和确认4.分析算法=分析算法5.程序实现=步骤的含义:一个好的算法是反复努力和重新修正的结果设计算法是一个非常有创造性和非常值得付出的过程.课程的目的就是想证明这个事实.191.1引言算法设计的例子—穷举法穷举法：是从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，找出问题的解。20例1.1百鸡问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”这里讨论更一般的n钱买n鸡问题.穷举法实例问题的陈述21解：设鸡翁、鸡母、鸡雏分别为a,b,c只。①测试集合：0≤a≤n0≤b≤n0≤c≤n判断条件：a+b+c=n5*a+3*b+c/3=n且c%3=0穷举法实例—百鸡问题选择模型或设计模型设计算法•算法描述如下：22输入：n输出：满足问题的解数目k,公鸡、母鸡、小鸡的只数g[]、m[]、s[]voidchilden_question(intn,int&k,intg[],intm[],ints[]);穷举法实例—百鸡问题设计算法23voidchilden_question(intn,int&k,intg[],intm[],ints[]){inta,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){g[k]=a;m[k]=b;s[k]=c;k++;}}执行时间：循环次数，(n+1)*(n+1)*(n+1)算法1.1设计算法•算法的复杂性分析24②测试集合：0≤a≤n/50≤b≤n/3c=n-a-b判断条件：5*a+3*b+c/3=n且c%3=0算法描述如下(算法1.2)：穷举法实例—百鸡问题25voidchilden_question(intn,int&k,intg[],intm[],ints[]){1inta,b,c;2intn1=n/5,n2=n/3;k=0;//53for(a=0;a=n1;a++)//1+2(n/5+1)4for(b=0;b=n2;b++)//n/5+1+2(n/5+1)(n/3+1)5{6c=100-a-b;//3(n/5+1)(n/3+1)7if(!(c%3)&&5*a+3*b+c/3==n)8{//10(n/5+1)(n/3+1)9g[k]=a;m[k]=b;s[k]=c;10k++;//4(n/5+1)(n/3+1)11}12}}运行时间：循环次数，(n/5+1)*(n/3+1)算法1.2•算法的复杂性分析26例1.2货郎担问题：某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行线路使每个城市仅经过一次，最后回到原出发城市，而总路程最短。穷举法实例—货郎担问题27解：假设n个城市，分别用1到n的数字编号，问题归结为在有向网中(顶点表示城市,弧上权重表示距离)，寻找一条路径最短，n个城市仅经过一次的回路(哈密尔顿回路)。测试集合：1,…,n的排列对应一条回路,如2356…n12全部排列构成测试集合穷举法实例—货郎担问题28判断条件：选择排列中路径和最小的回路。假设用邻接矩阵c存储网，算法描述如下：输入：城市数n,c[][]输出：最短距离min，旅行路线t[]voidsalesman_problem(intn,floatmin,intt[],floatc[][]);穷举法实例—货郎担问题29voidsalesman_problem(intn,floatmin,intt[],floatc[][]);{intp[n],i=1,m=n!;floatcost;min=MAX_FLOAT_NUM;while(i=m){产生n个城市的第i个排列于p;cost=回路p的权重和；if(costmin){min=cost;p复制至t;}i++;}}运行时间：循环次数，n!算法1.330表1.1算法1.3的执行时间随n的增长而增长的情况nn!nn!nn!nn!5120μs9362ms131.72h1711.27year6720μs103.62s1424h18203year75.04ms1139.9s1515day193857year840.3ms12479.0s16242day2077146year注：表1.1假设算法1.3中while循环体执行一次需1μs。对某类特定问题，穷举法只适用于规模较小的情况。穷举法实例—货郎担问题31ACM与算法设计1、穷举法如求素数、百钱百鸡问题2、分治法如汉诺塔问题、折半查找算法、快速排序算法3、贪心法如：哈夫曼算法、最小生成树、最短路径算法找硬币问题32ACM与算法设计4、回溯法如全排列问题、迷宫、N后问题5、动态规划法6、分支限界法如货郎担问题、作业分配问题如货郎担问题、最短路径、资源分配问题33（1）如何设计算法；……（2）如何评价算法的效率……时间复杂性：算法的执行时间空间复杂性：算法所需的存储空间算法设计目标：时间复杂性、空间复杂性低1.1引言—算法的复杂性分析主要341.2算法的时间复杂性算法的输入规模和运行时间的阶算法的执行时间随问题规模的增大而增大，故常用关于问题规模n的函数估算算法在大规模问题时的运行时间。35运行时间T(n)的估算运行时间T(n)的估算假设初等操作计算模型：所有操作数都具有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。如：算术运算；比较和逻辑运算；赋值运算(含遍历表和指针赋值）等。例1.3估算算法1.1的运行时间T1(n)。36voidchilden_question(intn,int&k,intg[],intm[],ints[]){inta,b,c;k=0;//1for(a=0;a=n;a++)//1+2(n+1)for(b=0;b=n;b++)//n+1+2(n+1)2for(c=0;c=n;c++)//(n+1)2+2(n+1)3if(!(c%3)&&a+b+c==n&&//14(n+1)35*a+3*b+c/3==n){g[k]=a;m[k]=b;s[k]=c;k++;//4(n+1)3}}算法1.1赋值等运算（初等操作）37T1(n)≤1+1+2(n+1)+n+1+2(n+1)2+(n+1)2+2(n+1)3+14(n+1)3+4(n+1)3=20n3+64n2+72n+31(1.1)当n增大时，算法1.1的执行时间取决于式(1.1)的第一项，为方便，定义算法的渐进时间复杂性。算法1.1的运行时间T(n)的估算初等操作38算法的渐进时间复杂性T*(n)定义1.2设算法的执行时间为T(n)，如果存在T*(n)，使得：（1.2）就称T*(n)为算法的渐近时间复杂性。0)()()(lim*nTnTnTn渐进时间复杂性T*(n)即T(n)-T*(n)是T(n)的高阶无穷小。39例1.4：给出算法1.1的渐进时间复杂性T1*(n)。解：T1*(n)=c1n3c1=200T1*(n)的阶是3。实际中，通常用渐进时间复杂性衡量一个算法的时间复杂性。练习1.1：估算算法1.2的和T2*(n)，并说明T2*(n)的阶。渐进时间复杂性T*(n)T2(n)=19n2/15+164n/15+30T1(n)≤20n3+64n2+72n+3140常用的有:logn、n、nlogn、n2、n3、2n当n足够大时，lognnnlognn