ACM程序设计算法原理和ACM入门参考.ppt

ACM程序设计 东北林业大学 陈宇 第一讲 算法原理和ACM入门 (Introduction to ACM) 我校的ACM在线评测系统 课件下载地址： /kj/suanfa01.ppt 开课目的 为林大ACM代表队培养后备人才 提高分析问题和应用计算机编程解决问题的能力 培养必要的自学能力 培养学生的协调和沟通能力 体会学习的快乐 ACM/ICPC in China 中国大陆高校从1996年开始参加ACM/ICPC—— 前六届中国赛区设在上海，由上海大学承办； 2002年：清华和西安交大； 2003年：清华和中山； 2004年：北大和上海交大； 2005年：川大、北大和浙大； 2006年：上海大学、清华和西电； 2007年：北航、南航、吉大、西华； 2008年：哈工程、北交、中科大、杭电、西南民大； 2009年：哈工大、中科大、NIT、武大、东华； 2010年：天大、福大、川大、哈工程、浙江理工； ACM in NEFU 2006年9月，第一次参加此类比赛（黑龙江省赛） 2006～2010，每年5月—— 黑龙江省第1～5届大学生程序设计竞赛 2007～2010，每年6月—— 东北地区第1～4届大学生程序设计竞赛 2006～2010，每年9月——11月 第29～34届ACM国际大学生程序设计竞赛亚洲区预选赛 预期赛事（今后每年） 3~4月，举行校内大赛（暨选拔赛） 4月， ACM全国邀请赛 5月，参加黑龙江省大学生程序设计大赛 6月，参加东北4省大学生程序设计大赛 10~11月，参加ACM/ICPC亚洲区比赛（至少参加4～5个赛区的比赛） 另外，每学期至少有三次月赛以及适当的练习赛 2010年的风采 第一部分 算法概述 评价算法 评价算法的三条主要标准是： (1) 算法实现所耗费的时间； (2) 算法实现所所耗费的存储空间，其中 主要考虑辅助存储空间； (3) 算法应易于理解，易于编码，易于调 试等等。 和算法执行时间相关的因素： 1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度 算法效率的衡量方法 通常有两种衡量算法效率的方法: 1）事后统计法（有缺点，较少使用） 2）事前分析估算法 算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=Ο(f(n)),称T(n)为算法的渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。Ο是数量级的符号。 一个算法中所有语句的频度之和构成了该算法的运行时间。 例如： for(j=1;j=n;++j) for(k=1;k=n;++k) ++x； 语句“++x、k=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。 再看看这个代码： 当一个算法的算法运行时间为n2+n+1，由于n2+n+1与n2的数量级相等(该表达式当n足够大时约等于n2), 我们说这个算法的渐进时间复杂度(简称算法的时间复杂度)为：T(n)=O(n2)。 算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)： Ο(1)称为常数级 Ο(logn)称为对数级 Ο(n)称为线性级 Ο(nc)称为多项式级 Ο(cn)称为指数级 Ο(n!)称为阶乘级 Temp=i；i=j；j=temp； 以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=Ο(1)。 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是Ο(1)。 【例2】变量计数之一。 (1) x=0；=0； (2) for(k-1；=n；++) (3) x++； (4) for(i=1；=n；++) (5) for(j=1；j=n；++)