算法分析

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

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

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

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

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

時間資源消耗

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

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

通常有兩種定義消耗的方法：^{[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符號

非正式地，如果一個關於 ${\displaystyle n}$ 的函數 ${\displaystyle f(n)}$，乘以一個係數以後，能夠為某個算法在輸入數據大小 ${\displaystyle n}$ 足夠大的情況下的運行時間提供一個上界，那麼稱此算法按該函數的階增長。一個等價的描述是，當輸入大小 ${\displaystyle n}$ 大於某個 ${\displaystyle n_{0}}$ 時，存在某個常數 ${\displaystyle c}$，使得算法的運行時間總小於 ${\displaystyle c\times f(n)}$。常用大O符號對此進行描述。比如，插入排序的運行時間隨數據大小二次增長，那麼插入排序具有 ${\displaystyle O(n^{2})}$ 的時間複雜度。大O符號通常用於表示某個算法在最差情況下的運行時間，但也可以用來表述平均情況的運行時間。比如，快速排序的最壞運行時間是 ${\displaystyle O(n^{2})}$，但是平均運行時間則是 ${\displaystyle O(n\log n)}$。^[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 步操作需時 T₁，第 2 步操作需時 T₂，如此類推。

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

${\displaystyle T_{1}+T_{2}+T_{3}+T_{7}}$

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

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

${\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}}$

上式可被因式分解^[9]為：

${\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]}$

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

${\displaystyle 2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}}$

${\displaystyle =T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}}$

上式可被分解為：

${\displaystyle T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}}$

${\displaystyle =\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}}$

${\displaystyle =T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}}$

${\displaystyle =\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}}$

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

${\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}}$

改寫一下：

${\displaystyle f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}$

通常情況下，一個函數的最高次項對它的增長率起到主導作用。在此例里，n² 是最高次項，所以有結論 ${\displaystyle f(n)=O(n^{2})}$。

嚴格證明如下：證明 ${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}}$

${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}}$

${\displaystyle \leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ (n\geq 0)}$

令 k 為一個常數，其大於從 T₁ 到 T₇ 所有的數。

${\displaystyle T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k}$

${\displaystyle =2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\,(n\geq 1)=12kn^{2}}$

因此有

${\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}}$，其中 ${\displaystyle c=12k,n_{0}=1}$

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

${\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\,(n\geq 1)=O(n^{2}).}$

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

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

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

在這個例子裏，當文件大小 n 增長的時候，內存消耗會以指數增長，或 ${\displaystyle O(2^{n})}$。這個速度非常快，很容易使得資源消耗失去控制。

參見

• 平攤分析
• 漸近分析
• 漸近時間複雜度
• 計算時間
• 大O符號
• 計算複雜性理論
• 主定理
• NP-完全
• 數值分析
• 多項式時間
• 程序優化
• 性能分析
• 可擴放性
• 平滑分析
• 時間複雜度，包括常見算法的增長率列表

註釋

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. 在算法分析的場合里，常用 ${\displaystyle \log }$ 或 ${\displaystyle \lg }$ 作為 ${\displaystyle \log _{2}}$ 的簡稱。
8. 但這對量子計算機不成立。
9. 可用數學歸納法證明 ${\displaystyle 1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}}$
10. 比起上面的方法，這個方法忽略了結束循環的判斷語句所消耗的時間，但很明顯可以證明這種忽略不影響最後結果。

來源

書籍

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford. Introduction to Algorithms. Chapter 1: Foundations Second. Cambridge, MA: MIT Press and McGraw-Hill. 2001: 3–122. ISBN 0-262-03293-7.
• Sedgewick, Robert. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching 3rd. Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-31452-6.
• Knuth, Donald. The Art of Computer Programming. Addison-Wesley.
• Greene, Daniel A.; Knuth, Donald E. Mathematics for the Analysis of Algorithms Second. Birkhäuser. 1982. ISBN 3-7643-3102-X.
• Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2010. ISBN 978-0-521-88473-0.