第八单元简单算法时空分析

第八单元简单算法时空分析8.1算法分析的概念算法分析是指通过数学方法对一个算法的时间效率和空间效率经行评估，并判断该算法的优劣。如果算法A的时空复杂度均低于算法B，那么我们认为算法A优于算法B。有时也有以空间换时间或者以时间换空间的算法，比如暴搜和记忆化搜索，前者是以时间换空间的算法，而后者是以空间换时间。算法的设计要求：正确性程序不含语法错误；程序对几组输入数据能够得出满足规格要求的结果；程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；程序对一切合法的输入数据都能产生满足规格要求的结果。可读性：有助于阅读和交流、有助于对算法的理解、有助于对算法的调试和修改。高效率和低存储：处理速度快、存储容量小。8.2时间复杂度时间复杂度，从名字就可以知道，它表示的是算法运行的时间效率。一个算法运行所耗费的时间，除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。一个算法中所有语句的频度之和构成了该算法的运行时间。以下为几个代码例子，我们依次分析它们的基本操作次数，并尝试分析时间复杂度。【代码分析例1】fact=1;for(inti=1;i<=n;i++)fact=fact*i;一次乘法为一个基本操作，忽略i改变的时间。共f(n)=n次基本操作。时间复杂度为n【代码分析的例子2】sum=0;for(inti=1;i<=n;i++)for(intj=1;j<=n;i++) //这里的a[i][j]是二维数组，我们认为a数组存储了n*n个变量。sum=sum+a[i][j];基本操作：加法，乘法，忽略循环变量i和j的改变时间，共n^2次基本操作。时间复杂度为n^2【代码分析的例子3】这段代码实现的是1!+2!+……+n!sum=0;for(inti=1;i<=n;i++){fact=1;for(intj=1;j<=i;i++)fact=fact*jsum:=sum+fact;}第i次循环执行了i个操作,总时间复杂度为1+2+3+…+n=n(n+1)/2。这个式子我们可以约等于n^2/2。如果式子再长一点，怎么办？比较【例2】和【例3】，【例2】执行了f(n)=n^2次基本操作，【例3】执行了g(n)=n^2/2次基本操作。那个算法好呢？算法二好，因为g(n)<f(n)增长情况呢？n扩大10倍，f(n)扩大100倍，g(n)也扩大100倍。两个算法的增长情况一样！我们其实更在乎数据规模扩大，时间随着n增加的渐进时间复杂度。对于例2和例3，根据其执行次数与n的关系：f(n)=n^2和g(n)=n^2/2。我们知道，它们的增长情况一样。如何表示“增长情况”？把f(n)和g(n)变成“渐进”形式，然后直接比较。如何变成“渐进”形式？1）只保留最“大”项；2）忽略系数例1：3n^4+8n^2+n+2的渐进时间复杂度为n^4例2：2^(n+1)+n*100+5的渐进时间复杂度为2^n(为什么n+1变成了n？)有时候复杂度分析不是万能的，或者说有时候不知道最坏情况是多少。我们看一下OJ【P1029】一个数n，如果它是奇数则变换到3n+1，否则变换到n/2。给一个数n，不停的变换下去，经过几步变成1？你知道它的运行时间吗?!反正我不知道，这是个著名的停机问题所以，我们在分析时间复杂度的时候，只分析上限，而不管实际运行时间。若n充分大时|f(n)|<=c|g(n)|，其中c为某常数。记f(n)=O(g(n))，表示g(n)为f(n)的渐进上限例1：5n^2+3n+1=O(n^2)例2：2n^3=O(n^3)由于上限有无限多个，我们希望它尽量精确。否则我们的分析就过于悲观了，实际算法没那么糟糕。 这就是我们常说的时间复杂度，一般用最坏的时间复杂度来衡量一个程序的效率。常见的复杂度等级：绝大多数算法都是多项式算法O(n^t)，t是常数O(log(t)n),t是常数O(loglogn),奇怪吗？后面会遇到一个两个多项式时间复杂度的积仍是多项式的复杂度效率排序，越靠左边，效率越高。O(1)<O(loglogn)<O(logn)<O(sqrt(n))<O(n)O(n)<O(nloglogn)<O(nlogn)<O(n^2)O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)O(1)：表示复杂度为常数。(常数级)O(N)：表示复杂度为N。(线性级)O(N^i)：N^i表示N的i次幂。(多项式级)O(sqrt(N))：表示根号N，即N开方。(多项式级)O(logN)：表示以2为底数N的对数。(对数级)O(i^N)：表示i的N次幂。(指数级)O(N!)：表示N的阶乘，即N!=1*2*3*…*N。(阶乘级)强调：这里的logn的对数底不是10，而是2，也就是log2(n)。这个是要记住的。以后再学相应的算法，我们就要学着分析算法的时间效率。考试时的参考：我们知道，考试时1s的运行次数是10^8次，那么我们就要根据数据规模来判断算法。如果数据规模在100以内，三重循环就不会超时。如果数据规模在9000以内，二重循环就不会超时。如果数据规模在10000以上，你的程序就必须要考虑1重循环了，或者n*logn的算法。8.3空间复杂度空间复杂度指的是实现算法的空间开销，同样使用多项式来表示。最主要的体现就是数组，数组的大小即为该算法的空间复杂度。（1）计算机基本计量单位计算机最基本单位为字节(Byte)，计算机最小的单位是位（bit）一个int数据占8个B。1024B=2^10B=1KB1024KB=2^20B=1MB1024MB=2^30B=1GB50M的内存限制可以定义50*1024*1024/4个int变量约等于1000万长度的int数组（2）一般的估算说到空间复杂度，其实主要担心就是会不会爆内存。这里有一个很简单的方法就可以确定：在C/C++里面有sizeof()这个函数(Pascal里面应该也有)，它返回的是变量的字节数，比如说sizeof(int)，就会告诉你int所占用的空间大小；sizeof(a)，其中a是一个数组，这时返回的就是数组a的总空间大小。对于一个已经写好的程序，我们把它所有静态数组的sizeof()全部加起来，然后除上10^6，得到的数字就是所占用的静态内存MB数，有没有爆内存自然一目了然。8.4空间换时间实例现代计算机的内存空间的增加要超过运算速度增加，我们现在的题目，一般都是空间不会超，时间可能会超。所以，我们更多的考虑算法的时候，一般会考虑用空间换时间来将问题。【P1058】陶陶刚学了数组，并且他对查找一维数组中的最大值特别感兴趣，于是，他就产生了疑问：能不能找到数组中某个元素的左边的最大值、右边的最大值和不包含自身的最大值。

