首页 > 代码库 > 普林斯顿公开课 算法1-1:算法分析
普林斯顿公开课 算法1-1:算法分析
为什么要分析算法
分析算法能够预測算法的性能,比較算法之间的优劣,保证算法的正确性,理解算法的理论基础。
成功算法的样例
离散傅立叶变换,假设使用暴力方法,那么算法的复杂度是是N^2,假设使用FFT高速傅立叶变换能够实现O(N logN)复杂度
N-body模拟:使用Barnes-hut算法能够将复杂度减少到N logN
顺便发一张N-body模拟的炫图
Barnes-Hut算法示意图
算法分析的步骤
观察问题的特征和想到得到的结果
依据观察结果提出如果
使用如果来预測可能发生的情况
检測预測结果与观察到的特征是否一致
反复验证,直到如果和实际观察到的特征相符
算法分析的原则
实验必须能够反复
如果必须能够否定
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。