时间复杂度 笔记
Ο表示上界，Θ表示确界，Ω表示下界
在OI中O通常表示确界。
估计时间复杂度
-
10^{18} 数论，矩阵快速幂
-
10^7 O(n)
-
10^6 O(n log n) ，小数据结构
-
10^5 O(n log n) O(n \sqrt n ) 主要数据结构
-
10^3 O(n^2) DP
-
10^2 O(n^3) DP 网络流
主定理
定理内容
定理应用
例： T(n) = 8T(n/3) + n^2logn
代入定理，其中 a = 8 , b=3 , f(n) = n^2logn
因为 n^2logn > n^{log_38} ，属于情况(3).
所以 O(T(n)) = O(f(n)) = n^2logn
时间复杂度优化
-
预处理（优化询问的时间复杂度）
-
调和级数（线性筛，埃氏筛）
总结
- 可以先根据数据范围估算时间复杂度来大致判断算法
- 主定理经常被用于计算分治算法的时间复杂度