空间复杂度

空间复杂度就是你的程序占用了多少空间。

$1GB=1024MB$

$1MB=1024KB$

$1KB=1024B$

$1B=8bit$

一个 int 类型的范围一般是 $(-2^{31})\sim (2^{31}-1)$，总共 $2^{32}$ 个数字，占用 $32$ 个 $bit$，也就是 $4$ 个$B$。

所以一般情况下，$128MB$ 大约最多开 $128\ast 1024\ast 1024/4=33,554,432$ 个int 变量，大约三千万。

每道题都有一定的内存限制，注意数组的开设大小。

如果你开的空间超过了内存限制，会爆出 MLE 错误，表示内存超限。

如果你访问到了没有定义的数组范围，比如定义了 a[100] 而访问了 a[110]，那么会爆 RE 错误，表示访问越界。

时间复杂度

我们的计算机一秒大约能跑五千万次运算。

什么是一次运算？

a=b+c;

就算一次运算。

所以大额时间复杂度的来源主要在于循环和递归，一般手写是绝对写不到五千万的。

时间复杂度一般采用大 $O$ 计数法，忽略常数，且只保留在增长意义下数量级最大的式子。

for(int i=1;i<=n;++i)
{
	cin>>a[i];
}

这个循环执行了 $n$ 次，所以时间复杂度是 $O(n)$。

for(int i=1;i<=n;++i)
{
	cin>>a[i];
    a[i]*=2;
}

这个循环执行了 $n$ 次，每次两个操作，时间复杂度仍然是 $O(n)$。

因为 $2\ast n$ 和 $n$ 在 $n$ 增长时，数量级并没有明显的变化，对于比较小的常数可以忽略。

for(int i=1;i<=n;++i)
{
	for(int j=1;j<=m;++j)
	{
		cin>>a[i][j];
	}
}

这个时间复杂度是$O(nm)$。

for(int i=1;i<=n;++i)
{
	for(int j=1;j<=100;++j)
	{
		cin>>a[i][j];
	}
}

这个时间复杂度是$O(100n)$。

为什么这个 $100$ 没有省去呢，因为这里的$100$ 相比于 $n$ 已经有相当的规模了。

考虑到我们一秒只能跑 $5\ast {10}^7$ 次 ，所以 $100$ 相比于数据规模 $n$ 并不是一个可以忽略的数字。

for(int i=1;i<=n;++i)
{
	for(int j=1;j<=n;++j)
	{
		for(int k=1;k<=n;++k)
		{
			cin>>a[i][j][k];
		}
	}
    for(int p=1;p<=2*n;++p)
    {
        ++ans;
    }
}

这份的时间复杂度是 $O(n(n^2+2n))$，根据只保留 $n$ 增长意义下最大的数量级，所以这份代码的时间复杂度是 $O(n^3)$。

int n;cin>>n;
int sum=0;
while(n) n/=2,++sum;

这个时间复杂度是$O(logn)$。

不写底数是因为，从时间复杂度的角度来看，底数的大小（只要大于等于$2$）对数值大小的影响比较小，所以一般简称为 $O(logn)$。

如果严谨一点，也可以指出是 $O(lo{g}_{2}n)$或者 $O(lo{g}_{10}n)$。

如果你的算法运行时间过长，会爆 TLE 错误，表示运行超时。

枚举

不同的枚举方式往往花费的时间也不同。

例一：

给定长度为 $n$ 的数组 a[1]~a[n]，有多少对不同的数字$(i,j)$，满足 a[i]+a[j]==0 ？

$n\le 1000$

$-1000\le a[i]\le 1000$。

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
}

先做一点准备工作，读取一个长度为 $n$ 的数组。

然后最朴素的方法是：

for(int i=1;i<=n;++i)
{
	for(int j=1;j<=n;++j)
	{
        if(i==j) continue;
		if(a[i]+a[j]==0) ++ans;		
	}
}

这样是 $O(n^2)$

考虑到如果 a[i]+a[j]==0 ，那么对称地 a[j]+a[i]==0，所以可以先算 $i<j$ 的答案，然后将答案乘以二。

for(int i=1;i<=n;++i)
{
	for(int j=i+1;j<=n;++j)
	{
		if(a[i]+a[j]==0) ++ans;
	}
}
ans=ans*2;

这样时间复杂度变成了$0+1+2+\dots \dots +n-1=\frac{n\ast (n-1)}{2}=O(n^2)$