例如：一个数组共8个元素，

1

3

7

8

4

3

61

第5个数（4）左边的最大值是8

右边最大值是6，不包含自身的最大值是8输入格式：第一行为n,k(n表示数组含有n个元素,k表示有k次查询)(n<=100,k<=50)

第二行为n个整数,表示数组的n个元素

第三行为k个整数表示对数组的k次查询输出格式：n行整数,每行三个整数分别为:左边最大值,右边最大值,不包含自身的最大值输出样例：868输出样例：868818821378436157｛查询了２次，第５个数和第７个数｝【分析】本题就是要找ｋ次最大值，根据我们的经验，按照要求，提问一次，找一次。就可以得到结果。这种查询在以后的题目中经常用到。 本次给的例子还是用函数来将主程序给分成了几段，再次强调这种写程序的思路。#include<iostream>usingnamespacestd;intn,k,m,a[110],max3;voidinit(){ cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i];}voidwork(){for(inti=0;i<m;i++){ cin>>k; intmaxleft=-10000,maxright=-10000;for(intj=1;j<=k-1;j++)if(maxleft<a[j])maxleft=a[j];for(intj=k+1;j<=n;j++)if(maxright<a[j])maxright=a[j]; if(maxleft>maxright)max3=maxleft; elsemax3=maxright; cout<<maxleft<<''<<maxright<<''<<max3<<endl; }}intmain(){init();//读入数据work();//计算return0;}上面这个程序的时间复杂度是O(n*k)。题目给的n最大为100，k最大为50，所以最大计算次数为100*50。程序在1s之内是肯定不会超时。我们来看【p1059】，数据量n到达了500000，k到了50000的数据量。用以上思路，最大计算次数是500000*50000，2.5*10^9。这么多运算次数1s（10^8）肯定是不够的。我们必须调整思路，对程序进行相应的优化。我们上面程序为什么费时间，就是每次查询都会重新查找一次，而每次的查找其实有很多重复计算。我们试着来避免这些重复，而要避免重复计算就是提前将可能要查询的答案预先处理出后存储起来，这样查询的时候，就不必重新查找了。我们定义leftmax[]，rightmax[]两个数组，leftmax[i]表示第i个元素左边的最大值是多少，rightmax[i]表示第i个元素右边的最大值是多少。 我们在查询之前将leftmax和rightmax都计算出来，查询的时候，只需要输出结果即可。 那么如何预处理这两个数组呢？如果还是每个leftmax[i]都用一次循环，那么这个程序的效率依然很差，我们需要用更高效率的代码来求出这两个数组。 我们观察样例：i12345678a13784361Leftmax01378888RightmaxRightmax自己去填。我们可以发现一个现象：leftmax[i]=max(a[i-1],leftmax[i-1])。这个式子可以让我们用一重循环来求出leftmax。同理，肯定也能求出rightmax。这样我们我们的代码的运算次数基本就是n+n+k。这样肯定就不会超时。代码下面给出，请理解这种思想。#include<iostream>usingnamespacestd;inta[501000],leftmax[501000],rightmax[501000];intn,k,m,maxx=0;voidinit(){cin>>n>>k;a[0]=0;a[n+1]=0;for(inti=1;i<=n;i++)cin>>a[i];}voidwork(){for(inti=1;i<=n;i++)//预处理leftmaxif(a[i-1]>=leftmax[i-1])leftmax[i]=a[i-1];elseleftmax[i]=leftmax[i-1];for(inti=n;i>=1;i--)//预处理rightmaxif(a[i+1]>=rightmax[i+1])rightmax[i]=a[i+1];elserightmax[i]=rightmax[i+1];for(inti=1;i<=k;i++){cin>>m;if(leftmax[m]>rightmax[m])maxx=leftmax[m];elsemaxx=rightmax[m];cout<<leftmax[m]<<''<<rightmax[m]<<''<<maxx<<endl;}}intmain(){init();work();return0;}【P1061】数组求和陶陶学了数组以后，他对数组之间的累加和特别感兴趣，于是他就提出了要求数组元素之间的累加和的问题。

