跳至內容

算法分析

維基百科,自由的百科全書

計算機科學中,算法分析(英語:Analysis of algorithm)是分析執行一個給定算法需要消耗的計算資源數量(例如計算時間,存儲器使用等)的過程。算法的效率或複雜度在理論上表示為一個函數。其定義域是輸入數據的長度(通常考慮任意大的輸入,沒有上界),值域通常是執行步驟數量(時間複雜度)或者存儲器位置數量(空間複雜度)。算法分析是計算複雜度理論的重要組成部分。

理論分析常常利用漸近分析估計一個算法的複雜度,並使用大O符號大Ω符號大Θ符號作為標記。舉例,二分查找所需的執行步驟數量與查找列表的長度之對數成正比,記為 ,簡稱為「對數時間」。通常使用漸近分析的原因是,同一算法的不同具體實現的效率可能有差別。但是,對於任何給定的算法,所有符合其設計者意圖的實現,它們之間的性能差異應當僅僅是一個係數。

精確分析算法的效率有時也是可行的,但這樣的分析通常需要一些與具體實現相關的假設,稱為計算模型。計算模型可以用抽象機器來定義,比如圖靈機。或者可以假設某些基本操作在單位時間內可完成。

假設二分查找的目標列表總共有 n 個元素。如果我們假設單次查找可以在一個時間單位內完成,那麼至多只需要 單位的時間就可以得到結果。這樣的分析在有些場合非常重要。

算法分析在實際工作中是非常重要的,因為使用低效率的算法會顯著降低系統性能。在對運行時間要求極高的場合,耗時太長的算法得到的結果可能是過期或者無用的。低效率算法也會大量消耗計算資源。

時間資源消耗

[編輯]

時間複雜度分析和如何定義「一步操作」有緊密聯繫。作為算法分析成立的一項基本要求,單步操作必須能夠在確定的常量時間內完成。

實際情況很複雜。舉例,有些分析方法假定兩個數相加是單個步驟,但這假定可能不成立。若被分析的算法可以接受任意大的數,則無法保證相加操作能夠在確定的時間內完成。

通常有兩種定義消耗的方法:[1] [2] [3] [4] [5]

  • 單一消耗:每一步操作的消耗定義為一個常量,與參與運算的數據的大小無關。
  • 對數消耗:每一步操作的消耗,均與參與運算的數據的長度(位數)成正比。

後者更難以應用,所以只在必要時使用。一個例子是對接受任意精度數據的算法(比如密碼學中用到的一些算法)的分析。

人們常常忽略一點:算法的效率的理論界限,通常建立在比實際情況更加嚴格的假定之上。因此在實際中,算法效率是有可能突破理論的界限的。[6]

經驗分析的缺陷

[編輯]

算法是平台無關的,也即一個算法可以在任意計算機、任意作業系統上、用任意程式語言實現。因此,算法性能的相對好壞,不能僅僅通過基於運行記錄的經驗來判斷。

舉例:一個程序在大小為 n 的有序數組中搜索元素。假設該程序在一台先進的電腦 A 上用線性搜索實現,在一台老舊的電腦 B 上用二分搜索實現。性能測試的結果可能會如下:

數組長度 n 計算機 A 的運行時間
(以納秒計)
計算機 B 的運行時間
(以納秒計)
15 7 100,000
65 32 150,000
250 125 200,000
1,000 500 250,000

通過這些數據,很容易得出結論說計算機 A 運行的算法比計算機 B 的算法要高效得多。但假如輸入的數組長度顯著增加的話,很容易發現這個結論的錯誤。 以下是另一組數據:

數組長度 n 計算機 A 的運行時間
(以納秒計)
計算機 B 的運行時間
(以納秒計)
15 7 100,000
65 32 150,000
250 125 200,000
1,000 500 250,000
... ... ...
1,000,000 500,000 500,000
4,000,000 2,000,000 550,000
16,000,000 8,000,000 600,000
... ... ...
63,072 × 1012 31,536 × 1012納秒,
約等於 1 年
1,375,000 納秒,
或 1.375 毫秒

計算機 A 運行的線性搜索算法具有線性時間。它的運行時間直接與輸入規模成正比。輸入大小若加倍,運行時間同樣加倍。而計算機 B 運行的二分搜索算法具有對數時間。輸入大小若加倍,運行時間僅僅增加一個常量,在此例中是 25,000 納秒。即使計算機 A 明顯性能更強,在輸入不斷增加的情況下,計算機 B 的運行時間終究也會比計算機 A 更短,因為它運行的算法的增長率小得多。

