时间空间复杂度分析

c++一般1s能够计算10^7~108

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 10^7～108为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

• n ≤ 30 , 指数级别, dfs+剪枝，状态压缩dp(n皇后，八数码，蒙德里安的梦想)
• n ≤ 100 => O(n^3)，floyd，dp，高斯消元
• n ≤ 1000 => O(n ^ 2)，O(n ^ 2 * logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
• n ≤ 10000 => O(n ? √n) 块状链表、分块、莫队
• n ≤ 100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
• n ≤ 1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
• n ≤ 10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
• n ≤ 10^9 => O(√n)，判断质数
• n ≤ 10^18 => O(logn)，最大公约数，快速幂，数位DP

代码时间复杂度分析

• 看循环
• 递归，比如快排，一般logn层递归，每层需要O(n)的时间复杂度
  • 并查集
    • 路径压缩
    • 按秩合并
    • 两个优化可以使得并查集达到O(log(logn)),单纯路径压缩可以达到O(nlogn)
• 排列数字，O(n! * n),总共有n！中结果，每次需要复制结果需要O(n)的时间
• dp的问题计算量 = 状态数量 * 状态转移的计算量，(没有上司的舞会，每个点只会遍历一次，所以时间复杂度为O(n))

空间复杂度

一个 int 4 byte，char 1 byte，double / long long 8 byte, bool 1 byte，题目一般给64MB = 2 ^ 26 byte, (2 ^ 26) / 4 = 16 * 1024 * 1024
1 byte = 8 bit
1 KB = 1024 byte
1 MB = 1024 * 1024 byte