例如：现在有长度为10的数组：3251453782

从第2个元素到第5个元素的和就是2+5+1+4=12

从第4个元素到第9个元素的和就是

1+4+5+3+7+8=28输入格式；第一行nk两个正整数,分别表示数组有n个元素,k次求和查询(0<=n,k<=1000)第二行为n个整数数组的n个元素以下有k行,每行两个元素,为求和的起点和终点输出格式：k行,每行为起点到终点的和.【分析】这道题的n和k最大只为1000，所以，我们可以用两重循环根据每次查询来完成此题，到这里，我们应该具备这种能力。并参考上面代码的形式，用函数来写。【P1062】本题是1061的加强版，n和k的上限到了100000。用两重循环写的话，会超时的一塌糊涂，我们必须尝试调整思路，进行优化。 在求部分和的时候，经常用的思想就是线转换点的思想。我们提前预处理一个sum数组，sum[i]表示前i项的累加和。i12345678910a3251453782Sum351011152023303840如果我们要求第2项到第5项的累加和只需要做一次减法即可：sum[5]-s[1]=12同理，第4项到第9项的累加和就是sum[9]-sum[3]=28。在本例中，我们利用提前预处理一个sum数组，就可以让求部分区间累加和的那重循环给省略掉，这样极大的提高了程序的效率。这就是一种典型的空间换时间思想。 以上两道题的数据量加大后，我们都