演算法分析

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

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

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

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

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

## 時間資源消耗

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

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

通常有兩種定義消耗的方法：

- 單一消耗：每一步操作的消耗定義為一個常量，與參與運算的數據的大小無關。
- 對數消耗：每一步操作的消耗，均與參與運算的數據的長度（位數）成正比。

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

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

### 經驗分析的缺陷

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

舉例：一個程序在大小為 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 更短，因為它運行的演算法的增長率小得多。

### 增長的階

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

$\log$

$\lg$

$\log_2$

### 運行時間複雜度的分析

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

```
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''' "完成！"
```

一台給定的電腦執行每一條指令的時間是確定的，並可以用 DTIME 描述。

假設第 1 步操作需時 T1，第 2 步操作需時 T2，如此類推。

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

$$T_1 + T_2 + T_3 + T_7$$

步驟 4、5、6 中的循環更為複雜。步驟 4 中的最外層循環會執行 (n + 1) 次（需要一次執行來結束 for 循環，因此是 (n + 1) 次而非 n 次），因此會消耗 T4 × (n + 1) 單位時間。內層循環則由 i 的值控制，它會從 1 迭代到 n。

第一次執行外層循環時，j 從 1 迭代到 1，因此內層循環也執行一次，總共耗時 T6 時間。以及內層循環的判斷語句消耗 3T5 時間。

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

$$T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6$$

上式可被因式分解

$1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}$

為：

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

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

$$2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5$$

$$= T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5$$

上式可被分解為：

$$T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5$$

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

$$= T_5 \left[ \frac{1}{2} (n^2 + n) \right] + n T_5$$

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

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

$$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$$

改寫一下：

$$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² 是最高次項，所以有結論 $f(n) = O(n^2)$。

嚴格證明如下：證明 $\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 \le cn^2,\ n \ge n_0$

$$\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$$

$$\le ( 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 為一個常數，其大於從 T1 到 T7 所有的數。

$$T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k$$

$$= 2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \, (n \geq 1) = 12kn^2$$

因此有

$\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 \le cn^2, n \ge n_0$，其中 $c = 12k, n_0 = 1$

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

$$4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \, (n \geq 1) =O(n^2).$$

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

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

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

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