《算法设计与分析优秀》由会员分享，可在线阅读，更多相关《算法设计与分析优秀（78页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析主讲教师：刘春凤天津大学计算机系课程安排n课程安排n学生成绩评定方法：笔试+上机作业n上课时间: 周二，3,4节，周四，5,6节n上课地点：23-204nSlides download from: ftp:/59.67.33.8/learn/cfliu/ Algorithm_2009Spring 匿名登录匿名登录主要参考书目nSartaj Sahni， Data Structures, Algorithms, and Applications in C+， 机械工业出版社，2000 （影印版）nSartaj Sahni著，汪诗林等译，数据结构、算法与应用-C+语言描述，机械工业出
2、版社，2003 （翻译版）nT. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms (the second edition)，The MIT Press，2001算法导论（第二版）（影印版，中文本），高等教育出版社，2003 第1章 算法在计算中的应用n什么是算法？n为什么要对算法进行研究？n相对于计算机中使用的其他技术来讲，算法的作用是什么？ 算法的定义算法（algorithm）是定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。算法是一系列的计算步骤，
3、用来将输入数据转换成输出结果。算法是一种工具，用来解决一个具有良好规格说明的计算问题。 例1：将一列数按非降序进行排列n形式化描述：输入：由n个数构成一个序列(a1, a2, ,an)输出：对输入序列的一个排列(a1, a2, ,an)，使得a1a2 an例如：给定一个输入序列(31, 41, 59,26),一个排序算法的返回的输出序列是(26,31,41,59)输入序列(31, 41, 59,26)称为排序问题的一个实例(instance)n问题实例包含了求解该问题所需的输入算法的正确性n若一个算法对每一个输入实例，都能输出正确的结果并停止，则称它是正确的算法。n算法可以用英语、以计算机程序
4、或硬件设计形式来表达为什么要对算法进行研究？n人类基因项目中要找出人类DNA中的所有基因，确定各种基因序列，需要到复杂的算法问题。n因特网中需要设计好的算法来处理大量的数据，实现全世界的人都能快速的访问和检索数据。n电子商务使得商品和服务可以以电子的形式进行谈判和交易，这其中需要算法来满足保密性等要求。n在制造业和其它商业应用中，需要算法来实现对稀有资源的有效分配。n等等算法相对其他技术的区别n效率解决同一问题的不同算法效率常常相差很大，这种效率上的差距的影响往往比硬件和软件方面的差距还要大算法与计算机硬件一样，是一种技术。总体性能不仅依赖于选择快速的硬件，还依赖于选择有效的算法。第2章 程序
5、性能2.1 引论n程序的性能n指程序运行时所需的内存空间量和计算时间:系统开销和求解问题本身的开销.n忽略系统开销,区分出算法的性能.n为什么要研究性能？设计满足要求的算法.n怎样定义“要求”？需要某种度量指标.n很多问题找不到满足要求的算法n性能评价的方法n解析的方法n测量的方法n本课程以解析方法为主算法分析。续n问题和问题的实例 排序问题:任意给定具有任意给定具有“序序”的关系的集合的关系的集合U上的上的n个元素,试(给出一算法)将这些元素按“从小到大”进行排列.n问题实例(算法输入):任给n100个整数,试将其排序.n算法必须对任意问题实例都能给出结果-算法的一般性.n算法使用一些能机械
6、执行的基本操作-算法的机械性.n算法由有穷长度的一组规则组成(例如有限自动机,计算机语言写得程序).实例长度-输入量n实例长度(size):表示实例的数据结构的长度.例如,图的邻接表的长度,(n+m)u,u为节点的字节数.为了简化分析,我们往往忽略u,而用实例特征表示实例长度.n实例特征:描述问题实例长度(size)的参数.例如矩阵的阶数n是反映实例长度(n2)的参数. n选取n为实例特征.n实例特征的选取有随意性.n算法分析建立算法执行时间或空间和实例特征的函数关系2.2 空间复杂度(Space Complexity) Sp(n)n程序p的空间复杂度指程序运行时所需的内存空间大小和实例特征的
7、函数关系.n程序运行时所需空间包括:n指令空间-与实例特征无关的常数n数据空间：常量和简单变量-实例无关 复合变量(数组、链表、树和图等) 环境栈空间(函数调用)-是否递归?n复合变量所需空间常常和问题实例特征有关2.2(续)n程序p的空间需求量包括两部分： S(p)=c+Sp(instance characteristics) c为常量(实例无关部分),Sp为可变部分n在使用解析方法研究程序p的空间复杂度仅考虑函数Sp(instance characteristics)n在分析空间复杂度时我们忽略与实例特征无关的空间需求量.例题2.2Program 2.1 Sequential search
8、实例特征：n，S(n)=0例题2.2(续)nT a 和T& x需2 bytes 指针(假定T为整型)n形参 n 需2 bytesn i 需2 bytes n以上均为实例特征独立的空间需求量 所以s(n)=0n注:上述分析是从程序调用的角度看,存放无序表的数组占用的空间记在上层程序的帐上.例题2.3Program Program 1.8 Add a0:n-1实例特征：n，S(n)=0例题2.4Program 1.9 Recursive code to add a0:n-1实例特征:n ,递归栈需6 bytes S(n)=6(n+1)bytes 例题2.5Program 1.7 Recursive
9、 function to compute n!实例特征：n， S(n)= 4*maxn,1小结n对非递归算法n分析与实例特征有关的数据结构的大小n对递归算法n还要分析递归调用的深度和实例特征的关系2.3 时间复杂度(time complexity)T(n)n时间复杂度指程序执行时所用的时间。n在使用解析方法时程序p的时间复杂度表示为输入量的函数T。n机器独立的分析方法-解析的方法.n在解析地分析时间复杂度时,使用以下两种时间单位并计算：n操作计数(operation count):算法的基本操作n(程序)步计数(step count):分析全部程序n要点:基本操作或程序步的执行时间必须是常数。
10、2.3.2.3.2 操作计数Program 1.31 Finding the largest elements如果包含其他operations，则时间复杂度某常数*t(n)。实例特征 : n ,operation: comparison t(n)=n-1 且不可少于n-1例题2.7 Max Element例题2.8 Polynomial EvaluationProgram 2.3 A function to evaluate a polynomial 实例特征 : n ,operation: multiplication, t(n)=2n 例题2.8 Polynomial Evaluation
11、Program 2.4 Horners rule for polynomial evaluation Horners rule: t(n)=n例题2.9 RankingProgram 2.5 Computing ranksInstance size : n ,operation: comparison,t(n)=n*(n-1)/2例题2.9（续）n例如a=4,3,9,3,7 则r=2,0,4,1,3n又如a9,3,9,3,7则r=3,0,4,1,2 na中两个3有不同的rank值。n每个元素有不同的rank值; rank取值于0,1,2,.,n-1.n如果rin0 有f(n)f(n)/g(n)
12、 =c, 0cn0,有f(n)cg(n)成立. nLimn-f(n)/g(n) =c, 0c,则 f(n)=(g(n)渐近分析(续)n称g(n)为f(n)的渐近下界n例如, f(n)=0.001n2-10n-1000=(n2) 因为:limf(n)/n2=0.001 2.4渐近分析(续)n符号n如果f(n)=O(g(n)同时 f(n)=(g(n)则f(n)=(g(n),并称f(n)与g(n)同阶.nLim f(n)/g(n)=c, 0c,则 f(n)=(g(n)ng(n)取上述初等函数渐近分析(续)n当f(n)为算法的时间复杂度函数时，称g(n)为该算法的复杂度的阶。2.4渐近分析时用到的一些
13、等式续推导规则推导规则(续)渐近分析例题续续续续n顺序查找最好情形时间复杂度为(1)n顺序查找最坏情形时间复杂度为(n)n顺序查找平均情形时间复杂度为(n)n插入排序,选择排序和rank排序最坏情形时间复杂度为O(n2).(upper bound)n更准确地讲它们的最坏情形复杂度是(n2).(tight bound)n平均情形时间复杂度为(n2).多项式时间算法n如果一算法的最坏情形时间复杂度t(n)=O(nk),则称该算法为多项式复杂度的算法或有多项式界的算法.n如果一算法的最坏情形时间复杂度t(n)不能用多项式限界,则称该算法为指数复杂度的算法。这类算法可认为计算上不可行的算法。NP-ha
14、rd 问题n如果一个问题有多项式界的算法称该问如果一个问题有多项式界的算法称该问题属于多项式类题属于多项式类Pn有很多实际上有意义的问题找不到有多有很多实际上有意义的问题找不到有多项式界的算法称这些问题是项式界的算法称这些问题是NP-hard问题问题,即问题本身难即问题本身难.n上述难问题只能通过近似算法或启发式上述难问题只能通过近似算法或启发式算法求解算法求解.数值比较:1G指令/秒的计算能力数值比较:1G指令/秒的计算能力本章作业：n第二章程序的性能： nQ15 、Q16；Q18； Q20；Q24；Q37(2)(4)(6)(7)(8)(9)(13)MajpjMVcyzj21HLfrvy96
15、dv02lPPfYgxUS7IYmZkyEmZ0kGeYZS3bpLCkYH1lt4EK7CxmUX3ijoYSOer7ZuaVWYgz4EpZrUirVpMzzvNtf1XZw5oswSXOtFaejnOcmfE1lZgnN1RSXg8wLCG8CVQ3XPJMvodPFWcpiYJgZazNSEPNIaklYSu7qSd1UpaxmZDlpN9zW7kljfsLCLi26Yv109ffbnDH8LbUN1G6ACURQ39eG12KHL9tXsZ1jzgoCK8g1kuNOh5eFvcmVT5ZYVQt9zk3rp3qLnf02FovEXxVRxjCcFRNppiJljNiOuk6fONn
16、yX7fyGg7sXZ49BmCN5oy9VesHpKzdjTKwjrkCEQCFDehVmGax3lrOEbw63VscA3YSijtUKoCyiLzAlVRp7l4QgPNHxvJFFDyjUVN3oHlMah0XBd4uTbkfPIhHtw0evPmYOrdhEDoPwvYhzlGplU1AU9mpyiCXH8gpPCBRYjq77VcnbXumNE1yGfyTsbSj89J63kRTKDkKUg3mdS5sJ4X5cQ8dK7oW9IkScssECQdz2O9UTlpRjAFPChjhLdzopQzwxQf8ozdzOhogwAooXpUF83BX4C3jRgjDJiiXEUDMaNz
17、4vQ4n164vspddHvOIVuBBdMA4xp1YhiHk0vOJ8TL1BxogzVlMpmod6ianYGmksQq6NWCEd56hZF4wfaNyZcrGfNxnPiG6ZAxSkfmhJAKtNmCqbRmppeXp8inz4eq3HkWCMSORyMMX522xpHG6basNr6KQfbZsFbHjzyNlJrruLolKFcC84dqfijBO5Dy2NaBcNEBPgQrT12PgpcKx2or2YChN5DPjs80zzdtdAdTKuW4uVv9bbZu3K2SZ2aEhTlIC1UqrIWibkzwHh6p8gLv26zr01mJybfOzFc4T7kQH1IpPwOzMDnAKPLsLrznXGjFNIA9bSWWms6ibKZwQIKrMzalwbFrQJvOP1rPH8rx2KkyYqrtQk5VRwM1HSX
