算法与数据结构

算法

循环不变式

在排序算法中，每一轮循环做的操作就是一轮不变式，通过证明三条性质来确定算法是正确的

对于复杂度的分析，一般分析的都是在最坏情况下的复杂度

需要分析复杂度的原因在于不同的算法对于不同量级的数据，所需要的时间与空间会相差很多

复杂度的衡量单位是增长量级，也就是时间或空间的增长率

可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n) 和 O(n!)

时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题

分析方法：

最好时间复杂度：最理想的情况下，执行这段代码的时间复杂度

最坏时间复杂度：最糟糕的情况下，执行这段代码的时间复杂度

平均时间复杂度：了解输入的概率分布是关键，对算法在所有可能输入上的性能进行平均分析

均摊时间复杂度：一些操作可能会花费较长时间，但它们并不经常发生，因此这些操作的成本可以分摊到其他较为常见的操作上

对于使用分治策略的算法，可以使用一棵树描述其时间复杂度

stateDiagram-v2  n --> 1(2/n)  n --> 2(2/n)  1(2/n) --> 1(4/n)  1(2/n) --> 2(4/n)  2(2/n) --> 3(4/n)  2(2/n) --> 4(4/n)

只需要知道这棵树的高度 h，用高度 h 乘以每一层的时间消耗 n，就可以得到总的时间复杂度 O(n∗h)