《算法的基本概念.ppt》由会员分享，可在线阅读，更多相关《算法的基本概念.ppt（27页珍藏版）》请在三一办公上搜索。
1、1,算法设计与分析,2,Donald E.Knuth：计算机科学就是算法研究,3,在计算机科学与技术中的地位,操作系统、语言编译系统、数据库管理系统、以及各种各样的计算机应用系统软件，都用具体的算法来实现。算法的好坏，决定了所实现软件性能的优劣。在实现一个软件时，必须解决用什么方法设计算法、如何判定算法的性能。,4,目录,第一章 算法的基本概念第二章 算法的复杂性分析第三章 排序问题与离散集合的操作第四章 递归与分治第五章 贪婪法第六章 动态规划第七章 回溯第八章 分支与限界第九章 随机算法第十章 图和网络问题第十一章 计算几何问题第十二章 NP完全问题第十三章 计算复杂性第十四章 下界第十五
2、章 近似算法,5,1.1 引言,一 算法的定义和特征二 算法设计的例子三 算法的复杂性分析,6,1.算法的定义,算法是解某一特定问题的一组有穷规则的集合,“Kitb al-jabr WalmuqbJla”（复原和化简的规则）Algebra（代数）Ab Abd Allh Muhammad ibn Msa al-Khwrizm Algorithm(算法),7,2.算法的特征,1）有限性。算法在执行有限步之后必须终止。2）确定性。算法的每一个步骤，都有精确的定义。要执行 的每一个动作都是清晰的、无歧义的。3）输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。算
3、法的输入 是从特定的对象集合中抽取的。4）输出。一个算法有一个或多个输出，这些输出，和输入有 特定的关系，实际上是输入的某种函数。不同取值的输 入，产生不同结果的输出。5）能行性。算法的能行性指的是算法中有待实现的运算，都 是基本的运算。原则上可以由人们用纸和笔，在有限的时 间里精确地完成。,8,二 算法设计的例子,1.穷举法2.百鸡问题3.货郎担问题,9,1.穷举法,从有限集合中，逐一列举集合的所有元素，对每一个元素逐一判断和处理，从而找出问题的解,10,2.百鸡问题,令 a：公鸡只数 b：母鸡只数 c：小鸡只数约束方程：a+b+c=100 5a+3b+c/3=100 c%3=0a、b、c的
4、可能取值范围：0 100对在此范围内的a，b、c、的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。把问题转化为用 n 元钱买 n 只鸡，n 为任意正整数约束方程：a+b+c=n 5a+3b+c/3=n c%3=0,“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”方程求解？,编程实现,11,1）第一种解法：,输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s 1.void chicken_question(int n,int 13.,12,第一种解法的执行时间：,外循环：n+1 次，中间循环：(n+1
5、)(n+1)次，内循环：(n+1)(n+1)(n+1)次。当n=100时，内循环的循环体执行次数大于 100 万次,如何优化算法，减少执行次数？,13,2）第二种解法：,公鸡只数：a=0 n/5母鸡只数：b=0 n/3小鸡只数：c=n a b,编程实现，内循环执行次数？,14,第二种解法程序：,1.void chicken_problem(int n,int 15.16.,15,第二种解法的执行时间：,外循环：n/5+1内循环：(n/5+1)(n/3+1)当 n=100 时，内循环的循环体的执行次数为 21 34=714 次,16,3.货郎担问题,货郎担问题也叫推销商问题（traveling
6、salesman problem）,其一般提法为：有n个城市，用1，2，n表示，城i,j之间的距离为Sij，有一个货郎从城k出发到其他城市一次且仅一次，最后回到城市k，怎样选择行走路线使总路程最短？,有？条线路,17,3.货郎担问题,n 个城市共有 n!个排列，采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。,18,货郎担问题的穷举法版本,输入：城市个数 n,费用矩阵c 输出：旅行路线 t,最小费用 min 1.void salesman_problem(int n,float 14.15.,试求n=？计算时间在1年以上，假设1s处理能力为100万次,19,货郎担
7、问题穷举法版本的执行时间,20,三 算法的复杂性分析,问题一：如何设计算法，算法的设计方法。问题二：如何分析算法的效率，算法的复杂性分析。算法的效率用算法的复杂性来衡量算法的复杂性：算法的时间复杂性和算法的空间复杂性算法的时间复杂性越高，算法的执行时间越长算法的空间复杂性越高，算法所需的存储空间越多一、算法复杂性的度量？二、如何分析和计算算法的复杂性？,21,1.算法的输入规模和运行时间,令百鸡问题的第一、二两个算法，其最内部的循环体每执行一次，需1s时间。规模 第一个算法 第二个算法 n=100 的内循环次数 100万次 714次 执行时间 1s 714sn=10000的内循环次数 执行时间
8、 11天零13小时 6.7秒,22,1.算法的输入规模和运行时间,两个事实：1）算法的执行时间随问题规模的增大而增长，增长的速度 随不同的算法而不同。当问题规模较小时，不同增长速 度的两个算法，其执行时间的差别或许并不明显。而当 规模较大时，这种差别就非常大，甚至令人不能接受。2）没有一个方法能准确地计算算法的具体执行时间。（依 赖于编程语言、计算机性能、操作系统等）,23,2.算法运行时间的评估,1）计算模型：RAM模型（随机存取机模型）、图灵机 模型等2）初等操作：所有操作数都具有相同的固定字长；所 有操作的时间花费都是一个常数时间间隔。算术运 算；比较和逻辑运算；赋值运算，等等；,24,例：百鸡问题算法的时间估计,可把 写成,第一个算法：,试计算第二个算法的时间估计？,25,3、算法时间复杂性的定义,定义：设算法的执行时间，如果存在 T(n)，使得：就称 T(n)为算法的渐近时间复杂性。,26,3、算法时间复杂性的定义,27,3、算法时间复杂性的定义,表1.2 不同时间复杂性下不同输入规模的运行时间,
