一.怎么评估一个算法的优劣
算法表达式.png
- 可以把求时间转化为求这个算法需要运行的次数,这样就可以避免硬件的干扰
二.算法复杂度
- 大O记号(好读书不求甚解_陶渊明:不要拘泥于细节,你的大方向一定要对)
- 常数系可忽略
- 低次项可忽略
- log 对数复杂度,无限接近于O(1),高效
- 线性复杂度,可预测
- 多项式复杂度,有效算法
- 指数复杂度,不可忍受的算法
指数代表了运算量很大的算法,耗时
如果有算法可以归结为多项式,那么将比指数更优(似懂非懂)
三.算法分析
- 正确性->1.不变性(可推理) 2.单调性(推理是有限的)
- 复杂度
级数
级数.png
四.算法优化
- 分而治之:一份平凡,一份规模缩减
- 减而治之:平分
