算法分析

一、什么是算法分析？

?程序和算法的區(qū)別。算法是對問題解決的分步描述，程序則是采用某種編程語言實現(xiàn)的算法，同一個算法通過不同的程序員采用不同的編程語言，能產(chǎn)生很多程序。

?我們來看一段程序，完成從1到n的累加，輸出總和。設(shè)置累計變量=0，從1到n循環(huán)，逐次累加到累計變量，返回累計變量。

?? 再看第二段程序，是否感覺怪怪的？但實際上本程序功能與前面

那段相同，這段程序失敗之處在于：變量命名，有無用的垃圾代碼。比較程序的“好壞”，可從多因素入手，如代碼風(fēng)格、可讀性等等。

?我們主要感興趣的是算法本身特性，算法分析主要就是從計算資源消耗的角度來評判和比較算法，更高效利用計算資源，或者更少占用資源的算法，就是好算法。從這個角度，前述兩段程序?qū)嶋H上是基本相同的，它們都采用了一樣的算法來解決累計求和問題。

?

二、計算資源指標(biāo)

?何為計算資源？一種是算法解決問題過程中需要的存儲空間或內(nèi)存，但存儲空間受到問題自身數(shù)據(jù)規(guī)模的變化影響，要區(qū)分哪些存儲空間是問題本身描述所需，哪些是算法占用不容易。

?另一種是算法的執(zhí)行時間。我們可以對程序進行實際運行測試，獲得真實的運行時間。Python有一個time模塊，可以獲取計算機系統(tǒng)當(dāng)前時間，在算法開始前和結(jié)束后分別記錄系統(tǒng)時間，即可得到運行時間。

三、運行時間檢測

?累計求和程序的運行時間檢測，增加了總運行時間，函數(shù)返回一個元組tuple：包括累計和，以及運行時間（秒），連續(xù)運行5次看看。

? ? 如果累加到100000看起來運行時間增加到10000的10倍

? ? 進一步累加到1000000運行時間又是100000的10倍了

四、第二種無迭代的累計算法

?利用求和公式的無迭代算法，采用同樣的方法檢測運行時間，需要關(guān)注的兩點，這種算法的運行時間比前種都短很多，運行時間與累計對象n的大小沒有關(guān)系（前種算法是倍數(shù)增長關(guān)系），新算法運行時間幾乎與需要累計的數(shù)目無關(guān)。

五、運行時間檢測的分析

?觀察一下第一種迭代算法，包含了一個循環(huán)，可能會執(zhí)行更多語句。這個循環(huán)運行次數(shù)跟累加值n有關(guān)系，n增加，循環(huán)次數(shù)也增加。但關(guān)于運行時間的實際檢測有點問題。同一個算法，采用不同的編程語言編寫，放在不同的機器上運行，得到的運行時間會不一樣，有時候會大不一樣，比如把非迭代算法放在老舊機器上跑，甚至可能慢過新機器上的迭代算法，所以我們需要更好的方法來衡量算法的運行時間，這個指標(biāo)與具體的機器、程序、運行時段，與編譯器都無關(guān)。

公眾號推薦：數(shù)據(jù)思踐

數(shù)據(jù)思踐公眾號記錄和分享數(shù)據(jù)人思考和踐行的內(nèi)容與故事。

《數(shù)據(jù)科學(xué)與人工智能》公眾號推薦朋友們學(xué)習(xí)和使用Python語言，需要加入Python語言群的，請掃碼加我個人微信，備注【姓名-Python群】，我誠邀你入群，大家學(xué)習(xí)和分享。

? ? 關(guān)于Python語言，有任何問題或者想法，請留言或者加群討論。