算法剖析和枚举的策略.ppt

ACM Group 算法的分析方法 简单性 健壮性 效率——时间复杂度 占用空间——空间复杂度 算法的时间复杂度 一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的基本操作或“步”数。 假设我们求出算法过程中执行基本操作的次数，为c(n)次。我们进一步规定在特定计算机上算法的基本操作的执行时间为t，则可以估计出整个算法的运行时间T≈t·c(n)。 时间复杂度只能衡量c(n)相对于n的增长速度情况，和t没有直接关系。但考虑整个算法的运行时间时千万不要忽略了基本操作的执行时间t。 时间复杂度的规定 设f(n)是关于n的函数，我们用关于f(n)的一个函数来表示算法的渐进时间复杂度。严格的定义是这样的：若存在两个正常数c和m，对于任意nm都有|T(n)|≤c·|f(n)|，（这可以看作是极限的思想：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·|f(n)|≤|T(n)|≤c2·|f(n)| 一般来说取满足上式的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。 关于时间复杂度的两个表 Accepted or TLE 一般来说评测机每秒处理基本操作10^8次左右，所以将题目最大数据带入O(f(n))就基本可以估计出是否会超时。 试分析三个算法的时间复杂度 ?1.f[0]=f[1]=1, f[2]=2; for (i=3; i=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 || j==i) f[i][j]=1; else f[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)。 算法三的基本操作数为12+22+32+…+n2=1/6·n·(n+1)·(2n+1)，时间复杂度为O(n3)。 试分析递归算法的时间复杂度 int f?(int x) { if (x == 2) return 2; if (x 2) return 1; return f(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题目对空间方面一般不会有太严格的要求，只要保证程序申请的内存空间小于题目要求就行了。不过这个不能随便估计要精确计算。 再普及一下应该都知道的知识： char = 1 B short = 2B int = 4 B double = 8 B long long = 8 B 1MB = 1024 KB = 1024*1024 B 时空权衡 一般来说可以通过花费更多的空间换取更少的时间，或者花费更多的时间换取更少的空间。 我们要根据要求来时空权衡设计算法。 这一点大家会在今后学习更多的算法后得到体会，这里就不深入讲解了。 枚举 所谓枚举法，指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 枚举是一种确定范围后的搜索。枚举的几个主要步骤如下：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围；利用循环语句、条件判断语句逐步求解或证明。 枚举的优点是简单、直观、便于理解和证明。主要缺点就是计算规模大，效率低下。 但枚举类的题目不一定简单，在有多种枚举策略的时候，要分析每种策略的优劣，选取最好