绪论

理论基础

ADT

抽象数据模型：数据对象，对象关系，操作方法

数据的逻辑结构 + 抽象算法

• 算法设计要求

1. 正确性
2. 可读性
3. 健壮性
4. 高效性

渐进时间复杂度

T(n) = O f(n)

级数求和 —> 算法时间复杂度分析

概念：存在一个辅助函数 f(n)，当 n 无穷大时，T(n) / f(n) 的极限值为不等于 0 的常数，同数量级函数

• 最坏时间复杂度
• 平均时间复杂度
• 最好时间复杂度

时间复杂度算法

1. 加法 O(max(f(n)，g(n)))
2. 乘法 O(f(n) x g(n))

时间复杂度数量级递增顺序

常数阶 —> 对数阶 —> 线性阶 —> 线性对数阶 —> 平方阶 —> 立方阶 —> K次方阶 —> 指数阶

渐进空间复杂度

S(n) = O(f(n))