算法与数据结构

算法

好的算法

正确性

循环不变式

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

易读性

健壮性

高效性

低存储性

分析算法

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

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

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

时间复杂度

可以粗略地分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个: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)

设计算法

空间复杂度