《算法分析与枚举策略ppt课件》由会员分享，可在线阅读，更多相关《算法分析与枚举策略ppt课件（20页珍藏版）》请在装配图网上搜索。
1、算法的分析方法算法的分析方法简单性强健性效率时间复杂度占用空间空间复杂度算法的时间复杂度算法的时间复杂度一个算法对特定输入的时间复杂性是该算法对该输入产生结果需求的根本操作或“步数。假设我们求出算法过程中执行根本操作的次数，为c(n)次。我们进一步规定在特定计算机上算法的根本操作的执行时间为t，那么可以估计出整个算法的运转时间Ttc(n)。时间复杂度只能衡量c(n)相对于n的增长速度情况，和t没有直接关系。但思索整个算法的运转时间时千万不要忽略了根本操作的执行时间t。时间复杂度的规定时间复杂度的规定设f(n)是关于n的函数，我们用关于f(n)的一个函数来表示算法的渐进时间复杂度。严峻的定义是这
2、样的：假设存在两个正常数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)还是很多，为还是很多，为了方便准
3、确的表示时间复杂度，了方便准确的表示时间复杂度，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+)f
4、i=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=nn+11/2=1/2n2+1/2n，时间复杂度为O(n2)。算法三的根本操作数为12+22+32+n2=1/6n(n+1)(2n+1)，时间复杂度为O(n3)。试分析递归算法的时间复杂度试分析递归算法的时间复杂度in
5、t 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=2Bin
6、t=4 B double=8 B long long=8 B1MB=1024 KB=1024*1024 B 时空权衡时空权衡 普通来说可以经过破费更多的空间换取更少的时间，或者破费更多的时间换取更少的空间。我们要根据要求来时空权衡设计算法。这一点大家会在今后学习更多的算法后得到领会，这里就不深化讲解了。枚举枚举所谓枚举法，指的是从可以的解集合中一一枚举各元素,用标题给定的检验条件断定哪些是无用的，哪些是有用的。能使命题成立，即为其解。枚举是一种确定范围后的搜索。枚举的几个主要步骤如下：对命题建立正确的数学模型；根据命题确定的数学模型中各变量的变化范围；利用循环语句、条件判别语句逐渐求解或证明。
7、枚举的优点是简单、直观、便于了解和证明。主要缺陷就是计算规模大，效率低下。但枚举类的标题不一定简单，在有多种枚举战略的时候，要分析每种战略的优劣，选取最好的战略来满足标题的要求。简单的例题简单的例题HOJ 1128HOJ 1459 例例1 1 统计问题统计问题x+2y+3z=200，求正整数解的个数。三种枚举方法：可以比较一下优劣枚举x，枚举y，枚举z，验证。枚举x，枚举y，验证200-x-2y整除3。枚举y，枚举z，统计即可。例题例题2 2 时钟时钟思索将如此安排在一个33行列中的九个时钟。目的要找一个最小的挪动顺序次将一切的指针指向12点。下面图中列出了9种不同的旋转指针的方法，每一种方法
8、都叫一次挪动。选择1到9号挪动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。输入文件共包含三行，每行三个空格分开的数字，每个数字表示一个时钟的初始时间：3,6,9,12。输出文件包含单独的一行包括一个用空格分开的将一切指针指向12:00的最短挪动顺序的列表。假设有多种方案，输出那种使的衔接起来数字最小的方案。(举例来说52469311)。HOJ 1827例题例题2 2 时钟时钟每挪动一次，时针将顺时针旋转90度。由此我们可以得出：对于恣意一个时钟i1i9来说，从初始位置j出发至少需求Ci=4-j mod 4次操作，才干使得时针指向12点。而对每种挪动方法要么不采用，要么采用1次、2次或
9、3次，由于操作四次以后，时钟将反复以前外形。因此，9种旋转方案最多产生49个外形，可以建立时钟控制表后枚举。例题例题2 2 时钟时钟显然这种枚举规模比较大，效率比较低。由于最终的外形是确定的，我们可以枚举一部分，并作为知去推出另一部分。仔细察看可以发现：P4P9可直接由P1，P2，P3求出：P4=order(C1-P1-P2)P5=order(C2-P1-P2-P3)P6=order(C3-P2-P3)P7=order(C4-P1-P4-P5)P8=order(C8-P5-P7-P9)P9=order(C6-P3-P5-P6)这样一来，我们只需求枚举C1，C2和C3就可以了。外形总数为43。可以说，优化的效果很明显。谢谢谢谢
算法分析与枚举策略ppt课件
