一、前言
在進一步學習數(shù)據結構與算法前，我們應該先掌握算法分析的一般方法。算法分析主要包括對算法的時空復雜度進行分析，但有些時候我們更關心算法的實際運行性能如何，此外，算法可視化是一項幫助我們理解算法實際執(zhí)行過程的實用技能，在分析一些比較抽象的算法時，這項技能尤為實用。在在本篇博文中，我們首先會介紹如何通過設計實驗來量化算法的實際運行性能，然后會介紹算法的時間復雜度的分析方法，我們還會介紹能夠非常便捷的預測算法性能的倍率實驗。當然，在文章的末尾，我們會一起來做幾道一線互聯(lián)網的相關面試/筆試題來鞏固所學，達到學以致用。
二、算法分析的一般方法
1. 量化算法的實際運行性能
在介紹算法的時空復雜度分析方法前，我們先來介紹以下如何來量化算法的實際運行性能，這里我們選取的衡量算法性能的量化指標是它的實際運行時間。通常這個運行時間與算法要解決的問題規(guī)模相關，比如排序100萬個數(shù)的時間通常要比排序10萬個數(shù)的時間要長。所以我們在觀察算法的運行時間時，還要同時考慮它所解決問題的規(guī)模，觀察隨著問題規(guī)模的增長，算法的實際運行時間時怎樣增長的。代碼如下：
以上代碼用到的StdIn和StdOut這兩個類都在這里：
我們可以看到，以上代碼的功能是統(tǒng)計標準一個int[]數(shù)組中的所有和為0的三整數(shù)元組的數(shù)量。采用的算法十分直接，就是從頭開始遍歷數(shù)組，每次取三個數(shù)，若和為0，則計數(shù)加一，最后返回的計數(shù)值即為和為0的三元組的數(shù)量。這里我們采取含有整數(shù)數(shù)量分別為1000、2000、4000的3個文件（這些文件可以在上面的項目地址中找到），來對以上算法進行測試，觀察它的運行時間隨著問題規(guī)模的增長是怎樣變化的。
測量一個過程的運行時間的一個直接的方法就是，在這個過程運行前后各獲取一次當前時間，兩者的差值即為這個過程的運行時間。當我們的過程本身需要的執(zhí)行時間很短時間，這個測量方法可能會存在一些誤差，但是我們可以通過執(zhí)行多次這個過程再取平均數(shù)來減小以至可以忽略這個誤差。下面我們來實際測量一下以上算法的運行時間，相關代碼如下：
我們分別以1000、2000、4000個整數(shù)作為輸入，得到的運行結果如下:
我們從以上結果大概可你看到，當問題的規(guī)模變?yōu)樵瓉淼?倍時，實際運行時間大約變?yōu)樵瓉淼?倍。根據這個現(xiàn)象我們可以做出一個猜想：程序的運行時間關于問題規(guī)模N的函數(shù)關系式為T(N) = k*(n^3)。
在這個關系式中，當n變?yōu)樵瓉淼?倍時，T(N)會變?yōu)樵瓉淼?倍。那么ThreeSum算法的運行時間與問題規(guī)模是否滿足以上的函數(shù)關系呢？在介紹算法時間復雜度的相關內容后，我們會回過頭來再看這個問題。
2. 算法的時間復雜度分析
（1）基本概念
關于算法的時間復雜度，這里我們先簡單介紹下相關的三種符號記法：
我們在平常的算法分析中最常用到的是Big O notation。下面我們將介紹分析算法的時間復雜度的具體方法。
（2）時間復雜度的分析方法
這部分我們將以上面的ThreeSum程序為例，來介紹一下算法時間復雜度的分析方法。為了方便閱讀，這里再貼一下上面的程序：
在介紹時間復雜度分析方法前，我們首先來明確下算法的運行時間究竟取決于什么。直觀地想，一個算法的運行時間也就是執(zhí)行所有程序語句的耗時總和。然而在實際的分析中，我們并不需要考慮所有程序語句的運行時間，我們應該做的是集中注意力于最耗時的部分，也就是執(zhí)行頻率最高而且最耗時的操作。也就是說，在對一個程序的時間復雜度進行分析前，我們要先確定這個程序中哪些語句的執(zhí)行占用的它的大部分執(zhí)行時間，而那些盡管耗時大但只執(zhí)行常數(shù)次（和問題規(guī)模無關）的操作我們可以忽略。我們選出一個最耗時的操作，通過計算這些操作的執(zhí)行次數(shù)來估計算法的時間復雜度，下面我們來具體介紹這一過程。
首先我們看到以上代碼的第1行和第2行的語句只會執(zhí)行一次，因此我們可以忽略它們。然后我們看到第4行到第12行是一個三層循環(huán)，最內存的循環(huán)體包含了一個if語句。也就是說，這個if語句是以上代碼中耗時最多的語句，我們接下來只需要計算if語句的執(zhí)行次數(shù)即可估計出這個算法的時間復雜度。以上算法中，我們的問題規(guī)模為N（輸入數(shù)組包含的元素數(shù)目），我們也可以看到，if語句的執(zhí)行次數(shù)與N是相關的。我們不難得出，if語句會執(zhí)行N * (N-1) * (N-2)/6次，因此這個算法的時間復雜度為O(n^3)。這也印證了我們之前猜想的運行時間與問題規(guī)模的函數(shù)關系（T(n) =k*n^3）。由此我們也可以知道，算法的時間復雜度刻畫的是隨著問題規(guī)模的增長，算法的運行時間的增長速度是怎樣的。在平常的使用中，Big O notation通常都不是嚴格表示最壞情況下算法的運行時間上限，而是用來表示通常情況下算法的漸進性能的上限，在使用Big O notation描述算法最壞情況下運行時間的上限時，我們通常加上限定詞“最壞情況“。
通過以上分析，我們知道分析算法的時間復雜度只需要兩步,比把大象放進冰箱還少一步：
在以上的例子中我們可以看到，不論我們輸入的整型數(shù)組是怎樣的，if語句的執(zhí)行次數(shù)是不變的，也就是說上面算法的運行時間與輸入無關。而有些算法的實際運行時間高度依賴于我們給定的輸入，關于這一問題下面我們進行介紹。
3. 算法的期望運行時間
算法的期望運行時間我們可以理解為，在通常情況下，算法的運行時間是多少。在很多時候，我們更關心算法的期望運行時間而不是算法在最壞情況下運行時間的上限，因為最壞情況和最好情況發(fā)生的概率是比較低的，我們更常遇到的是一般情況。比如說盡管快速排序算法與歸并排序算法的時間復雜度都為O(nlogn)，但是在相同的問題規(guī)模下，快速排序往往要比歸并排序快，因此快速排序算法的期望運行時間要比歸并排序的期望時間小。然而在最壞情況下，快速排序的時間復雜度會變?yōu)镺(n^2)，快速排序算法就是一個運行時間依賴于輸入的算法，對于這個問題，我們可以通過打亂輸入的待排序數(shù)組的順序來避免發(fā)生最壞情況。
4. 倍率實驗
下面我們來介紹一下算法（第4版） (豆瓣)一書中的“倍率實驗”。這個方法能夠簡單有效地預測程序的性能并判斷他們的運行時間大致的增長數(shù)量級。在正式介紹倍率實驗前，我們先來簡單介紹下“增長數(shù)量級“這一概念（同樣引用自《算法》一書）：
我們還是拿ThreeSum程序來舉例，假設g(N)表示在輸入數(shù)組尺寸為N時執(zhí)行if語句的次數(shù)。根據以上的定義，我們就可以得到g(N) ~ N ^ 3（當N趨向于正無窮時，g(N) / N^3 趨近于1）。所以g(N)的增長數(shù)量級為N^3，即ThreeSum算法的運行時間的增長數(shù)量級為N^3。
現(xiàn)在，我們來正式介紹倍率實驗（以下內容主要引用自上面提到的《算法》一書，同時結合了一些個人理解）。首先我們來一個熱身的小程序：
以上代碼會以250為起點，每次講ThreeSum的問題規(guī)模翻一倍，并在每次運行ThreeSum后輸出本次問題規(guī)模和對應的運行時間。運行以上程序得到的輸出如下所示：
上面的輸出之所以和理論值有所出入是因為實際運行環(huán)境是復雜多變的，因而會產生許多偏差，盡可能減小這種偏差的方式就是多次運行以上程序并取平均值。有了上面這個熱身的小程序做鋪墊，接下來我們就可以正式介紹這個“可以簡單有效地預測任意程序執(zhí)行性能并判斷其運行時間的大致增長數(shù)量級”的方法了，實際上它的工作基于以上的DoublingTest程序，大致過程如下：
DoublingRatio程序如下：
運行倍率程序，我們可以得到如下輸出：
我們可以看到，time/prev確實收斂到了8（2^3)。那么，為什么通過使輸入不斷翻倍而反復運行程序，運行時間的比例會趨于一個常數(shù)呢？答案是下面的[倍率定理]:
以上定理的證明很簡單，只需要計算T(2N) / T(N)在N趨向于正無窮時的極限即可。其中，“a * N^b * lgN”基本上涵蓋了常見算法的增長量級（a、b為常數(shù)）。值得我們注意的是，當一個算法的增長量級為NlogN時，對它進行倍率測試，我們會得到它的運行時間的增長數(shù)量級約為N。實際上，這并不矛盾，因為我們并不能根據倍率實驗的結果推測出算法符合某個特定的數(shù)學模型，我們只能夠大致預測相應算法的性能（當N在16000到32000之間時，14N與NlgN十分接近）。
5. 均攤分析
考慮下我們之前在 深入理解數(shù)據結構之鏈表 中提到的ResizingArrayStack，也就是底層用數(shù)組實現(xiàn)的支持動態(tài)調整大小的棧。每次添加一個元素到棧中后，我們都會判斷當前元素是否填滿的數(shù)組，若是填滿了，則創(chuàng)建一個尺寸為原來兩倍的新數(shù)組，并把所有元素從原數(shù)組復制到新數(shù)組中。我們知道，在數(shù)組未填滿的情況下，push操作的復雜度為O(1)，而當一個push操作使得數(shù)組被填滿，創(chuàng)建新數(shù)組及復制這一工作會使得push操作的復雜度驟然上升到O(n)。
對于上面那種情況，我們顯然不能說push的復雜度是O(n)，我們通常認為push的“平均復雜度”為O(1)，因為畢竟每n個push操作才會觸發(fā)一次“復制元素到新數(shù)組”，因而這n個push把這一代價一均攤，對于這一系列push中的每個來說，它們的均攤代價就是O(1)。這種記錄所有操作的總成本并除以操作總數(shù)來講成本均攤的方法叫做均攤分析（也叫攤還分析）。
三、小試牛刀之實戰(zhàn)名企面試題
前面我們介紹了算法分析的一些姿勢，那么現(xiàn)在我們就來學以致用，一起來解決幾道一線互聯(lián)網企業(yè)有關于算法分析的面試/筆試題。
看到這道題要我們分析算法時間復雜度后，我們要做的第一步便是確定關鍵操作，這里的關鍵操作顯然是if語句，那么我們只需要判斷if語句執(zhí)行的次數(shù)即可。首先我們看到這是一個遞歸過程：foo會不斷的調用自身，直到foo的實參小于等于1，foo就會返回1，之后便不會再執(zhí)行if語句了。由此我們可以知道，if語句調用的次數(shù)為n次，所以時間復雜度為O(n)。
這道題明顯要比上道題難一些，那么讓我們來按部就班的解決它。首先，它的關鍵操作時if語句，因此我們只需判斷出if語句的執(zhí)行次數(shù)即可。以上函數(shù)會在n > 0的時候不斷遞歸調用自身，我們要做的是判斷在到達遞歸的base case（即n <= 0）前，共執(zhí)行了多少次if語句。我們假設if語句的執(zhí)行次數(shù)為T(n, m, o)，那么我們可以進一步得到：T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) （當n > 0時）。我們可以看到base case與參數(shù)m, o無關，因此我們可以把以上表達式進一步簡化為T(n) = 2T(n-1)，由此我們可得T(n) = 2T(n-1) = (2^2) * T(n-2)......所以我們可以得到以上算法的時間復雜度為O(2^n)。
以上算法的關鍵操作即while語句中的兩條賦值語句，我們只需要計算這兩條語句的執(zhí)行次數(shù)即可。我們可以看到，當x - y > e時，while語句體內的語句就會執(zhí)行，x = (x + y) / 2使得x不斷變�。ó攜<<x時，執(zhí)行一次這個語句會使x變?yōu)榧s原來的一半），假定y的值固定在1，那么循環(huán)體的執(zhí)行次數(shù)即為~logm，而實際情況是y在每次循環(huán)體最后都會被賦值為m / x，這個值總是比y在上一輪循環(huán)中的值大，這樣一來x-y的值就會更小，所以以上算法的時間復雜度為O(logm)。
核心關注：拓步ERP系統(tǒng)平臺是覆蓋了眾多的業(yè)務領域、行業(yè)應用，蘊涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務管理理念，功能涉及供應鏈、成本、制造、CRM、HR等眾多業(yè)務領域的管理，全面涵蓋了企業(yè)關注ERP管理系統(tǒng)的核心領域，是眾多中小企業(yè)信息化建設首選的ERP管理軟件信賴品牌。
轉載請注明出處：拓步ERP資訊網http://www.ezxoed.cn/
本文標題：算法分析的正確姿勢
相關文章
