时间复杂度与空间复杂度分析-526互联

noip模拟赛爆空间真难受。。。。

空间常数

1Byte=8bit(位)。KB,MB,TB......采用1024进制。

short	2字节	(-2¹⁵~2¹⁵) 整数型
int	4字节	(-2³¹~2³¹) 整数型
long long	8字节	(-2⁶³~2⁶³) 整数型
unsigned long long	8字节	[0~2⁶⁴) 整数型
char	1字节	(0~256) ascll码
bool	1字节	true(1) 或 false(0)
float	4字节	单精度浮点数
double	8字节	双精度浮点数
long double	未知	未知

例：int a[1e8]约占381MB（100000000*4/1024²）。(考场一般512MB，数组最好不超过1e8)

如何在代码中快速有效计算空间呢？

#include<bits/stdc++.h>
const int maxn=1e7;
using namespace std;
bool st;
int a[maxn];
int b[maxn];
double c[maxn];
bool end;
int main(){
    printf("%dMB",(&end-&st)/(1024*1024));
    return 0;
}

时间常数优化的一些小trick

1.快读&&快输

int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
    return s*f;
}

2.STL的巨大常数(sort除外)so必要时自己手写。

#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
#define sight(c) ('0'<=c&&c<='9')
#define swap(a,b) a^=b,b^=a,a^=b

bitset：

struct bitsets{
    long long t[4];
    void set(int x){
        int aa,bb;
        aa=x/60;bb=x%60;
        this->t[aa]|=1LL<<bb;
    }
    void reset(){
        this->t[0]=0;
        this->t[1]=0;
        this->t[2]=0;
        this->t[3]=0;
    }
    void ad(const bitsets &g){
        this->t[0]&=g.t[0];
        this->t[1]&=g.t[1];
        this->t[2]&=g.t[2];
        this->t[3]&=g.t[3];
    }
    void oo(const bitsets &g){
        this->t[0]|=g.t[0];
        this->t[1]|=g.t[1];
        this->t[2]|=g.t[2];
        this->t[3]|=g.t[3];
    }
    void xo(const bitsets &g){
        this->t[0]^=g.t[0];
        this->t[1]^=g.t[1];
        this->t[2]^=g.t[2];
        this->t[3]^=g.t[3];
    }
    bool tr(const bitsets &g){
        bool top=true;
        top&=((this->t[0]&g.t[0])==0);
        top&=((this->t[1]&g.t[1])==0);
        top&=((this->t[2]&g.t[2])==0);
        top&=((this->t[3]&g.t[3])==0);
        return top;
    }
};

3.循环优化。

for (i=1;i<=b;i++)

这样写是很慢的。

for (int i=1;i<=b;i++)

快一丢丢。

4.位运算优化。

if (a^b) 等价于 if (a!=b)
if (!(a^b)) 等价于 if (a==b)

5.多维数组循环。

int a[100001][51];
for(int i=1;i<=50;i++){
    for(int j=1;j<=100000;j++){
        a[j][i]++;
    }
}
慢于
int a[51][100001];
for(int i=1;i<=50;i++){
    for(int j=1;j<=100000;j++){
        a[i][j]++;
    }
}

主要是因为数组的地址是连续的，但连续访问第一维时地址却是跳跃的（更慢）。

比如a[1][1],a[1][2],a[1][3],a[1][4]....a[2][1].中a[1][1]与a[2][1]的地址相隔甚远。

memset，sizeof，strlen是O(n)的时间复杂度。

length()是O(1)的,但string的运算慢于char数组。