什么是算法分析

當(dāng)我們說算法分析的時候我們在說什么？（狹義的技術(shù)層面的定義）：
算法分析指的是：對算法在運行時間和存儲空間這兩種資源的利用效率進(jìn)行研究。
即時間效率和空間效率。

時間效率指算法運行有多快；
空間效率指算法運行時需要多少額外的存儲空間。
（時間效率也叫時間復(fù)雜度；空間效率也叫空間復(fù)雜度。）

在計算機(jī)時代早期，時間和空間這兩種資源都是及其昂貴的。但經(jīng)過半個多世紀(jì)的發(fā)展，計算機(jī)的速度和存儲容量都已經(jīng)提升了好幾個數(shù)量級。
現(xiàn)在空間效率已經(jīng)不是我們關(guān)注的重點了，但時間效率的重要性并沒有減弱到這種可以忽略的程度。

所以，當(dāng)我們分析一個算法的的時候，我們只關(guān)注它的時間效率。

算法分析通用思路：

當(dāng)我們遇到一個算法時，我們可以用這樣一個通用的思路去分析它：

1. 輸入規(guī)模

首先第一步考慮這個算法的輸入規(guī)模是什么？即輸入?yún)?shù)，再換句話說也就是待解決的問題有多大？
從這里入手是因為一個顯而易見的規(guī)律就是，不管使用什么算法，輸入規(guī)模越大，運行效率肯定會更長。
輸入規(guī)模的確定要根據(jù)具體要解決的實際問題的細(xì)節(jié)來決定，相同的問題不同的細(xì)節(jié)，輸入規(guī)模是不一樣的。比如：一個拼寫檢查的算法，
如果算法關(guān)注的是單獨的字符檢查，那么字符的數(shù)量就是輸入規(guī)模的大小；
如果算法關(guān)注的是詞組搭配的檢查，那么這個輸入規(guī)模就要比單獨的字符檢查的輸入規(guī)模要小，這里輸入規(guī)模就是詞的數(shù)量了。

2. 運行時間的度量單位

接下來第二步考慮這個算法的運行時間，即這個算法運行地快慢。
我們可以簡單地用計時的方法，即某個算法運行了多少毫秒。
但這個方式有一個缺陷就是在不同計算機(jī)上，相同算法的運行時間是不一樣，因為有的電腦快有的電腦慢。
所以有沒有一種度量方法可以排除這些無關(guān)因素？
答案是肯定的，我們可以關(guān)注算法執(zhí)行了多少步，即操作的運行次數(shù)。而且為了簡化問題我們只需關(guān)注最重要的操作步驟，即所謂的基本操作，因為基本操作已經(jīng)足夠可以決定這個算法的品質(zhì)。
比如一個算法通常是最內(nèi)層的循環(huán)中是最費時的操作，那我們就只需要把它循環(huán)了多少次作為基本操作進(jìn)行研究。

3. 增長次數(shù)

這里需要延伸的一點是在大規(guī)模的輸入情況下考慮執(zhí)行次數(shù)的增長次數(shù)。因為針對小規(guī)模的輸入，在運行時間的差別上不太明顯。比如只對100個數(shù)字進(jìn)行排序，不管你用什么排序算法，時間效率都差不多。只有在輸入規(guī)模變大的時候，算法的差異才變得既明顯又重要了起來。
簡單來說，
如果一個算法在輸入規(guī)模變大時，但運行時間平緩增長，那么我們就可以說它就是一個效率高的算法；
而如果一個算法在輸入規(guī)模變大時，它的運行時間成指數(shù)級增長，那就可以說這個算法的效率很差。
總而言之就是，對基本操作的大規(guī)模輸入情況下的變化的研究才更具有深遠(yuǎn)意義。

4. 算法的最優(yōu)、最差和平均效率

