首页 > 代码库 > 普林斯顿公开课 算法1-1:算法分析

普林斯顿公开课 算法1-1:算法分析

为什么要分析算法


分析算法能够预測算法的性能,比較算法之间的优劣,保证算法的正确性,理解算法的理论基础。


成功算法的样例


离散傅立叶变换,假设使用暴力方法,那么算法的复杂度是是N^2,假设使用FFT高速傅立叶变换能够实现O(N logN)复杂度

N-body模拟:使用Barnes-hut算法能够将复杂度减少到N logN


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



Barnes-Hut算法示意图



算法分析的步骤


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

  2. 依据观察结果提出如果

  3. 使用如果来预測可能发生的情况

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

  5. 反复验证,直到如果和实际观察到的特征相符


算法分析的原则


  • 实验必须能够反复

  • 如果必须能够否定