一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。
在这种情况下，C++ 代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

1. $n \le 30$, 指数级别,

   dfs + 剪枝，数字排列， n皇后问题， 八数码问题

   状态压缩 dp，蒙德里安的梦想， 最短Hamilton路径

2. $n \le 100$ => $O(n^3)$，

   floyd，

   dp，

3. $n \le 1000$ => $O(n^2)$，$O(n^2logn)$，

   dp，

   二分，

   朴素版 Dijkstra、朴素版 Prim、Bellman-Ford

4. $n \le 10000$ => $O(n * \sqrt n)$，

   块状链表、分块、莫队

5. $n \le 100000$ => $O(nlogn)$

   各种 sort，线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分

6. $n \le 1000000$ => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法

   hash、双指针扫描、并查集，kmp、AC 自动机，

   常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa

7. $n \le 10000000$ => $O(n)$，

   双指针扫描、kmp、AC 自动机、线性筛素数

8. $n \le 10^9$ => $O(\sqrt n)$，

   判断质数

9. $n \le 10^{18}$ => $O(logn)$，

   最大公约数，快速幂

10. $n \le 10^{1000}$ => $O((logn)^2)$，

    高精度加减乘除

11. $n \le 10^{100000}$ => $O(logn \times loglogn)$，

    高精度加减、FFT/NTT

算法时间复杂度分析实例：

一般来说，k重循环，算法时间复杂度就是$n^k$

spfa算法， 匈牙利算法， 最大流算法时间复杂度理论值很大，但是实际运行速度很快

动态规划问题的计算量=状态数量*状态转移的计算量

空间复杂度分析

64M

1 Byte = 8 bit

1 KB= 1024 Byte

1 MB=1024*1024 Byte

1 GB=1024 * 1024 * 1024 Byte

int  4 Byte

char 1 Byte

double, long long   6Byte

bool 1 Byte

C++: 为什么bool类型是1 Byte(8 bits)长？

为什么bool类型所需存储空间不是 1 bit, 1 bit就可以覆盖bool类型的值域范围 。

Cpp的数据类型必须就可以通过地址得到的（addressable）。

我们无法通过一位创建一个指针，但是我们可以通过一个自己创建一个指针。

所以， 在Cpp中，Bool类型的大小是一个字节。

64MB=2^26Byte

2^26Byte /4 =2^24 int

=1.6*10^7 int

注意

递归也是需要空间的，递归调用了系统栈，快速排序使用了递归，所以空间复杂度是O(logn)