算法分析与枚举策略.ppt

ACM Group,算法分析与枚举策略,程序设计实践,算法的分析方法,简单性 健壮性 效率时间复杂度 占用空间空间复杂度,算法的时间复杂度,一个算法对特定输入的时间复杂性是该算法对该输入产生结果需要的基本操作或“步”数。 假设我们求出算法过程中执行基本操作的次数，为c(n)次。我们进一步规定在特定计算机上算法的基本操作的执行时间为t，则可以估计出整个算法的运行时间Ttc(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)。例如3n4+8n2+n+2=O(n4)，其中f(n)=n4。,关于时间复杂度的两个表,Accepted or TLE,一般来说评测机每秒处理基本操作108次左右，所以将题目最大数据带入O(f(n)就基本可以估计出是否会超时。,试分析三个算法的时间复杂度,1.f0=f1=1, f2=2; for (i=3; i=n; i+) fi=fi-1+fi-3; 2.for (i=1; i=n; i+) for (j=1; j=i; j+) if (j=1 | j=i) fij=1; else fij=fi-1j+fi-1j-1; 3.for (i=1; i=n; i+) for (j=1; j=i*i; j+) fj+;,试分析三个算法的时间复杂度,算法一的基本操作数为n-2，时间复杂度为O(n)。 算法二的基本操作数为（1+2+3+n）=n（n+1）1/2=1/2n2+1/2n，时间复杂度为O(n2)。 算法三的基本操作数为12+22+32+n2=1/6n(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,时空权衡,一般来说可以通过花费更多的空间换取更少的时间，或者花费更多的时间换取更少的空间。 我们要根据要求来时空权衡设计算法。 这一点大家会在今后学习更多的算法后得到体会，这里就不深入讲解了。,枚举,所谓枚举法，指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。 枚举是一种确定范围后的搜索。枚举的几个主要步骤如下：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围；利用循环语句、条件判断语句逐步求解或证明。 枚举的优点是简单、直观、便于理解和证明。主要缺点就是计算规模大，效率低下。 但枚举类的题目不一定简单，在有多种枚举策略的时候，要分析每种策略的优劣，选取最好的策略来满足题目的要求。,简单的例题,HOJ 1128 HOJ 1459,例1 统计问题,x+2y+3z = 200，求正整数解的个数。 三种枚举方法： 可以比较一下优劣 枚举x，枚举y，枚举z，验证。 枚举x，枚举y，验证200-x-2y整除3。 枚举y，枚举z，统计即可。,例题2 时钟,考虑将如此安排在一个33行列中的九个时钟。目标要找一个最小的移动顺序次将所有的指针指向12点。下面图中列出了9种不同的旋转指针的方法，每一种方法都叫一次移动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。,输入文件共包含三行，每行三个空格分开的数字，每个数字表示一个时钟的初始时间：3,6,9,12。 输出文件包含单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。如果有多种方案，输出那种使的连接起来数字最小的方案。(举例来说52469311)。,HOJ 1827,例题2 时钟,每移动一次，时针将顺时针旋转90度。由此我们可以得出：对于任意一个时钟i（1i9）来说，从初始位置j出发至少需要Ci=（4-j） mod 4次操作，才能使得时针指向12点。而对每种移动方法要么不采用，要么采用1次、2次或3次，因为操作四次以后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态，可以建立时钟控制表后枚举。,例题2 时钟,显然这种枚举规模比较大，效率比较低。由于最终的状态是确定的，我们可以枚举一部分，并作为已知去推出另一部分。仔细观察可以发现：P4P9可直接由P1，P2，P3求出： P4=order(C1-P1-P2) P5=order(C2-P1-P2-P3) P6=