算法的經驗分析

摘要：我們以前應用過許多算法分析，雖然這些技術能夠成功應用于許多簡單的算法，但即使有許多高級技術的支持，數學也遠不是萬能的。實際上我們能夠證明，即使許多貌似簡單的算法也是很難用數學的精確性和嚴格性來分析的。除了可以對算法的效率做數學分析以外，另一種主要的方法是對算法的效率做經驗分析。

關鍵詞：算法；效率；偽隨機數；散點圖

中圖分類號：TP302文獻標識碼：A文章編號：1009-3044(2008)20-30281-02

Empirical Analysis of Algorithms

LI Zhan-xin

（Guangdong Technical School of Metallurgy，Guangzhou 511430，China）

Abstract：Algorithmic analysis has been put into application in many ways.And it has been applied in many simple algorithm successfully. Though this technology has been supported by many other advanced techniques， mathematics are not definitely omnipotent. In fact it has been proved that it is difficult to analyze many seemingly simple algorithm through the accuracy and preciseness of mathematics.Besides mathematic analysis of efficiency of algorithm， we can focus on the empirical analysis of it.

Key words：Algorithms;efficiency;pseudo-random number;scatter diagram

我們常常希望算法具有許多良好的特性，除了正確性，最重要的的特性就是“效率”了。實際上，有兩種算法效率：時間效率和空間效率。對特定算法設計技術使問題求解的有效策略。下面這個方案清楚地描述了算法分析中的經驗分析。

1 對算法效率做經驗分析的通用方案

(1)了解實驗的目的。

(2)決定用來度量效率的量度M和度量單位（操作次數還是直接時間）。

(3)決定輸入樣本的特性（它的范圍和大小等）。

(4)為實驗準備算法（或者若干算法）的程序實現。

(5)生成輸入樣本。

(6)對輸入樣本運行算法（或者若干算法），并記錄觀察到的實驗數據。

(7)分析獲得的實驗數據。

在做算法的經驗分析時，我們的目標往往不盡相同。可選的目標包括：檢驗算法效率理論上的結論的精確性，比較相同問題的不同算法或者相同算法的不同實現的效率，先假定算法的效率類型，然后在特定的計算機上確定實現該算法的程序效率。顯而易見，這種實驗的設計依賴于實驗者打算探尋什么答案。

2 對算法的效率進行度量的方法

第一種方法就是在算法的程序實現中插入一些計數器來對算法執行的基本操作次數進行計數。這常常是一種簡單的操作，我們只要留心程序的哪些地方可以會出現基本操作，并保證對每次基本操作都進行計數。雖然這項工作常常很簡單，我們每次修改完程序以后還要對程序做測試，一方面保證它能夠正確解決問題，另一方面保證它對基本操作的計數是正確的。

第二種方法是記錄待討論算法的程序實現的運行時間。最簡單的做法是利用系統命令，就像UNIX中的time命令一樣。另一種測量程序段運行時間的做法是，在程序段德剛開始處（tstart）和才結束時（tfinish）查詢系統的時間，然后計算著兩個時間的差（tfinish—tstart）。再C和C++中，我們可以用clock函數來達到這個目的；在Java中，System類的currentTimeMillis()方法提供了這個功能。

然而，我們應該了解這樣一些事實。第一，一般來說，系統時間并不是十分精確的，對相同程序的相同輸入重復運行多次，可能會得到有輕微差異的統計結果。一個明顯的補救辦法是進行多次這樣的度量，然后取它們的平均值或中值作為該樣本的觀察值。第二，由于現代計算機的速度很快，程序的運行時間可能被報告為0，使得記錄完全失敗。解決這種困境的標準做法是用一個特定的循環多次運行這段程序，度量總運行時間，然后除以循環的重復次數。第三，在一個運行分時系統（像UNIX）的計算機上，所報告的時間很可能包含了CPU運行其他程序的時間，很明顯這完全有悖于實驗的初衷。所以我們應該引起注意，并要求系統提供專門用于運行我們的程序的時間（在UNIX中，這個時間稱為“用戶時間”，time命令中就提供了這個功能）。

