专栏文章

时空复杂度分析及master定理

CChanis
算法·理论参与者 81已保存评论 98

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
98 条
当前快照
1 份
快照标识符
@mhz5rowf
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
#时空复杂度分析及master定理
###●QQ826755370
###●如果您会简单的内容，那么您可以直接跳到master定理了。
##引入
不同的题目有不同的解法，那么我们该如何评价每种解法的优劣呢？此时我们就需要引入两个概念，一个是时间复杂度，另一个是空间复杂度。
##时间复杂度
###概念
这里我们介绍的是渐进时间复杂度，用符号OO表示。一个程序的语句执行次数可以用一个代数式表示，那么我们取这个代数式的最高次项且忽略此项系数作为时间复杂度。如果一个程序的语句执行次数为2n3+3n2+n+72n^3+3n^2+n+7，那么这个程序的渐进时间复杂度为O(n3)O(n^3)。
###栗子
1.以下代码中的sum+=a[i][j]sum+=a[i][j]会运行n2n^2次，所以该算法的时间复杂度为O(n2)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]sum+=a[i][j]会运行n2n^2次，pai∗=a[i][j]pai*=a[i][j]也会运行n2n^2次，所以总运行次数为2n22n^2，忽略系数，时间复杂度仍为O(n2)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])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])会运行n3n^3次，sum+=a[i][j]sum+=a[i][j]与pai∗=a[i][j]pai*=a[i][j]都会运行n2n^2次，所以总运行次数为n3+2n2n^3+2n^2,忽略低次项及最高次项系数，时间复杂度为O(n3)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∗1051e5=1*10^5，其他的式子同理。欸？表里好像混入了什么奇怪的东西（逃）。
数据范围
###非递归程序的时间复杂度计算技巧
对于非递归程序时间复杂度的运算方法，比较简单粗暴的方法是数循环。但这种方法并不一定始终正确，如NOIP2017PJT4的二分答案是O(logn)O(logn)复杂度的，dp的转移是执行nn次的，而对于单调队列，每个元素至多进队一次，出队一次，最多与2n2n次操作，dp的总操作次数应该是将它们加在一起，共3n3n次操作，时间复杂度为O(n)O(n)，而非O(n2)O(n^2)。所以std的时间复杂度为O(nlogn)O(nlogn)，与之类似的还有kmp算法的时间复杂度。
###符号
在介绍master定理前，我们需要介绍几个符号：
T(n)T(n)表示时间复杂度，我们可以这么表示时间复杂度：
T(n)=T(n)=下面的任意一个符号((一个单项式))。
ΘΘ，读音：theta，等于的意思。
OO，读音：big-oh，小于等于的意思。
oo，读音：small-oh，小于的意思。
ΩΩ，读音：big omega，大于等于的意思。
ωω，读音：small omega，大于的意思。
如果你不能完全理解的话，在目前我们参加的NOIP中，你可以把它们都理解为成OO。（逃）
###master定理——对于递归式的时间复杂度计算方法
现在我们介绍一个定理，它的名字叫达拉崩吧斑得贝迪卜多比鲁翁master定理，又名主定理，它的内容是这样的：我们将一个规模为nn的问题，通过分治得到aa个规模为nb\frac{n}{b}的子问题，每次递归带来的额外计算为f(n)f(n)，那么我们得到以下关系式：
T(n)=aT(nb)+f(n)T(n)=aT(\frac{n}{b})+f(n)
此外，我们定义一个ccritc_{crit}，它是这么计算的：
ccrit=logbac_{crit}=log_ba
那么存在以下关系：
●1.当f(n)=O(nc)f(n)=O(n^c)，且c<ccritc<c_{crit}时
T(n)=Θ(nccrit)T(n)=Θ(n^{c_{crit}})
e.g.
T(n)=8T(n2)+1000n2T(n)=8T(\frac{n}{2})+1000n^2
此时
a=8,b=2,f(n)=1000n2a=8,b=2,f(n)=1000n^2
当c=2c=2时
f(n)=O(nc)f(n)=O(n^c)
所以
c=2c=2
又因为
ccrit=logba=log28=3>cc_{crit}=log_ba=log_28=3>c
所以
T(n)=Θ(nlogba)=Θ(n3)T(n)=Θ(n^{log_ba})=Θ(n^3)
●2.若存在一个非负数kk，使得
f(n)=Θ(nccritlogkn)f(n)=Θ(n^{c_{crit}}log^kn)
那么
T(n)=Θ(nccritlogk+1n)T(n)=Θ(n^{c_{crit}}log^{k+1}n)
e.g.
T(n)=2T(n2)+10nT(n)=2T(\frac{n}{2})+10n
此时
a=2,b=2,f(n)=10na=2,b=2,f(n)=10n
ccrit=logba=log22=1c_{crit}=log_ba=log_22=1
当k=0k=0时
f(n)=O(nccritlogkn)f(n)=O(n^{c_{crit}}log^kn)
所以
T(n)=Θ(nccritlogk+1n)=Θ(n1log1n)=Θ(nlogn)T(n)=Θ(n^{c_{crit}}log^{k+1}n)=Θ(n^1log^1n)=Θ(nlogn)
●3.当f(n)=Ω(nc)f(n)=Ω(n^c)且c>ccritc>c_{crit}时
T(n)=Θ(f(n))T(n)=Θ(f(n))
e.g.
T(n)=2T(n2)+n2T(n)=2T(\frac{n}{2})+n^2
此时
a=2,b=2,f(n)=n2a=2,b=2,f(n)=n^2
当c=2c=2时
f(n)=Ω(nc)f(n)=Ω(n^c)
又因为
ccrit=logba=log22=1<cc_{crit}=log_ba=log_22=1<c
所以
T(n)=Θ(f(n))=Θ(n2)T(n)=Θ(f(n))=Θ(n^2)
对于master定理的第二种情况，它还有扩展，由于几乎用不到，所以我们仅做介绍：
●2a.当存在一个大于−1-1的kk时，使得
f(n)=Θ(nccritlogkn)f(n)=Θ(n^{c_{crit}}log^kn)
那么
T(n)=Θ(nccritlogk+1n)T(n)=Θ(n^{c_{crit}}log^{k+1}n)
●2b.当k=−1k=-1时，使得
f(n)=Θ(nccritlogkn)f(n)=Θ(n^{c_{crit}}log^kn)
那么
T(n)=Θ(nccritloglogn)T(n)=Θ(n^{c_{crit}}loglogn)
●2c.当存在一个小于−1-1的kk时，使得
f(n)=Θ(nccritlogkn)f(n)=Θ(n^{c_{crit}}log^kn)
那么
T(n)=Θ(nccrit)T(n)=Θ(n^{c_{crit}})
master定理的证明又长又臭，我也不会证，有兴趣的同学可以看这篇文章。
###初赛中的时间复杂度分析题选讲
NOIP初赛中的时间复杂度分析题就是授人以鱼，考人以鱽鱾鲀鱿鲃鲂鲉鲌鲄鲆鲅鲇鲏鲊鲋鲐鲈鲍鲎鲝鲘鲙鲗鲓鲖鲞鲛鲒鲚鲜鲟鲔鲕鲑鲧鲬鲪鲫鲩鲣鲨鲡鲢鲤鲠鲥鲦鲺鲯鲹鲴鲶鲳鲮鲭鲵鲲鲰鲱鲻鲷鲸鳋鳊鳁鳀鲾鲼鳈鳉鳃鳄鲿鳇鳂鳆鳅鲽鳌鳒鳎鳏鳑鳐鳍鳘鳛鳕鳓鳙鳗鳚鳔鳖鳜鳟鳞鳝鳡鳠鳢鳣鳤。
1.NOIP2016TGT14
关于这题，当年还闹出了一件很好玩的事：锅锅f。
题面1
根据主定理，此时
a=2,b=4,f(n)=n=n12a=2,b=4,f(n)=\sqrt{n}=n^\frac{1}{2}
ccrit=logba=log42=12c_{crit}=log_ba=log_42=\frac{1}{2}
当k=0k=0时
f(n)=O(nccritlogkn)f(n)=O(n^{c_{crit}}log^kn)
所以
T(n)=Θ(nccritlogk+1n)=Θ(n12log1n)=Θ(nlogn)T(n)=Θ(n^{c_{crit}}log^{k+1}n)=Θ(n^\frac{1}{2}log^1n)=Θ(\sqrt{n}logn)
选择C。
2.NOIP2015TGT10
题面2
解：
T(n)T(n)
=T(n−1)+n=T(n-1)+n
=T(n−2)+(n−1)+n=T(n-2)+(n-1)+n
=T(n−3)+(n−2)+(n−1)+n=T(n-3)+(n-2)+(n-1)+n
=T(0)+1+2+...+(n−2)+(n−1)+n=T(0)+1+2+...+(n-2)+(n-1)+n
=1+1+2+...+(n−2)+(n−1)+n=1+1+2+...+(n-2)+(n-1)+n
=1+(n+1)∗n2=1+\frac{(n+1)*n}{2}
=O(n2)=O(n^2)
选择D。
3.NOIP2013TGT7
题面3
其实这道题目是个智障题，由于：
f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2)
所以计算f(n)f(n)的次数也是计算f(n−1)f(n-1)与计算f(n−2)f(n-2)的次数和，我们设计算f(i)f(i)的次数为g(i)g(i)，那么：
g(n)=g(n−1)+g(n−2)g(n)=g(n-1)+g(n-2)
由于f(1)f(1)与f(2)f(2)已知 ，所以：
g(1)=1=f(1),g(2)=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)f(n)=f(n-1)+f(n-2),g(n)=g(n-1)+g(n-2)
所以：
g(n)=f(n)g(n)=f(n)
则：
T(n)=g(n)=f(n)=O(f(n))T(n)=g(n)=f(n)=O(f(n))
选择D。
###关于常数
常数即为我们忽略掉的T(n)T(n)中最高次项的系数与低次项所带来的时间消耗，可能在一个题目中，树状数组跑了900ms900ms，而线段树跑了1500ms1500ms，这时线段树就会超时。为了避免这种情况，我们需要在所有的正解中选择常数小的解法，还可以适当加一些卡常技巧，说到卡常，就不得不提wys与百度百科的卡常数词条（手动滑稽）。
##空间复杂度
###定义
空间复杂度类似于时间复杂度，我们还是用符号OO表示，下面代码的空间复杂度为O(n3)O(n^3)。
CPP
int matrix[n][n],sum[n],delta[n];
int a[n][n][n],ans,cnt;
bool vis[n][n];
###避免爆空间
现在的NOIP比赛中每道题目一般会给你256MB256MB的内存，当然也有可能给你128MB128MB、512MB512MB之类的内存。拿intint类型为例，一个int类型的变量占44个字节的空间，如果你的程序中的变量、数组全是intint类型的，且本题给你256MB256MB的空间，那么你的程序中最多能有的元素个数为：
256∗1024∗10244≈6∗107\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.自行用百度文库查找往年的初赛试题，只看定项选择题部分（时空复杂度分析题都在定项选择题里），把所有的时空复杂度分析题做一遍。
完结撒花！★,°:.☆(￣▽￣)/$:.°★ 。

评论

共 98 条评论，欢迎与作者交流。

正在加载评论...