一.怎么評估一個算法的優(yōu)劣
算法表達(dá)式.png
- 可以把求時間轉(zhuǎn)化為求這個算法需要運行的次數(shù),這樣就可以避免硬件的干擾
二.算法復(fù)雜度
- 大O記號(好讀書不求甚解_陶淵明:不要拘泥于細(xì)節(jié),你的大方向一定要對)
- 常數(shù)系可忽略
- 低次項可忽略
- log 對數(shù)復(fù)雜度,無限接近于O(1),高效
- 線性復(fù)雜度,可預(yù)測
- 多項式復(fù)雜度,有效算法
- 指數(shù)復(fù)雜度,不可忍受的算法
指數(shù)代表了運算量很大的算法,耗時
如果有算法可以歸結(jié)為多項式,那么將比指數(shù)更優(yōu)(似懂非懂)
三.算法分析
- 正確性->1.不變性(可推理) 2.單調(diào)性(推理是有限的)
- 復(fù)雜度
級數(shù)
級數(shù).png
四.算法優(yōu)化
- 分而治之:一份平凡,一份規(guī)模縮減
- 減而治之:平分