因此，度量物理運行時間存在著一些弊端，既有原則上的，也有技術上的，而統計基本操作的運行次數就沒有這些缺陷。但另一方面，物理運行時間提供了特定運行環境下的算法性能的詳細信息。這些信息對于實驗者來說，要比算法的漸進效率類型更重要。另外，對程序不同部分的運行時間進行度量能夠提示出程序性能的瓶頸，而對于算法基本操作進行抽象分析是做不到這一點的。搜這樣的數據——稱為剖面，對于算法運行時間的經驗分析來說是寶貴的資源；大多數環境中都提供了相關的系統工具，我們通常可以使用這些工具來獲得我們所需要的數據。

3 對算法的效率進行度量的樣本輸入

無論決定用計時方法還是用基本操作計數法來度量效率，我們都必須確定實驗的輸入樣本。一般來說，我們的目標是用一個樣本來代表一類“典型”的輸入，所以，我們面臨的挑戰是理解什么輸入是“典型”輸入。對于有些類型的算法，比如旅行商問題算法，研究人員制定了一系列輸入實例用來作為測試的基準。但更常見的情況是，輸入樣本必須由實驗者來確定。一般來說，我們必須做幾方面的決定：樣本的規模（一種比較明智的做法是，先從一個相對較小的樣本開始，以后如有必要再加大），輸入樣本的范圍（一般來說，既不要小的沒有意義，一不要過分大）以及一個在所選擇范圍為產生輸入的程序。就最后一個方面來說，輸入的規模即可以符合一種模式（例如，1000，2000，3000，……10000或者500，1000，2000，4000，……128000），也可以隨機產生（例如，在最大值和最小值之間均勻分布）。

根據一個模式來改變輸入規模的主要高處是，我們很容易分析這種改變所帶來的影響。例如，如果一個樣本的規模每次都會翻倍，我們可以計算所觀察到的度量M之間的比率M(2n)/M(n)，看一看該比率所揭示的算法典型性能是否屬于一個基本的效率類型。輸入規模不隨機變化的主要弊病是存在這種可能性，即我們所研究的算法在我們所挑選的樣本上正好表現出非典型的行為。例如，如果所有樣本的規模都是偶數，但所研究的算法對于奇數規模的輸入卻運行得十分緩慢，得出的經驗結論就會使人誤入歧途。

對于實驗樣本的規模，我們需要重點考慮的另一個因素是，是否需要包括同樣規模樣本的多個不同實例。如果我們預測，對于相同規模的不同實例，我們觀測到的度量值會有相當的不同，那么，讓樣本中的每一種規模都包括多個實例是比較明智的（統計學中有許多很成熟的方法幫助實驗者來作這種決定）。當然，如果樣本中包含相同規模的若干實驗，應該計算并研究每種每種規模的觀察結果的平均值或者中值，而不是僅僅研究單獨的樣本點。

4 算法經驗分析中的結果分析

對于算法效率的實驗分析來說，大多數情況下都需要產生一些隨機數。即使我們決定對輸入規模應用的一種模式，我們仍然希望輸入的實例會自動隨機產生。目前，在一臺數字式的計算機上產生隨機數還是一個難題，因為原理上，這個問題只能近似解決。這就是為什么計算機科學家傾向于把這種數稱為偽隨機數。從實用的角度看，獲得這種數的最簡單和最自然的方法是利用計算機語言的函數庫提供的隨機數發生器。典型情況下，它會輸出一個均勻分布在0和1區間中的（偽）隨機變量的值。如果需要一個另外一種隨機變量，我們應該做一個相應的變換。例如，x是一個均勻分布在0≤x＜1區間上的連續隨機變量，變量y=l+x?骔(r-l)」就會均勻地分布在l和r-l間的整數上，其中l和r是兩個整數(r＜l)。