當(dāng)我們了解了輸入規(guī)模對算法時間效率的會產(chǎn)生影響，但算法的執(zhí)行效率卻不僅僅只受輸入規(guī)模的影響，某些情況下，算法的執(zhí)行效率更取決于輸入?yún)?shù)的細(xì)節(jié)。
比如：一個簡單的順序查找的算法，在數(shù)組里查找數(shù)字 9：
在數(shù)組 l1 = [1, 2, 3, 4, 5, 6, 7, 8, 9] 里查找數(shù)字 9 和在相同的輸入規(guī)模的另一個數(shù)組 l2 = [9, 1, 2, 3, 4, 5, 6, 7, 8]里查找數(shù)字 9，在數(shù)組 l2 的執(zhí)行效率肯定更高。
上面小例子中的兩個數(shù)組就體現(xiàn)了兩個極端：輸入最優(yōu)情況和輸入最壞情況。
相對應(yīng)的，
在輸入最優(yōu)情況下的算法就叫最優(yōu)效率；
在輸入最壞情況下的算法就叫最差效率；
在這里有兩個經(jīng)驗性的規(guī)則：

1. 最優(yōu)效率的分析遠(yuǎn)遠(yuǎn)不如最差效率分析重要（因為最差效率可以確定算法運行時間的上界）；
2. 如果一個算法的最優(yōu)效率都不能滿足我們的要求，那么我們就可以立即拋棄它。

在現(xiàn)實情況下，輸入是“隨機(jī)”的，既不會是最優(yōu)輸入也不會是最壞輸入。所以這里又要引出一個概念，即：平均效率。
首先指出，我們絕不能用“最優(yōu)效率”和“最差效率”的平均數(shù)求得平均效率，即便有時間這個平均數(shù)和真正的平均效率巧合地一致。
正確的步驟是：我們要對輸入規(guī)模 n 做一些假設(shè)。
對于上面的順序查找算法的例子，標(biāo)準(zhǔn)的假設(shè)有兩個：

1. 輸入里包含目標(biāo)數(shù)字，那么算法會成功查找到目標(biāo)數(shù)字，此時，成功查找概率是 p(0 <= p <= 1)；
2. 對于任意數(shù)字 i，匹配發(fā)生在列表的第 i 個位置的概率是相同的。

基于這兩個假設(shè)求平均效率可得：

1. 成功查找到目標(biāo)的情況下，對于任意 i，第一次匹配發(fā)生在第 i 個位置的概率都是 p/n，此時，算法所做的比較次數(shù)是 i；
2. 輸入數(shù)組里不包含目標(biāo)數(shù)字，那么算法不成功查找，比較次數(shù)是 n，在這種情況下，可能性是 (1-p)。

由此，平均效率 C(n) = p(n+1) / 2 + n(1-p)

C(n) = [1 * p/n + 2 * p/n + ... + i * p/n + ... + n * p/n] + n*(1-p)
=  p/n[1 + 2 + ... + i + ... + n] + n(1-p)
= p/n * n(n+1)/2 + n(1-p)
= p(n+1) / 2 + n(1-p)               

由此可知，

1. 如果 p = 1，也就是說成功率是 100%，查找一定能成功，代入公式可得 (n+1)/2，即大約要查找數(shù)組中一半的元素；
2. 如果 p = 0，也就是說成功率是 0%，查找必定失敗，代入公式可得 n，即算法會對所有元素全部查找一遍。

從這個例子可以發(fā)現(xiàn)，平均效率的研究要比最差效率和最優(yōu)效率的研究困難很多：
我們要將輸入規(guī)模 n 劃分為幾種類型，對于同類型的輸入，使得算法的執(zhí)行次數(shù)是相同的。

結(jié)束：

算法是計算機(jī)科學(xué)的基礎(chǔ)，以后會繼續(xù)更新算法相關(guān)的隨筆，對算法感興趣的朋友歡迎關(guān)注本博客，也歡迎大家留言討論。
我們正處于大數(shù)據(jù)時代，對數(shù)據(jù)處理感興趣的朋友歡迎查看另一個系列隨筆：
利用Python進(jìn)行數(shù)據(jù)分析 基礎(chǔ)系列隨筆匯總

參考資料：

Introduction to The Design and Analysis of Algorithms, Third Edition by Anany Leitin

分享一張學(xué)校圖書館的照片