第一章基础知识

第一节时间复杂度

时间复杂度的比较

加减保留高阶

O (1) < O (l o g_{2} ​ n) < O (n) < O (n l o g_{2} ​ n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!) < O (n^{n})

时间复杂度的加法、乘法规则

T (n) = T_{1} ​ (n) + T_{2} ​ (n) = O (f (n)) + O (g (n)) = O (m a x (f (n), g (n))) $ $ ​ $ $ T (n) = T_{1} ​ (n) \times T_{2} (n) = O (f (n)) \times O (g (n)) = O (f (n) \times g (n))

TIP

忽视常数项

关注随循环变化的变量（如数组）
递归调用

数据结构

逻辑结构
- 线性结构
  - 一般线性表
  - 栈和队列
  - 串
  - 数组
- 非线性结构
  - 集合
  - 树
  - 图
存储结构
- 顺序存储
- 链式存储
- 索引存储
- 散列存储
数据的运算