- 计算平均复杂度很困难, 故一般只考虑最好 / 最坏情况, 然后取平均
- 空间复杂度的组分:
- 固定成分: 指令, 简单变量, 常量等
- 可变成分: 动态分配的空间, 递归的栈空间等(传参在栈上占用空间)
- 时间复杂度的组分:
- 编译时间: 与实例特征无关
- 操作步数: 与实例特征有关
- 大O表示法描述的是算法复杂度的上界
- 定义:
- 即描述复杂度的阶
, if positive constant and exist such that for all ,
- 表示法描述的则是下界
if positive constant and exist such that for all ,
- 表示法描述精确的阶
if positive constants and and a exist such that for all ,
