算法效率分析（原創文章）

天洑軟件

2019年11月5日 14:51

算法是一系列解決問題的明確指令，對于一定符合規范的輸入，能夠在有限時間內獲得要求的輸出。從實際問題的提出到設計合適的算法再到正確性的分析以及算法效率的分析，最后為算法編寫代碼，一步步得到問題的解決方案。

算法效率分析（原創文章）的圖1

圖1.算法的概念

算法效率分析（原創文章）的圖2

圖2.算法設計分析過程

對算法效率的分析，需要指出有兩種算法效率：時間效率和空間效率，分指算法運行速度和需要的額外空間。由于技術革新，對于大多數問題，速度上效率的提高遠大于空間上的提高。在研究算法效率上提出一般性框架。

定義1：如果存在正常數c和算法效率分析（原創文章）的圖3 使得當算法效率分析（原創文章）的圖4 時算法效率分析（原創文章）的圖5 ，則記為算法效率分析（原創文章）的圖6 。

定義2：如果存在正常數c和算法效率分析（原創文章）的圖7 使得當算法效率分析（原創文章）的圖8 時算法效率分析（原創文章）的圖9 ，則記為算法效率分析（原創文章）的圖10 。

定義3：算法效率分析（原創文章）的圖11 當且僅當算法效率分析（原創文章）的圖12 且算法效率分析（原創文章）的圖13 。

定義4：如果算法效率分析（原創文章）的圖14 且算法效率分析（原創文章）的圖15 ，則算法效率分析（原創文章）的圖16 。

定義的目的實在函數之間建立相對的級別。可直觀的理解為算法效率分析（原創文章）的圖17 增長率小于等于算法效率分析（原創文章）的圖18 ，算法效率分析（原創文章）的圖19 增長率大于等于算法效率分析（原創文章）的圖20 ，算法效率分析（原創文章）的圖21 增長率等于算法效率分析（原創文章）的圖22 ，算法效率分析（原創文章）的圖23 增長率小于算法效率分析（原創文章）的圖24 。

法則1：如果算法效率分析（原創文章）的圖25 且算法效率分析（原創文章）的圖26 ，那么

（a）算法效率分析（原創文章）的圖27

（b）算法效率分析（原創文章）的圖28

法則2：如果算法效率分析（原創文章）的圖29 是k次多項式，則算法效率分析（原創文章）的圖30

法則3：對任意常數k，算法效率分析（原創文章）的圖31

下面以最大子序列和問題的四種解決方法來分析算法的效率問題。

最大子序列和：給定整數算法效率分析（原創文章）的圖32 （可能含負數），求算法效率分析（原創文章）的圖33 最大值（若所有整數為負，則最大子序列和為0）

算法	1	2	3	4
時間
輸入大小/m	N=10	0.00103	0.00045	0.00066	0.00034
N=100	0.47015	0.01112	0.00486	0.00063
N=1000	448.77	1.1233	0.05843	0.00333
N=10000	NA	111.13	0.68631	0.03042
N=100000	NA	NA	8.0113	0.29832

算法效率分析（原創文章）的圖38

算法效率分析（原創文章）的圖39

方法一、窮舉嘗試所有可能，含有3重for循環。第一循環大小為N，第二循環大小為算法效率分析（原創文章）的圖40 ，第三循環大小為算法效率分析（原創文章）的圖41 。考慮最差時間效率，第二循環第三循環大小均為N。總數為算法效率分析（原創文章）的圖42 。可精確分析，第三循環時間算法效率分析（原創文章）的圖43