虽然理论复杂度没变，但实际上快了不少。

然而考虑到数字的范围不大，还可以用数组存储每个数字出现过多少次：

for(int i=1;i<=n;++i)
{
    a[i]+=1000;//消除负数，把问题变成求有多少对数字和等于2000
}
//定义cnt[i]表示数字 i 出现过多少次
for(int i=1;i<=n;++i)
{
	int t=2000-a[i];//另一个数字的大小应该是多少
    if(t>=0&&t<=2000) ans+=cnt[t];
    //前面的判断防止访问越界
}
ans=ans*2;

这样时间复杂度就变成了 $O(n)$。

例二：

求 1~n 每个数字分别有多少个因数。$1\le n\le 1000$。

暴力做法：

for(int x=1;x<=n;++x)
{
	for(int i=1;i<=x;++i)
	{
		if(x%i==0) ++ans[x];
	}
}

这样复杂度就是 $1+2+\dots \dots +n=O(n^2)$。

考虑一个性质：如果 $p\ast q=x$，且 $p\le q$ ，那么必然存在 $p\le \sqrt{x}$。

证明：如果 $\sqrt{x}<p\le q$，那么 $p\ast q>\sqrt{x}\ast \sqrt{x}=x$。

所以枚举因数的时候只需要枚举小于等于$\sqrt{x}$ 的因数，另一个因数是和它成对出现的。

for(int x=1;x<=n;++x)
{
	for(int i=1;i*i<=x;++i)
    {
        if(x%i==0) ++ans[x];
        if(i*i!=x) ++ans[x];//如果不是刚好根号，则对称的还有一个因数
    }
}

这样每个数字只要枚举到根号，总时间复杂度 $O(n\sqrt{n})$。

还有一个枚举思路：枚举一个数字，然后判断它是多少个数字的因子：

for(int i=1;i<=n;++i)
{
	for(int x=i;x<=n;x+=i)
	{
		++ans[x];
	}
}

虽然还不知道这样的时间复杂度是多少，但是显然上面两种枚举方法中，有些循环到的情况是不产生贡献的（不满足判断条件），而最后这种枚举方法每个循环到的地方都产生了贡献，效率应该是更高的。

这样的循环次数是 $n+\frac{n}{2}+\frac{n}{3}+\dots \dots +\frac{n}{n}=n(1+\frac{1}{2}+\frac{1}{3}+\dots +\frac{1}{n})$。

后面这个式子被称为调和级数，当 $n$ 趋向于无穷时，该式子的和趋向于 $O(logn)$。

可以用积分近似计数该式子的值：

$$\sum _{i=1}^n\frac{1}{n}\approx {\int }_1^{n+1}\frac{1}{x}dx=ln(n+1)$$

所以总体复杂度约等于 $O(nlogn)$ 比之前两种方法都快。

调和级数是算法中降低复杂度常用的枚举技巧，一定要学会。

简单来说就是先枚举数字，再枚举它的因子变成先枚举因子，再枚举倍数。

例三：

P1217 [USACO1.5] 回文质数 Prime Palindromes

因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

写一个程序来找出范围 $[a,b](5\le a<b\le 100,000,000)$（一亿）间的所有回文质数。

如果按如下方式：

for(int i=a;i<=b;++i)
{
	if(isprime(i)&&isreverse(i)) ++sum;
}

我们默认判断一个数是不是质数的时间复杂度是$O(\sqrt{n})$，判断一个数是不是回文的时间复杂度是 $O(logn)$

那么这份代码时间复杂度就是 $O(b\ast (\sqrt{b}+log{10}^8))$

粗算一下，${10}^8\ast (\sqrt{{10}^8}+lo{g}_{10}{10}^8)={10}^8\ast ({10}^4+8)\approx {10}^{12}$。

显然大于 $5\ast {10}^7$，因此不能通过。

优化以下算法，我们枚举一个数字的前一半，然后根据它回文的性质，去生成后一半。

for(int i=1;i<10000;++i)
{
	//以i为前一半，生成完整的数字x
	if(isprime(x)) ++sum;
}

这样时间复杂度就变成了

$O(\sqrt{b}\ast (\sqrt{{10}^8}+log{10}^8))$

粗算：${10}^4\ast ({10}^4+4)\approx {10}^8$。

然而因为并不是每次都对最大值 $b$ 做判断质数，所以实际复杂度远比这里估算的上界要小，结合每秒运行 $5\ast {10}^7$ 次可以通过。