时间复杂度

在電腦科學中，演算法的**時間複雜度**（time complexity）是一個函式，它定性描述該演算法的執行時間。這是一個代表演算法輸入值的字串的長度的函式。時間複雜度常用大 O 符號表述，不包括這個函式的低階項和首項係數。使用這種方式時，時間複雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。例如，如果一個演算法對於任何大小為 _n_ （必須比 _n0_ 大）的輸入，它至多需要 5_n_3 + 3_n_ 的時間執行完畢，那麼它的漸近時間複雜度是 O (_n_3)。

為了計算時間複雜度，我們通常會估計演算法的操作單元數量，每個單元執行的時間都是相同的。因此，總運行時間和演算法的操作單元數量最多相差一個常數係數。

相同大小的不同輸入值仍可能造成演算法的執行時間不同，因此我們通常使用演算法的最壞情況複雜度，記為 **_T_(_n_)** ，定義為任何大小的輸入 _n_ 所需的最大執行時間。另一種較少使用的方法是平均情況複雜度，通常有特別指定才會使用。時間複雜度可以用函式 _T_(_n_) 的自然特性加以分類，舉例來說，有著 _T_(_n_) = _O_(_n_) 的演算法被稱作「線性時間演算法」；而 _T_(_n_) = _O_(_M_n) 和 _M_n= O(_T_(_n_)) ，其中 _M_ ≥ _n_ > 1 的演算法被稱作「指數時間演算法」。

## 常見時間複雜度列表

以下表格統整了一些常用的時間複雜度類別。表中，poly (_x_) = _x_O(1)，也就是 _x_ 的多項式。

## 常數時間

若對於一個演算法， $T(n)$ 的上界與輸入大小無關，則稱其具有**常數時間**，記作 $O(1)$ 時間。一個例子是存取陣列中的單個元素，因為存取它只需要一條指令。但是，找到無序陣列中的最小元素則不是，因為這需要遍歷所有元素來找出最小值。這是一項線性時間的操作，或稱 $O(n)$ 時間。但如果預先知道元素的數量並假設數量保持不變，則該操作也可被稱為具有常數時間。

雖然被稱為「常數時間」，執行時間本身不須與問題規模無關，但它的**上界**必須是與問題規模無關的確定值。舉例，「如果 a > b 則交換 a、b 的值」這項操作，儘管具體時間會取決於條件「a > b」是否滿足，但它依然是常數時間，因為存在一個常數 t 使得所需時間總**不超過** t。

以下是一個常數時間的代碼片段：

```
int index = 5;
int item = list[index];
**if** (condition true) **then**
   perform some operation that runs in constant time
**else**
   perform some other operation that runs in constant time
**for** i = 1 **to** 100
   **for** j = 1 **to** 200
      perform some operation that runs in constant time
```

如果 $T(n)=O(c)$ ，其中 $c$ 是一個常數，這記法等價於標準記法 $T(n)=O(1)$ 。

## 對數時間

若演算法的 _T_(_n_) = **O(log _n_)**，則稱其具有**對數時間**。電腦使用二進位的記數系統，對數常常以 2 為底（即 log2 _n_，有時寫作 lg _n_）。然而，由對數的換底公式，loga _n_ 和 logb _n_ 只有一個常數因子不同，這個因子在大 O 記法中被丟棄。因此記作 O（log _n_），而不論對數的底是多少，是對數時間演算法的標準記法。

常見的具有對數時間的演算法有二元樹的相關操作和二分搜尋。

對數時間的演算法是非常有效的，因為每增加一個輸入，其所需要的額外計算時間會變小。

遞迴地將字串砍半並且輸出是這個類別函式的一個簡單例子。它需要 O（log n）的時間因為每次輸出之前我們都將字串砍半。
這意味著，如果我們想增加輸出的次數，我們需要將字串長度加倍。

## 冪對數時間

對於某個常數 _k_，若演算法的 _T_(_n_) = O((log _n_)k)，則稱其具有**冪對數時間**。例如，矩陣鏈排序可以通過一個 PRAM 模型。被在冪對數時間內解決。

## 次線性時間

對於一個演算法，若其符合 _T_(_n_) = o(_n_)，則其時間複雜度為**次線性時間**（**sub-linear time** 或 **sublinear time**）。實際上除了符合以上定義的演算法，其他一些演算法也擁有次線性時間的時間複雜度。例如有 O (_n_½) 葛羅佛搜尋演算法。

常見的非合次線性時間演算法都採用了諸如平行處理（就像 NC1 matrix 行列式計算那樣）、非古典處理（如同葛羅佛搜尋那樣），又或者選擇性地對有保證的輸入結構作出假設（如冪對數時間的二分搜尋）。不過，一些情況，例如在頭 log (n) 位元中每個字串有一個位元作為索引的字串組就可能依賴於輸入的每個位元，但又符合次線性時間的條件。

「次線性時間演算法」通常指那些不符合前一段的描述的演算法。它們通常執行於傳統電腦架構系列並且不容許任何對輸入的事先假設。但是它們可以是隨機化演算法，而且必須是真隨機演算法除了特殊情況。

## 線性時間

如果一個演算法的時間複雜度為 O (_n_)，則稱這個演算法具有線性時間，或 **O(_n_)** 時間。非正式地說，這意味著對於足夠大的輸入，執行時間增加的大小與輸入成線性關係。例如，一個計算列表所有元素的和的程式，需要的時間與列表的長度成正比。這個描述是稍微不準確的，因為執行時間可能顯著偏離一個精確的比例，尤其是對於較小的 n。

## 線性對數（準線性）時間

