时间复杂度分析

常规
1 
# 时间复杂度 笔记
Ο表示上界，Θ表示确界，Ω表示下界<br>
在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 网络流

## 主定理

### 定理内容
![Alt text](image.png)

### 定理应用
例： $T(n) = 8T(n/3) + n^2logn$<br>
代入定理，其中$a = 8$,$b=3$,$f(n) = n^2logn$<br>

因为$n^2logn > n^{log_38}$，属于情况(3).
所以$O(T(n)) =  O(f(n)) = n^2logn$

## 时间复杂度优化
1. 预处理（优化询问的时间复杂度）
2. 调和级数（线性筛，埃氏筛）
6 个赞
3

可怜的无回复帖

2 个赞
5

666

2 个赞
6

水贴举了（bushi

2 个赞
7

zc

2 个赞