数据结构 | （一）算法及算法分析

1、什么是算法？

算法是对特定问题的求解步骤，具有有穷性、确定性、可行性、输入、输出5个重要特性。

2、什么是好的算法？

正确、可读性强、健壮、高效、低存储需求。

3、如何衡量算法的好坏？

（1）时间复杂度

在分析算法的running time时，通常我们并不关心具体的大小，我们更关心running time 的阶数，当input size很大的时候，这个函数的表现如何。

（2）空间复杂度

算法原地工作：程序运行所需的辅助空间相对输入的数据量来说是常数。

4、算法分析的两个主要任务

正确性（不变性 X 单调性） +  复杂度

5、时间复杂度分析举例

分析BFS宽度优先搜索算法的时间复杂度

BFS算法

算法的时间复杂度与输入的数据结构有关：

当输入是邻接表时, 时间复杂度是 O（n + m）（其中n是节点数，m是边数） ；

当输入是邻接矩阵时, 算法时间复杂度为 O（ ) 。

邻接矩阵的时间复杂度分析如下：

BFS时间复杂度分析