《《算法基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算法基础》PPT课件.ppt（51页珍藏版）》请在三一办公上搜索。
1、1,Introduction to ACM/ICPC Programming ContestChen BinYangzhou UniversityE-mail:,2,ACM(Association for Computing Machinery)成立于计算机诞生次年，是目前计算机学界中历史最悠久、最具权威性的组织，是推进信息技术专业人员和学生提高技巧的主要力量。ACM通过提供前沿技术信息和从理论到实践的转化，为其全球7.5万名成员服务，并已经成为信息科技领域的一个基本信息来源。,What is ACM?,3,ACM/ICPC：,ACM主办的国际大学生程序设计竞赛(International C
2、ollegiate Programming Contest)，简称ACM/ICPC，自从1977年开始至今已经连续举办30届。其宗旨是提供一个让大学生向IT界展示自己分析问题和解决问题的能力的绝好机会，并成为一个有效的途径，让下一代IT天才可以接触到其日后工作中将要用到的各种软件。现在，ACM/ICPC已成为世界各国大学生中最具影响力的国际计算机赛事。,4,ACM/ICPC in China,中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛。前五届中国赛区设在上海，由上海大学承办；2002年由清华大学和西安交通大学承办；2003年由清华大学和中山大学承办。2004年由北京大
3、学和上海交通大学承办。2005年由四川大学、北大和浙大承办。2006年由上海大学、清华和西电承办。2007年由吉林大学、北大和西华大学以及南京航空航天大学承办。2008年由哈尔滨工程大学、北京交通大学、中国科学技术大学、杭州电子科技大学、西南民族大学 承办,5,如何比赛？,3人组队,可以携带诸如书、手册、程序清单等参考资料；不能携带任何可用计算机处理的软件或数据、不能携带任何类型的通讯工具；,可能收到的反馈信息包括：Compile Error-程序不能通过编译。Run Time Error-程序运行过程中出现非正常中断。Time Limit Exceeded-运行超过时限还没有得到输出结果。W
4、rong Answer-答案错误。Presentation Error-输出格式不对，可检查空格、回车等等细节。Accepted-恭喜恭喜！,6,首先根据解题数目进行排名。如果多支队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间而成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，其间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不记时。,如何排名？,7,比赛形式1支队伍1台机器（提供打印服务）上机编程解决问题（可带纸质资料）实时测试，动态排名试题6-10题全英文（可以带字典）时间：持续5个小时,8,Language,9,C
5、ourse Object,Provide a convenient summary/reference of important topics in mathematics and algorithms,along with appropriate challenges to help you master the material.Preparing for the contestImprove the programming ability,10,Course Outline,Algorithm basicsData StructuresAlgorithm designGreedy Bra
6、nch and Bound Dynamic ProgrammingMathematical BasicsNumber theoryArithmetic and algerbraCombinatoricsComputational Geometry,11,第一讲算法基础,扬州大学信息工程学院计算机系陈斌二九年三月,12,参考书目,算法艺术和信息学竞赛刘汝佳算法与数据结构傅清祥现代计算机常用数据结构与算法潘金贵等Introduction to AlgorithmsComputer Algorithms Introduction to Design and Analysis Sara Baase&A
7、llen Van Gelder计算机程序设计艺术 Donald KnuthArt of Programming ContestC Programming,Data Structures,Algorithms 2nd EditionProgramming Challenges,13,1.1 算法,什么是算法？平时所说的算法算法就是解决问题的方法或过程。计算机科学中的算法算法是指由有限指令集合中的一系列指令所组成的过程。,14,算法的基本特征,有穷性算法必须是可终止的。确切性算法的每一步都应确切地、无歧义地定义。可行性算法原则上能够精确地运行。输入一个算法必须有零个或多个输入。输出一个算法有一个或
8、多个输出,15,1.2 时间复杂度和空间复杂度,时间复杂度对于一个规模为n的输入数据，我们希望知道算法要运行多长时间得到结果，也希望知道随着n的增长，算法所需时间的增长速度如何？空间复杂度对于一定规模输入数据，算法运行所需空间的度量,16,1.2.1 基本渐进记号,定义1.1 设f和g是两个函数，如果存在c1，c2，N0,使得当nN时，此时用表示函数集合，其运行时间用来度量。如果存在正常数N和c使得当nN时，f(n)N时，f(n)cg(n)记为。,17,渐进记号的图例,18,1.2.2 代码分析,简单实例复杂实例算法比较,19,代码分析的例子(1),fact:=1;for i:=1 to n
9、do fact:=fact*i;一次乘法为一个基本操作忽略i改变的时间共f(n)=n次基本操作时间复杂度为n,20,代码分析的例子(2),sum:=0;for i:=1 to n do for j:=1 to n do sum:=sum+ai,j;基本操作：加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2,21,一个更为复杂的例子,sum:=0;for i:=1 to n do begin fact:=1;for j:=1 to i do fact:=fact*i;sum:=sum+fact;end第i次循环执行了i个操作总时间复杂度为1+2+3+n=n(n+1)/2,22,比
10、较两个算法,算法一执行了f(n)=n2次基本操作算法二执行了g(n)=n2/2次基本操作那个算法好呢？算法二好，因为g(n)f(n)增长情况呢？n扩大10倍，f(n)扩大100倍，g(n)也扩大100倍两个算法的增长情况一样！渐进时间复杂度一样！,23,1.3 渐近性时间复杂度,f(n)=n2和g(n)=n2/2增长情况一样如何表示“增长情况”？把f(n)和g(n)变成“渐进”形式，然后直接比较如何变成“渐进”形式？只保留最“大”项忽略系数例1：3n4+8n2+n+2 n4例2：2n+1+n100+5 2n(为什么n+1变成了n？),24,复杂度分析不是万能的,回忆刚才的变换方法变换前后的增长
11、情况一致需要先写出完整的式子至少知道最大项可是很多情况下无法知道最大项不信？一个数n，如果它是奇数则变换到3n+1，否则变换到n/2给一个数n，不停的变换下去，经过几步变成1？你知道它的运行时间吗?!这是个著名的停机问题复杂度分析不是万能的！,25,复杂度分析不清楚怎么办,只分析上限，而不管实际运行时间若n充分大时|f(n)|=c|g(n)|，其中c为某常数记f(n)=O(g(n)，表示g(n)为f(n)的渐进上限例1：5n2+3n+1=O(n2)例2：2n3=O(7n8)由于上限有无限多个，我们希望它尽量精确否则我们的分析就过于悲观了，实际算法没那么糟糕类似的，可以定义下限如果上下限相等，那
12、么增长情况就完全一样了记做,26,复杂度的等级,多项式算法O(nt)，t是常数O(logtn),t是常数O(loglogn),奇怪吗？两个多项式时间复杂度的积仍是多项式的排序O(1)O(loglogn)O(logn)O(n1/2)O(n)O(n)O(nloglogn)O(nlogn)O(n2)O(n2)O(n3)O(2n)O(n!)O(nn),27,复杂度曲线,28,不同情况的时间开销,输入规模决定运行时间吗？for i:=1 to n do read(ai);for i:=1 to n-1 do if ai ai+1 then do_it;假设do_it操作为一次基本操作，忽略其他如果输入是
13、从小大到排序好的，则操作数为0如果输入是从大到小排序好的，则操作数为n-1即使规模(n)相同，不同的输入导致不同的运行时间！,29,一道题目,给一串整数a1n，求出它和最大的子序列，即找出1=i=j=n，使ai+ai+1+aj最大介绍四个算法并分析时间复杂度枚举：O(n3)优化的枚举：O(n2)分治：O(nlogn)贪心：O(n),30,算法一,思想：枚举所有的i和j，计算ai+aj，选择最大的程序如下：max:=a1;for i:=1 to n do for j:=i to n do begin sum:=0;for k:=i to j do sum:=sum+ak;if sum max t
14、hen max:=sum;end;End;时间复杂度如何分析？,31,算法一分析,当i和j一定的时候，内层循环执行j-i+1次总次数为应该如何计算？方法一：直接计算先计算里层求和号，得再加起来？好复杂自己做一做吧，得利用公式12+n2=O(n3)一般地，有1k+nk=O(nk+1),32,算法一分析（续）,总次数为：完全的计算太麻烦能不能不动笔就知道渐进时间复杂度呢？何必非要计算出详细的公式再化简呢？里层求和计算出的结果是O(n-i)2)12+22+n2=O(n3)每步都化简！但是要保留外层需要的变量结论：算法一时间复杂度为O(n3)经验：一般只能支持 n=200,33,算法二,思路枚举i和j
15、后，能否快速算出ai+aj呢？预处理！记si=a1+a2+ai,规定s0=0则可以在O(n)的时间内计算出s1,sns0:=0;for i:=1 to n do si:=si1+ai;,34,算法二（续）,有了si，怎么快速求ai+aj呢？ai+aj=(a1+aj)(a1+ai-1)=sj si-1而si经过预处理以后可以直接读出！程序如下：max:=a1;for i:=1 to n do for j:=i to n do if sj si-1 max then max:=sj si-1;end;end;时间复杂度：预处理+主程序=O(n+n2)=O(n2).n=3000,35,算法三,用一种
16、完全不同的思路最大子序列的位置有三种可能完全处于序列的左半，即j=n/2跨越序列中间，即in/2j用递归的思路解决！设max(i,j)为序列aij的最大子序列那么,36,算法三（续）,用递归的思路解决！设max(i,j)为序列aij的最大子序列设mid=(i+j)/2，即区间aij的中点最大的第一种序列为max(i,mid)最大的第二种序列为max(mid+1,j)问题：最大的第三种序列为？既然跨越中点，把序列aij划分为两部分aimid：最大序列用扫描法在n/2时间内找到一共只有mid-1=n/2种可能的序列，一一比较即可amid+1j：同理一共花费时间为j-i+1,37,算法三分析,如何分
17、析时间复杂度呢？我们没有得到具体的T(n)的式子只有一个递推式子T(n)=2T(n/2)+n设时间复杂度的精确式子是T(n)第一、二种序列的计算时间是T(n/2)，因为序列长度缩小了一半第三种序列的计算时间是n计算出T(n)，就得到了时间复杂度怎样计算T(n)呢？,38,递归树分析,一般情形：T(n)=aT(n/b)+f(n)a,b为常数，f(n)为给定函数由递归树得结果为T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中最后一项为递归边界，即n/bL=1，因此L=logbn,39,算法三分析（续二）,n/bL=1因此bL=n记L=logbn，称L为以b为底的n的对
18、数对数的公式：logan+logam=loganmklogan=logank换底公式：logan/logbn=logba对数是一种增长很慢的函数log21000 约为 10log21000000 约为20时间复杂度O(nlogn)和O(n2)相比是很大的提高！和O(n)在实际中相差并不是非常大,40,算法三分析（续三）,一般情形：T(n)=aT(n/b)+f(n)a,b为常数，f(n)为给定函数递归树得到的结果：T(n)=f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中L=logbn算法三的递推式：T(n)=2T(n/2)+na=2,b=2,f(n)=n对于第k项，有2kf
19、(n/2k)=2k*n/2k=n一共有log2n项T(n)=n*log2n=O(nlogn).n=100,000底数2为什么没有了呢？换底公式：logan/logbn=logba=常数,41,算法四,算法二的实质是求出i max then max:=sj min_s;if sj min_s then min_s:=sj;end;时间复杂度很明显：O(n).n=1,000,000,42,扩展,给n*n矩阵，求和最大的子矩阵,43,分析,枚举起、止行号r1和r2，压缩子矩形成为一行，变成一维问题,第i个元素为bi=ar1,i+ar1+1,i+ar2,i对于第i列,计算前缀和prefixij=a1,
20、i+a2,i+aj,i则bi=prefixir2-prefixir1-1,常数时间计算前缀和:O(n2),一维问题:O(n)共O(n3),44,总结,45,需要学会的东西,为什么要分析算法算法分析的结果是什么样子具体时间？No基本操作的次数？Yes渐进分析的结果：增长情况为什么分析增长情况？计算机速度弥补运行时间O(n),O(nlogn),O(n2)分别能支持多大规模？分析简单的代码（幻灯片8，9，10）为什么要区分最坏、最好、平均情况算法都是可以分析的吗？为什么要定义上限、下限难点一：灵活的应用渐进分析难点二：用递归树解递归方程,46,实验一(1)3n+1 problem,47,实验一（2）
21、铁轨问题,例1：1,2,3,4,5 yes；例2：5,4,3,2,1 yes例3：3,2,4,5,1 yes；例4：3,1,4,5,2 no,48,习题1-1：函数的渐进表达式,求下列函数的渐进表达式3n2+10n n2/10+2n；211/n；logn310 log3n习题 O(1)和O(2)的区别,49,按照渐进序排列下列表达式,4n2,logn,3n,20n,2,n2/3,n!,50,习题12 算法效率,假设某算法在输入规模为n时的计算时间为T(n)32n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度是第一台的64倍，那么在这一台机器上使用同一算法在t秒内能够解决输入规模为多大的问题？,51,若算法效率改进为T(n)n2，那么能够运行多大规模的问题？进一步改进为T(n)8，那么其能够运行多大规模的问题？,
