算法与数据结构
算法
- 有穷性
- 确定性
- 可行性
- 输入输出
好的算法
正确性
循环不变式
在排序算法中，每一轮循环做的操作就是一轮不变式，通过证明三条性质来确定算法是正确的
- 初始化：第一次迭代前，为真
- 保持：如果迭代之前为真，迭代之后也为真
- 终止时，停止归纳
易读性
健壮性
高效性
低存储性
分析算法
对于复杂度的分析，一般分析的都是在最坏情况下的复杂度
需要分析复杂度的原因在于不同的算法对于不同量级的数据，所需要的时间与空间会相差很多
复杂度的衡量单位是增长量级，也就是时间或空间的增长率
时间复杂度
- 常数：1
- 线性：n
- 多项式：n^2 n^3
- 指数：2^n n!
- 对数：logn
可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)
时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题
分析方法：
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 当代码的复杂度由多个数据的规模来决定，表示为$O(n_1+_2+...+n_n)$
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
最好时间复杂度：最理想的情况下，执行这段代码的时间复杂度
最坏时间复杂度：最糟糕的情况下，执行这段代码的时间复杂度
平均时间复杂度：了解输入的概率分布是关键，对算法在所有可能输入上的性能进行平均分析
均摊时间复杂度：一些操作可能会花费较长时间，但它们并不经常发生，因此这些操作的成本可以分摊到其他较为常见的操作上