算法与数据结构
算法
- 有穷性
- 确定性
- 可行性
- 输入输出
好的算法
正确性
循环不变式
在排序算法中，每一轮循环做的操作就是一轮不变式，通过证明三条性质来确定算法是正确的
- 初始化：第一次迭代前，为真
- 保持：如果迭代之前为真，迭代之后也为真
- 终止时，停止归纳
易读性
健壮性
高效性
低存储性
分析算法
对于复杂度的分析，一般分析的都是在最坏情况下的复杂度
需要分析复杂度的原因在于不同的算法对于不同量级的数据，所需要的时间与空间会相差很多
复杂度的衡量单位是增长量级，也就是时间或空间的增长率
时间复杂度
- 常数：n
- 多项式
- n^2 n^3
- 指数
- 2^n n!
- 对数
- logn