时空复杂度分析及master定理

#时空复杂度分析及master定理 ###●QQ826755370 ###●如果您会简单的内容，那么您可以直接跳到master定理了。 ##引入 不同的题目有不同的解法，那么我们该如何评价每种解法的优劣呢？此时我们就需要引入两个概念，一个是时间复杂度，另一个是空间复杂度。 ##时间复杂度 ###概念 这里我们介绍的是渐进时间复杂度，用符号$O$表示。一个程序的语句执行次数可以用一个代数式表示，那么我们取这个代数式的最高次项且忽略此项系数作为时间复杂度。如果一个程序的语句执行次数为$2n^3+3n^2+n+7$，那么这个程序的渐进时间复杂度为$O(n^3)$。 ###栗子 1.以下代码中的$sum+=a[i][j]$会运行$n^2$次，所以该算法的时间复杂度为$O(n^2)$。 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum+=a[i][j]; ``` 2.以下代码中的$sum+=a[i][j]$会运行$n^2$次，$pai*=a[i][j]$也会运行$n^2$次，所以总运行次数为$2n^2$，忽略系数，时间复杂度仍为$O(n^2)$。 ```cpp for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum+=a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) pai*=a[i][j]; ``` 3.以下代码中的$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])$会运行$n^3$次，$sum+=a[i][j]$与$pai*=a[i][j]$都会运行$n^2$次，所以总运行次数为$n^3+2n^2$,忽略低次项及最高次项系数，时间复杂度为$O(n^3)$。 ```cpp for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) sum+=a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) pai*=a[i][j]; ``` ###时间复杂度的应用 一般来说，我们所做的题目里就会给我们数据范围，这暗示了我们应该使用什么样的时间复杂度的算法，这里给出一张表格。关于极限范围，那东西只是大概的数值，究竟能做到多少我也不知道。注：$1e5=1*10^5$，其他的式子同理。欸？表里好像混入了什么奇怪的东西（逃）。  ###非递归程序的时间复杂度计算技巧 对于非递归程序时间复杂度的运算方法，比较简单粗暴的方法是数循环。但这种方法并不一定始终正确，如NOIP2017PJT4的二分答案是$O(logn)$复杂度的，dp的转移是执行$n$次的，而对于单调队列，每个元素至多进队一次，出队一次，最多与$2n$次操作，dp的总操作次数应该是将它们加在一起，共$3n$次操作，时间复杂度为$O(n)$，而非$O(n^2)$。所以std的时间复杂度为$O(nlogn)$，与之类似的还有[kmp算法](https://xcb.blog.luogu.org/aho-corasick-automaton-ac-zi-dong-ji)的时间复杂度。 ###符号 在介绍master定理前，我们需要介绍几个符号： $T(n)$表示时间复杂度，我们可以这么表示时间复杂度： $T(n)=$下面的任意一个符号$($一个单项式$)$。 $Θ$，读音：theta，等于的意思。 $O$，读音：big-oh，小于等于的意思。 $o$，读音：small-oh，小于的意思。 $Ω$，读音：big omega，大于等于的意思。 $ω$，读音：small omega，大于的意思。 如果你不能完全理解的话，在目前我们参加的NOIP中，你可以把它们都理解为成$O$。（逃） ###master定理——对于递归式的时间复杂度计算方法 现在我们介绍一个定理，它的名字叫~~达拉崩吧斑得贝迪卜多比鲁翁~~master定理，又名主定理，它的内容是这样的：我们将一个规模为$n$的问题，通过分治得到$a$个规模为$\frac{n}{b}$的子问题，每次递归带来的额外计算为$f(n)$，那么我们得到以下关系式： $$T(n)=aT(\frac{n}{b})+f(n)$$ 此外，我们定义一个$c_{crit}$，它是这么计算的： $$c_{crit}=log_ba$$ 那么存在以下关系： ●1.当$f(n)=O(n^c)$，且$c<c_{crit}$时 $$T(n)=Θ(n^{c_{crit}})$$ e.g. $$T(n)=8T(\frac{n}{2})+1000n^2$$ 此时 $$a=8,b=2,f(n)=1000n^2$$ 当$c=2$时 $$f(n)=O(n^c)$$ 所以 $$c=2$$ 又因为 $$c_{crit}=log_ba=log_28=3>c$$ 所以 $$T(n)=Θ(n^{log_ba})=Θ(n^3)$$ ●2.若存在一个非负数$k$，使得 $$f(n)=Θ(n^{c_{crit}}log^kn)$$ 那么 $$T(n)=Θ(n^{c_{crit}}log^{k+1}n)$$ e.g. $$T(n)=2T(\frac{n}{2})+10n$$ 此时 $$a=2,b=2,f(n)=10n$$ $$c_{crit}=log_ba=log_22=1$$ 当$k=0$时 $$f(n)=O(n^{c_{crit}}log^kn)$$ 所以 $$T(n)=Θ(n^{c_{crit}}log^{k+1}n)=Θ(n^1log^1n)=Θ(nlogn)$$ ●3.当$f(n)=Ω(n^c)$且$c>c_{crit}$时 $$T(n)=Θ(f(n))$$ e.g. $$T(n)=2T(\frac{n}{2})+n^2$$ 此时 $$a=2,b=2,f(n)=n^2$$ 当$c=2$时 $$f(n)=Ω(n^c)$$ 又因为 $$c_{crit}=log_ba=log_22=1<c$$ 所以 $$T(n)=Θ(f(n))=Θ(n^2)$$ 对于master定理的第二种情况，它还有扩展，由于几乎用不到，所以我们仅做介绍： ●2a.当存在一个大于$-1$的$k$时，使得 $$f(n)=Θ(n^{c_{crit}}log^kn)$$ 那么 $$T(n)=Θ(n^{c_{crit}}log^{k+1}n)$$ ●2b.当$k=-1$时，使得 $$f(n)=Θ(n^{c_{crit}}log^kn)$$ 那么 $$T(n)=Θ(n^{c_{crit}}loglogn)$$ ●2c.当存在一个小于$-1$的$k$时，使得 $$f(n)=Θ(n^{c_{crit}}log^kn)$$ 那么 $$T(n)=Θ(n^{c_{crit}})$$ master定理的证明又长又臭，我也不会证，有兴趣的同学可以看[这篇文章](http://www.doc88.com/p-9761826142176.html)。 ###初赛中的时间复杂度分析题选讲 ~~NOIP初赛中的时间复杂度分析题就是授人以鱼，考人以鱽鱾鲀鱿鲃鲂鲉鲌鲄鲆鲅鲇鲏鲊鲋鲐鲈鲍鲎鲝鲘鲙鲗鲓鲖鲞鲛鲒鲚鲜鲟鲔鲕鲑鲧鲬鲪鲫鲩鲣鲨鲡鲢鲤鲠鲥鲦鲺鲯鲹鲴鲶鲳鲮鲭鲵鲲鲰鲱鲻鲷鲸鳋鳊鳁鳀鲾鲼鳈鳉鳃鳄鲿鳇鳂鳆鳅鲽鳌鳒鳎鳏鳑鳐鳍鳘鳛鳕鳓鳙鳗鳚鳔鳖鳜鳟鳞鳝鳡鳠鳢鳣鳤。~~ 1.NOIP2016TGT14 关于这题，当年还闹出了一件很好玩的事：[锅锅f](http://www.noi.cn/newsview.html?id=557&hash=051291&type=1)。  根据主定理，此时 $$a=2,b=4,f(n)=\sqrt{n}=n^\frac{1}{2}$$ $$c_{crit}=log_ba=log_42=\frac{1}{2}$$ 当$k=0$时 $$f(n)=O(n^{c_{crit}}log^kn)$$ 所以 $$T(n)=Θ(n^{c_{crit}}log^{k+1}n)=Θ(n^\frac{1}{2}log^1n)=Θ(\sqrt{n}logn)$$ 选择C。 2.NOIP2015TGT10  解： $T(n)$ $=T(n-1)+n$ $=T(n-2)+(n-1)+n$ $=T(n-3)+(n-2)+(n-1)+n$ $=T(0)+1+2+...+(n-2)+(n-1)+n$ $=1+1+2+...+(n-2)+(n-1)+n$ $=1+\frac{(n+1)*n}{2}$ $=O(n^2)$ 选择D。 3.NOIP2013TGT7  其实这道题目是个智障题，由于： $$f(n)=f(n-1)+f(n-2)$$ 所以计算$f(n)$的次数也是计算$f(n-1)$与计算$f(n-2)$的次数和，我们设计算$f(i)$的次数为$g(i)$，那么： $$g(n)=g(n-1)+g(n-2)$$ 由于$f(1)$与$f(2)$已知 ，所以： $$g(1)=1=f(1),g(2)=1=f(2)$$ 又因为： $$f(n)=f(n-1)+f(n-2),g(n)=g(n-1)+g(n-2)$$ 所以： $$g(n)=f(n)$$ 则： $$T(n)=g(n)=f(n)=O(f(n))$$ 选择D。 ###关于常数 常数即为我们忽略掉的$T(n)$中最高次项的系数与低次项所带来的时间消耗，可能在一个题目中，树状数组跑了$900ms$，而线段树跑了$1500ms$，这时线段树就会超时。为了避免这种情况，我们需要在所有的正解中选择常数小的解法，还可以适当加一些[卡常技巧](https://blog.csdn.net/a1351937368/article/details/78162078)，说到卡常，就不得不提[wys](https://www.zhihu.com/search?type=content&q=%E7%8E%8B%E9%80%B8%E6%9D%BE)与[百度百科的卡常数词条](https://baike.baidu.com/item/%E5%8D%A1%E5%B8%B8%E6%95%B0/16211104?fr=aladdin)（手动滑稽）。 ##空间复杂度 ###定义 空间复杂度类似于时间复杂度，我们还是用符号$O$表示，下面代码的空间复杂度为$O(n^3)$。 ```cpp int matrix[n][n],sum[n],delta[n]; int a[n][n][n],ans,cnt; bool vis[n][n]; ``` ###避免爆空间 现在的NOIP比赛中每道题目一般会给你$256MB$的内存，当然也有可能给你$128MB$、$512MB$之类的内存。拿$int$类型为例，一个int类型的变量占$4$个字节的空间，如果你的程序中的变量、数组全是$int$类型的，且本题给你$256MB$的空间，那么你的程序中最多能有的元素个数为： $$\frac{256*1024*1024}{4} \approx 6*10^7$$ 虽然可以开这么大的数组，但是要注意，大数组请开成全局变量，开在函数里很有可能会爆栈导致RE。附一种数据类型占用空间及其数值范围的查询方式（以int为例）： ```cpp #include<iostream> #include<limits> using namespace std; int main() { cout<<sizeof(int)<<endl; cout<<numeric_limits<int>::min()<<endl; cout<<numeric_limits<int>::max(); return 0; } ``` ##作业 1.计算常用排序算法的一般情况、最差情况下的时空复杂度。 2.自行用百度文库查找往年的初赛试题，只看定项选择题部分（时空复杂度分析题都在定项选择题里），把所有的时空复杂度分析题做一遍。 完结撒花！*★,°*:.☆(￣▽￣)/$:*.°★* 。