ACM培训班课件(2013年春季)

20131《算法设计及其高效实现》周健ahjzhouatgmail.com电话：1525510383520112前言ACM/ICPC介绍34567820119前言ACM/ICPC介绍激情梦想成功10关于ACM/ICPC竞赛ACM竞赛是计算机学科领域最高级别的赛事；主要考查选手用算法+数据结构解决问题的能力；题量多，时间长，高手云集；洲际网络选拔赛-洲际现场赛-全球总决赛；亚洲区15个赛场，其中中国大陆5个；省程序设计竞赛；11安徽大学ACM07年开始参赛；08年获亚洲区合肥赛区铜奖获奖队员：吴翔，王汉，宋康09年获亚洲区武汉赛区铜奖获奖队员：吴翔，朱国锋，李东10年获亚洲区杭州赛区银奖获奖队员：朱国锋，朱学智，牛铮12组织结构与队员负责人：郑诚（副院长）指导老师：马猛，周健组织网站：icpc.ahu.edu.cn集训队专用实验室：笃南A21530平方，9台机器上课、讨论实验室：笃南A211120平方，30台机器左右13队员05级宋康（保研东南大学）06级宋克鑫（保研中国科学技术大学）07级吴翔（保研中国科学技术大学）08级朱国锋朱学智朱俊丁亚光牛铮崔晨阳周宝通吴翔（物理系）韩梁何学斌09级卢肖胡文翔王博岩14入队条件人文素质条件品德端正团队精神不接受急功近利、胸无大志、心理脆弱、自暴自弃、缺乏自理和自控能力、以个人利益为中心者技术条件有比较扎实的代码能力了解常用的算法设计方法有比较广博的知识面技术衡量指标同学评价在OJ上的活跃度，做题量月赛排名15队员选拔与淘汰选拔Step1.校赛Step2.ACM培训班，期末考试Step3.暑期集训接受优秀者自荐！淘汰入队半年后毫无进展者队员评价差者不服从指导老师安排者16AHCPC队选拔过程校程序设计竞赛赛初选赛ACM培训、日常训练暑期集训AHCPC队选拔赛1911年ACM/ICPC赛事3-7月区域邀请赛安徽省省赛校级月赛9月-11月中国区域赛（网络，现场）复旦大学西南石油大学福州师范大学大连理工大学北京邮电大学20开课目的交流学习提高发现高手21教学方法理论讲解题目剖析课后练习poj,zoj,topcoder,usacoAOJ:上课安排教师老队员23参考教材潘金贵等译《算法导论》（第二版）王晓东著《算法分析与设计》刘汝佳等著《算法艺术与信息学竞赛》NOI,IOI论文集24队员考核1.习题完成数2.月赛排名3.其他主动做题量4.期末考试201125第一部分算法分析基础26算法+数据结构=程序算法是指解决问题的一种方法或一个过程的良定义。算法是若干指令的有穷序列，满足性质：输入：有外部提供的量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令是清晰，无歧义的。有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。27算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）281.4算法复杂性分析最坏情况下的时间复杂性：),(maxmaxINT(N)TNDI),(max1INetkiiiDIN),(*1INetkiii),(*INT最好情况下的时间复杂性：),(minminINT(N)TNDI),(min1INetkiiiDIN)~,(1INetkiii)~,(INT平均情况下的时间复杂性：NDIINTIP(N)T),()(avgNDIkiiiINetIP),()(1其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是DN中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。I~I~291.4算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Ω、o、、设f(N)和g(N)是定义在正数集上的正函数。在下面的讨论中，对所有n，f(n)0，g(n)0。（1）紧渐近上界OO(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}（2）紧渐近下界(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}30（3）非紧渐进上界oo(g(n))={f(n)|对于任何正常数c0，存在正数n0使得对所有nn0有：0f(n)cg(n)}等价于f(n)/g(n)0，asn。（4）非紧渐进下界(g(n))={f(n)|对于任何正常数c0，存在正数n00使得对所有nn0有：0cg(n)f(n)}等价于f(n)/g(n)，asn。f(n)(g(n))g(n)o(f(n))31（5）紧渐近确界（）(g(n))={f(n)|存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}定理1：(g(n))=O(g(n))(g(n))舍弃低阶项和最高阶项系数3233渐进复杂性的直观理解当输入规模趋向无穷大时，算法的运行时间只决定于算法运行时间表达式中的高阶项，低阶项相对来说就不重要了。34常见的描述算法复杂度的函数多项式函数p(n)=a0+a1n+a2n2+…+adnd；ad0;p(n)=(nd);kdp(n)=O(nk);kdp(n)=(nk);kdp(n)=o(nk);kdp(n)=(nk).35f(n)=O(nk)f(n)多项式有界；f(n)=O(1)f(n)c;36指数函数对于正整数m,n和实数a0:a0=1;a1=a;a-1=1/a;(am)n=amn;(am)n=(an)m;aman=am+n;a1an为单调递增函数;a1nb=o(an)推论：任何底大于1的指数函数比任何多项式函数增长得更快37对任意x有ex1+x;当|x|1时1+xex1+x+x2;ex=1+x+(x2),asx0;032!!3!21iixixxxxexnnenx1lim38（5）对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=(logn)kl;loglogn=log(logn);fora0,b0,c0abbalog39baabcccloglog)(loganabnbloglogbaaccblogloglogaabblog)/1(logbaablog1logacbbcaloglog40|x|1forx-1,foranya0,,logbn=o(na).5432)1ln(5432xxxxxxxxxx)1ln(10loglim)2(loglimlogabnnabnnnn推论：任意正的多项式函数都比多项对数函数增长得更快41（6）阶乘函数Stirling’sapproximation00)!1(1!nnnnnnn321!nennnn11π2!42neennnnπ2!nnn121α1121)(!nnon)2(!nn)log()!log(nnn43算法分析中常见的复杂性函数44小规模数据45中等规模数据46函数增长和运行时间47其他常见函数和近似48算法复杂度分析方法例：顺序搜索算法templateclassTypeintseqSearch(Type*a,intn,Typek){for(inti=0;in;i++)if(a[i]==k)returni;return-1;}49（1）Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）在平均情况下，假设：(a)搜索成功的概率为p(0p1)；(b)在数组的每个位置i(0in)搜索成功的概率相同，均为p/n。nIsizeavgITIpnT)()()()(pnnpnnpnpnp1321)1(2)1(11pnnppninpni50算法分析的基本法则非递归算法：（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。51templateclassTypevoidinsertion_sort(Type*a,intn){Typekey;//costtimesfor(inti=1;in;i++){//c1nkey=a[i];//c2n-1intj=i-1;//c3n-1while(j=0&&a[j]key){//c4sumoftia[j+1]=a[j];//c5sumof(ti-1)j--;//c6sumof(ti-1)}a[j]=key;//c7n-1}}52在最好情况下，ti=1,for1in;在最坏情况下，ti=i+1,for1in;)1()1()1()1()1()(7116115114321nctctctcncncncnTniiniinii)1()1()1()1()(74321minncncncncncnT)()()(743274321nccccnccccc1112)1()1(ninni112)1(ninni)()(22)1(2)1(2)1(12)1()1()1()(27432765432126547654321maxnccccncccccccncccncnncnncnncncncncnT53例如对于输入数据a[i]=n-i,i=0,1,…,n-1，算法insertion_sort达到其最坏情形。因此，)()(22)(2743276543212654nccccncccccccncccnT54实例：最大和连续序列问题给一串整数a[1..n]，求出其和最大的子序列，即找出1=i=j=n，使a[i]+a[i+1]+…+a[j]最大介绍四个算法并分析时间复杂度枚举：O(n3)优化的枚举：O(n2)分治：O(nlogn)贪心：O(n)55算法一思想：枚举所有的i和j，计算a[i]+…+a[j]，选择最大的时间复杂度如何分析？三层循环内层操作次数取决于i,j中层操作次数取决于imax=a[1];fori=1tondoforj=itondobeginsum=0;fork=itojdosum=sum+a[k];ifsummaxthenmax=sum;end;56算法一分析当i和j一定的时候，内层循环执行j-i+1次总次数为应该如何计算？先计算里层求和号，得利用公式12+…+n2=O(n3)一般地，有1k+…+nk=O(nk+1).证明:数学归纳法结论：算法一时间复杂度为O(n3)经验