算法分析与枚举策略课件.ppt

《算法分析与枚举策略课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACMGroup算法分析与枚举策略程序设计实践算法的分析方法简单性健壮性效率——时间复杂度占用空间——空间复杂度算法的时间复杂度一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的基本操作或“步”数。假设我们求出算法过程中执行基本操作的次数，为c(n)次。我们进一步规定在特定计算机上算法的基本操作的执行时间为t，则可以估计出整个算法的运行时间T≈t·c(n)。时间复杂度只能衡量c(n)相对于n的增长速度情况，和t没有直接关系。但考虑整个算法的运行时间时千万不要忽略了基本操作的执行时间t。时间复杂度的规定设f(n)是关于n的函

2、数，我们用关于f(n)的一个函数来表示算法的渐进时间复杂度。严格的定义是这样的：若存在两个正常数c和m，对于任意n>m都有

3、T(n)

4、≤c·

5、f(n)

6、，（这可以看作是极限的思想：n->∞时，f(n)是T(n)的同阶或高阶无穷大）则称T(n)在集合O(f(n))中，用O(f(n))表示算法的时间复杂度。通常可以认为，算法过程中执行基本操作的次数为k时，g是对于某数的增长情况的函数，有g(k)≈g(f(n))，则该算法的时间复杂度为O(f(n))。O(f(n))中的f(n)的计算c1·

7、f(n)

8、≤

9、T(n)

10、≤c2·

11、f(n)

12、一般

13、来说取满足上式的f(n)来表示时间复杂度较为精确。但是满足条件的f(n)还是很多，为了方便准确的表示时间复杂度，f(n)应用下面的方法求得：令f(n)=T(n),然后忽略常数和低次项（增长次数的排序见下张幻灯片）求得f(n)。例如3n^4+8n^2+n+2=O(n^4)，其中f(n)=n^4。关于时间复杂度的两个表AcceptedorTLE一般来说评测机每秒处理基本操作10^8次左右，所以将题目最大数据带入O(f(n))就基本可以估计出是否会超时。试分析三个算法的时间复杂度1.f[0]=f[1]=1,f[2]=2;for(i=3;i

14、<=n;i++)f[i]=f[i-1]+f[i-3];2.for(i=1;i<=n;i++)for(j=1;j<=i;j++)if(j==1

15、

16、j==i)f[i][j]=1;elsef[i][j]=f[i-1][j]+f[i-1][j-1];3.for(i=1;i<=n;i++)for(j=1;j<=i*i;j++)f[j]++;试分析三个算法的时间复杂度算法一的基本操作数为n-2，时间复杂度为O(n)。算法二的基本操作数为（1+2+3+…+n）=n·（n+1）·1/2=1/2·n2+1/2·n，时间复杂度为O(n2)。算法三的基本

17、操作数为12+22+32+…+n2=1/6·n·(n+1)·(2n+1)，时间复杂度为O(n3)。试分析递归算法的时间复杂度intf (intx){if(x==2)return2;if(x<2)return1;returnf(x-1)+f(x–3);}输入n计算f(n)试分析递归算法的时间复杂度设计算f(n)的基本操作数为g(n)则有g(n)=g(n-1)+g(n-3)g(0)=g(1)=g(2)=1可知g(n)=C0P0n+C1P1n+C2P2n可知f(n)的时间复杂度为O(an)空间复杂度ACM题目对空间方面一般不会有太严格的要

18、求，只要保证程序申请的内存空间小于题目要求就行了。不过这个不能随便估计要精确计算。再普及一下应该都知道的知识：char=1Bshort=2Bint=4Bdouble=8Blonglong=8B1MB=1024KB=1024*1024B时空权衡一般来说可以通过花费更多的空间换取更少的时间，或者花费更多的时间换取更少的空间。我们要根据要求来时空权衡设计算法。这一点大家会在今后学习更多的算法后得到体会，这里就不深入讲解了。枚举所谓枚举法，指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立

19、，即为其解。枚举是一种确定范围后的搜索。枚举的几个主要步骤如下：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围；利用循环语句、条件判断语句逐步求解或证明。枚举的优点是简单、直观、便于理解和证明。主要缺点就是计算规模大，效率低下。但枚举类的题目不一定简单，在有多种枚举策略的时候，要分析每种策略的优劣，选取最好的策略来满足题目的要求。简单的例题HOJ1128HOJ1459例1统计问题x+2y+3z=200，求正整数解的个数。三种枚举方法：可以比较一下优劣枚举x，枚举y，枚举z，验证。枚举x，枚举y，验证200-x-2

20、y整除3。枚举y，枚举z，统计即可。例题2时钟考虑将如此安排在一个3×3行列中的九个时钟。目标要找一个最小的移动顺序次将所有的指针指向12点。下面图中列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使