若一個演算法時間複雜度 T (n) = O (nlog n)，則稱這個演算法具有線性對數時間。因此，從其表達式我們也可以看到，線性對數時間增長得比線性時間要快，但是對於任何含有 n，且 n 的冪指數大於 1 的多項式時間來說，線性對數時間卻增長得慢。

## 多項式時間

### 強多項式時間與弱多項式時間

### 複雜度類別

從多項式時間的概念出發，在計算複雜度理論中可以得到一些複雜度類別。以下是一些重要的例子。

* **P**：包含可以使用確定型圖靈機在多項式時間內解決的決定性問題。
* **NP**：包含可以使用非確定型圖靈機在多項式時間內解決的決定性問題。
* **ZPP**：包含可以使用概率圖靈機在多項式時間內零錯誤解決的決定性問題。
* **RP**：包含可以使用概率圖靈機在多項式時間內解決的決定性問題，但它給出的兩種答案中（是或否）只有一種答案是一定正確的，另一種則有機率不正確。
* **BPP**：包含可以使用概率圖靈機在多項式時間內解決的決定性問題，它給出的答案有錯誤的概率在某個小於 0.5 的常數之內。
* **BQP**：包含可以使用量子圖靈機在多項式時間內解決的決定性問題，它給出的答案有錯誤的概率在某個小於 0.5 的常數之內。

在機器模型可變的情況下，P 在確定性機器上是最小的時間複雜度類別。例如，將單帶圖靈機換成多帶圖靈機可以使演算法執行速度以二次階提升，但所有具有多項式時間的演算法依然會以多項式時間執行。一種特定的抽象機器會有自己特定的複雜度類別分類。

## 超越多項式時間

如果一個演算法的時間 _T_(_n_) 沒有任何多項式上界，則稱這個演算法具有**超越多項式**（superpolynomial）時間。在這種情況下，對於所有常數 _c_ 我們都有 _T_(_n_) = ω(_n_c)，其中 _n_ 是輸入參數，通常是輸入的數據量（位元數）。指數時間顯然屬於超越多項式時間，但是有些演算法僅僅是很弱的超越多項式演算法。例如，Adleman-Pomerance-Rumely 質數測試對於 _n_ 位元的輸入需要運行 _n_O(log log _n_) 時間；對於足夠大的 _n_，這時間比任何多項式都快；但是輸入要大得不切實際，時間才能真正超過低階的多項式。

## 准多項式時間

**準多項式時間**演算法是運算慢於多項式時間的演算法，但不會像指數時間那麼慢。對一些固定的 $c>0$ ，準多項式時間演算法的最壞情況運行時間是 $2^{O((\log n)^{c})}$ 。如果準多項式時間演算法定義中的常數「c」等於 1，則得到多項式時間演算法；如果小於 1，則得到一個次線性時間演算法。

## 次指數時間

術語次指數時間用於表示某些演算法的運算時間可能比任何多項式增長得快，但仍明顯小於指數。在這種狀況下，具有次指數時間演算法的問題比那些僅具有指數演算法的問題更容易處理。「次指數」的確切定義並沒有得到普遍的認同，我們列出了以下兩個最廣泛使用的。

### 第一定義

如果一個問題解決的運算時間的對數值比任何多項式增長得慢，則可以稱其為次指數時間。更準確地說，如果對於每個 ε> 0，存在一個能於時間 O (2nε) 內解決問題的演算法，則該問題為次指數時間。所有這些問題的集合是複雜性 SUBEXP，可以按照 DTIME 的方式定義如下。

　
: ${\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon }}\right)$

### 第二定義

一些作者將次指數時間定義為 2o(_n_) 的運算時間。該定義允許比次指數時間的第一個定義更多的運算時間。這種次指數時間演算法的一個例子，是用於整數因式分解的最著名古典演算法 —— 普通數域篩選法，其運算時間約為 $2^{{\tilde {O}}(n^{1/3})}$ ，其中輸入的長度為 _n_。另一個例子是圖形同構問題的最著名演算法，其運算時間為 $2^{O({\sqrt {n\log n}})}$ 。

## 指數時間

若 _T_(_n_) 是以 2poly(_n_) 為上界，其中 poly (_n_) 是 _n_ 的多項式，則演算法被稱為**指數時間**。更正規的講法是：若 _T_(_n_) 對某些常數 _k_ 是由 O (2nk) 所界定，則演算法被稱為**指數時間**。在確定性圖靈機上認定為指數時間演算法的問題，形成稱為 **EXP** 的複雜性級別。

　
: ${\text{EXP}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{c}}\right)$

有時侯，指數時間用來指稱具有 _T_(_n_) = 2O(_n_) 的演算法，其中指數最多為 _n_ 的線性函式。這引起複雜性等級 **E**。

　
: ${\text{E}}=\bigcup _{c\in \mathbb {N} }{\text{DTIME}}\left(2^{cn}\right)$

## 雙重指數時間

若 _T_(_n_) 是以 22poly(_n_) 為上界，其中 poly (_n_) 是 _n_ 的多項式，則演算法被稱為雙重指數時間。這種演算法屬於複雜性等級 2-EXPTIME。

　
: ${\mbox{2-EXPTIME}}=\bigcup _{c\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{c}}}\right)$

眾所周知的雙重指數時間演算法包括：

* 預膨脹算術的決策程式
* 計算葛洛拿基底（在最差狀況）
* 實封閉體的量詞消去至少耗費雙重指數時間，而且可以在這樣的時間內完成。

## 參見

* L-notation
* 遊戲複雜度
* 計算複雜性理論
* 零一律
* 柯爾莫哥洛夫空間
* 柯氏複雜性
* 空間複雜度

## 參考資料