另外，有幾個已知的生成（偽）隨機數的算法，我們可以選擇一個來實現。它們中使用最廣泛、研究最徹底的一個算法是所謂的線性同余法。

這段簡單的算法代碼會令人誤以為求偽隨機數并不復雜，其實如何選擇算法參數才是真正的難點。基于復雜的數學分析，這里給出一部分建議：seed可以任意選擇，并且常常將它設為當前的日期或者時間；m應該是一個較大數，出于方便的考慮，可以把它定為2w，w是計算機的字長；a可以是0.01m和0.99m間的任何整數，除了a mod 8=5以外，它的值不要體現出任何模式；可以選擇1作為b的值。

作為實驗結果的經驗數據需要記錄下來，然后拿來作分析。數據可以用數值的形式記錄在表格中或者表現為散點圖的形式，散點圖就是在笛卡爾兒坐標系中用點將數據標出。任何時候只要可行，都應該同時使用這兩種方法，因為這兩種方法各有利弊。

以表格呈現數據的主要優點是，我們可以很方便地對它們進行計算。例如，我們可以計算M(n)/g(n)的比率，其中g(n)是所討論算法的效率類型的候選對象。如果該算法的確屬于Θ(g(n))，那么很可能當n變得越來越大時，這個比率會趨向于一個大于0的常數（注意，一個粗心的新手有時會假設這個常數必須為1，這顯然是不符合Θ(g(n))的定義的）。我們也可以計算M(2n)/M(n)的比率，看一看當輸入的規模翻倍的時候，運行時間是如何變化的。

另一方面，散點圖這種形式也會幫助我們確定可能的算法效率類型。一個對數算法的散點圖會具有一個上凸的形狀，這把它同其它效率類型區分開來。一個線性算法的散點圖趨向于分布在一條直線的周圍，或者更一般地來說，包含在兩根直線的當中區域。屬于Θ(nlgn)和Θ(n2)的函數的散點圖都會具有一個下凹的形狀，使我們很難把它們區分開來。一個立方算法的散點圖也具有一個下凹的形狀，但它的量度值顯示出非常快速的增長。一個指數算法在垂直軸上很可能需要一種對數刻度，我們在圖上標出的不是M(n)，而是logaM(n)(2或者10常常被用作對數的底)。在這樣一種坐標系中，一個真正的指數算法的散點圖應該像一個線性函數，因為M(n)≈can意味著logbM(n)≈logbc+nlogba。

經驗分析的一種可能應用是：對于不包含在實驗樣本中的輸入樣本，我們可以試著去與測算法會表現出來的性能。例如，如果在樣本實例中，我們觀察到的M(n)/g(n)的比率接近某些常數c，對于n的其他值，我們可以用cg(n)的積來近似表示M(n)。這種做法雖然有道理，但我們應該小心使用，尤其對于那些在樣本值范圍以外的n值來說（相對于專門處理樣本范圍內的值內推法來說，數學家把

這種方法稱為外推法），而且，用這種方法得到的估計值常常不做精確度聲明。當然，我們也可以使用標準的數據統計技術來做分析和預測。然而，請注意，大多數這種技術都是基于特定的概率假定，這種假定與所討論的實驗數據可能符合，也可能不符合。

5 結語

最后，我們應該指出算法的數學分析和經驗分析的基本區別。數學分析的主要優點是它并不依賴于特定的輸入，但它的主要缺點是適用性不強，這一點對于研究平均效率來說尤其明顯。經驗分析的主要優點是它能夠適用于任何算法，但它的結論依賴于實驗中使用的特定樣本實例和計算機。

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京:清華大學出版社，2006.

[2] Anany Levitin.算法設計與分析[M].潘彥，譯.北京:清華大學出版社，2007.