复杂度分析及常用技巧

• 1. 时间复杂度
• 2. 空间复杂度
• 3. 常用技巧
• 4. Debug技巧

1. 时间复杂度

• C++语言1秒钟可以执行的操作次数是 10^7^~10^8^
• 时间复杂度的常数怎么理解？可以理解为代码的指令行数，如果循环内部指令行数>=10条一般认为常数比较大
• 根据题目给定的范围，反推应该使用什么样时间复杂度的算法：

2. 空间复杂度

• C++中最大空间限制为2147483647，即5e8（对int型），如果数据范围超过5e8就不要用数组
• 对64MB的存储空间，开一个n×n的int型二维数组，其n最大为8172

3. 常用技巧

1. a/b向上取整，可以用ceil(a/b)，但是这个函数的返回值是double类型的，所以需要强转，即int(ceil(a/b))，这样写非常繁琐，不如用 $a+b-1/b$ 表示向上取整

2. 类似的技巧还有 a%b 如何把余数限制为正数？只需要 (a%b+b)%b 就可以了，保证模数不变的同时使结果都变为正数

3. 优化输入输出速度，但速度依然不及scanf和printf

ios::sync_with_stdio(0); // 优化输入输出(取消关联)
cin.tie(0); // 加快输入
cout.tie(0); // 加快输出

4. cin后面不能马上跟getline，因为cin读不了换行符，而换行符是getline的结束符，所以要忽略换行符，用语句，或者getchar()读走这个换行符

cin.ignore();

5. 万能头文件(蓝桥杯也可用，前提是开C++11)

#include<bits/stdc++.h>

6. 图论无穷大：0x3f3f3f3f

• 在图论中，将距离数组初始化为0x3f3f3f3f是为了表示无穷大。这是因为0x3f3f3f3f的十进制值是1061109567，它是一个很大的数，但又不会溢出。这个值被用来表示无穷大，因为两个0x3f3f3f3f的和只比int类型的最大值小一点，这样在两个无穷相加时能够保证不会溢出，对于long long类型，则用0x3f3f3f3f3f3f3f3f。需要注意的是，用memset函数进行初始化时，只需要memset(dis, 0x3f, sizeof dis)即可，因为memset函数是按照字节来赋值的，所以这条语句默认赋值0x3f3f3f3f

7. 行数不固定的输入

while(scanf("%d%d",&a,&b)==2)
while(cin>>n && n)

4. Debug技巧

1. Segmentation Fault：段错误，多为数组越界导致的，且不输出任何额外的信息，此时可以借助exit(0)函数：在程序的任何位置直接退出，来排除是哪一步的问题
2. CE：编译错误，
3. RE：运行错误，数组越界或爆栈
4. TLE：时间超限
5. MLE：内存超限
6. PE：格式错误
7. OLE：输出超限，通常为没有删除调试语句

打赏