增長的階

[編輯]

非正式地,如果一個關於 的函數 ,乘以一個係數以後,能夠為某個算法在輸入數據大小 足夠大的情況下的運行時間提供一個上界,那麼稱此算法按該函數的階增長。一個等價的描述是,當輸入大小 大於某個 時,存在某個常數 ,使得算法的運行時間總小於 。常用大O符號對此進行描述。比如,插入排序的運行時間隨數據大小二次增長,那麼插入排序具有 的時間複雜度。大O符號通常用於表示某個算法在最差情況下的運行時間,但也可以用來表述平均情況的運行時間。比如,快速排序的最壞運行時間是 ,但是平均運行時間則是 [7]

運行時間複雜度的分析

[編輯]

分析一個算法的最壞運行時間複雜度時,人們常常作出一些簡化問題的假設,並分析該算法的結構。以下是一個例子:

1    从输入值中获取一个正数
2    if n > 10
3        print "耗时可能较长,请稍候……"
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "完成!"

一台給定的電腦執行每一條指令的時間是確定[8]的,並可以用 DTIME 描述。 假設第 1 步操作需時 T1,第 2 步操作需時 T2,如此類推。

步驟 1、2、7 只會運行一次。應當假設在最壞情況下,步驟 3 也會運行。步驟 1 至 3 和步驟 7 的總運行時間是:

步驟 4、5、6 中的循環更為複雜。步驟 4 中的最外層循環會執行 (n + 1) 次(需要一次執行來結束 for 循環,因此是 (n + 1) 次而非 n 次),因此會消耗 T4 × (n + 1) 單位時間。內層循環則由 i 的值控制,它會從 1 迭代到 n。 第一次執行外層循環時,j 從 1 迭代到 1,因此內層循環也執行一次,總共耗時 T6 時間。以及內層循環的判斷語句消耗 3T5 時間。

所以,內層循環的總共耗時可以用一個等差級數表示:

上式可被因式分解[9]為:

類似地,可以分析內層循環的判斷語句:

上式可被分解為:

因此該算法的總運行時間為:

改寫一下:

通常情況下,一個函數的最高次項對它的增長率起到主導作用。在此例里,n² 是最高次項,所以有結論

嚴格證明如下:證明

令 k 為一個常數,其大於從 T1 到 T7 所有的數。

因此有

,其中

還可以假定所有步驟全部消耗相同的時間,它的值比 T1 到 T7 中任意一個都大。這樣的話,這個算法的運行時間就可以這樣來分析:[10]

其他運算資源的增長率分析

[編輯]

運用與分析時間相同的方法可以分析其他運算資源的消耗情況,比如存儲器空間的消耗。例如,考慮以下一段管理一個文件的內存使用的偽代碼

while (文件打开)
     n = 文件大小
    for n 每增长 100kb
        为该文件分配多一倍的内存空间

在這個例子裏,當文件大小 n 增長的時候,內存消耗會以指數增長,或 。這個速度非常快,很容易使得資源消耗失去控制。

參見

[編輯]

註釋

[編輯]
  1. ^ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974. , section 1.3
  2. ^ Juraj Hromkovič. Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. 2004: 177–178. ISBN 978-3-540-14015-3. 
  3. ^ Giorgio Ausiello. Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. 1999: 3–8. ISBN 978-3-540-65431-5. 
  4. ^ Wegener, Ingo, Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag: 20, 2005, ISBN 978-3-540-21045-0 
  5. ^ Robert Endre Tarjan. Data structures and network algorithms. SIAM. 1983: 3–7. ISBN 978-0-89871-187-5. 
  6. ^ Examples of the price of abstraction?頁面存檔備份,存於互聯網檔案館), cstheory.stackexchange.com
  7. ^ 在算法分析的場合里,常用 作為 的簡稱。
  8. ^ 但這對量子計算機不成立。
  9. ^ 可用數學歸納法證明
  10. ^ 比起上面的方法,這個方法忽略了結束循環的判斷語句所消耗的時間,但很明顯可以證明這種忽略不影響最後結果。

來源

[編輯]
書籍