算法基础 第七章 时空复杂度分析

y总总结

1. $n \le 30$, 指数级别, dfs+剪枝, 状态压缩dp
2. $n \le 100$ => $O(n^3)$, floyd, dp
3. $n \le 1000$ => $O(n^2)$, $0(n^2logn)$, dp, 二分
4. $n \le 10000$ => $O(n * \sqrt n)$, 块状链表
5. $n \le 10^5$ => $O(nlogn)$ =>
   各种sort, 线段树, 树状数组, set/map, heap, dijkstra+heāp, spfa, 求凸包, 求半平面交, 二分
6. $n \le 10^6$ => $O(n)$, 以及常数较小的 $0(nlogn)$算法 =>hash、双指针扫描, kmp, AC自动机, 常数比较小的$0(nlogn)$ 的做法:sort, 树状数组, heap, dijkstra, spfa
7. $n \le 10^7$ => $O(n)$, 双指针扫描, kmp, AC自动机, 线性筛素数
8. $n \le 10^9$ => $O(\sqrt n)$, 判断质数
9. $n \le 10^{18}$ => $O(1ogn)$, 最大公约数

其他技巧

C++

$\quad$ cost_time: $1s - 2s $
$\quad$ cost_cal: $O(10^7 - 10^8 per_s)$

时间复杂度由来

1. i层循环 $O(n^i)$
2. 递归(主定理)
3. 快排(平均)，归并$O(nlogn)$$\quad$参考十大排序
4. 并查集$O(nlognlogn)$$\quad$参考一$\quad$参考二$\quad$参考三
   1. 路径压缩 $O(nlogn)$
   2. 按秩排序
5. dp |