为什么要分析算法

分析算法可以预测算法的性能，比较算法之间的优劣，保证算法的正确性，理解算法的理论基础。

成功算法的例子

离散傅立叶变换，如果使用暴力方法，那么算法的复杂度是是N^2，如果使用FFT快速傅立叶变换可以实现O(N logN)复杂度

N-body模拟：使用Barnes-hut算法可以将复杂度降低到N logN

顺便发一张N-body模拟的炫图

Barnes-Hut算法示意图

算法分析的步骤

1. 观察问题的特征和想到得到的结果

2. 根据观察结果提出假设

3. 使用假设来预测可能发生的情况

4. 检测预测结果与观察到的特征是否一致

5. 重复验证，直到假设和实际观察到的特征相符

算法分析的原则

• 实验必须可以重复

• 假设必须可以否定