时空复杂度分析

[龚茂涵1 (龚茂涵)]

时间复杂度 笔记

Ο表示上界，Θ表示确界，Ω表示下界

在OI中O通常表示确界。

估计时间复杂度

1. 10^{18} 数论，矩阵快速幂

2. 10^7 O(n)

3. 10^6 O(n log n) ，小数据结构

4. 10^5 O(n log n) O(n \sqrt n ) 主要数据结构

5. 10^3 O(n^2) DP

6. 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$

时间复杂度优化

1. 预处理（优化询问的时间复杂度）

2. 调和级数（线性筛，埃氏筛）