時間複雜度

<image>

在電腦科學中，演算法的時間複雜度（time complexity）是一個函數，用於定性描述演算法的運行時間隨輸入長度增長而變化的情況；這裡的輸入長度通常指表示輸入值的字串長度。時間複雜度常用大O符號表述，並忽略函數中的低階項和首項係數。採用這種表述時，時間複雜度也可稱為漸近時間複雜度，即考察輸入規模趨近無窮時的情況。例如，如果一個演算法對於任何大小為 n（且 n 大於某個 n0）的輸入，至多需要 5n3 + 3n 的時間運行完畢，則該演算法的漸近時間複雜度是 O(n3)。

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

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

## 常見時間複雜度列表

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

名稱｜複雜度類｜運行時間（$T(n)$）｜運行時間舉例｜演算法舉例

常數時間｜$O(1)$｜10｜判斷一個二進位數的奇偶

反阿克曼時間｜$O(\alpha(n))$｜併查集的單個操作的平攤時間

迭代對數時間｜$O(\log^{*}n)$｜分散式圓環著色問題

對數對數時間｜$O(\log \log n)$｜有界優先隊列的單個操作

對數時間｜DLOGTIME｜$O(\log n)$｜$\log n$，$\log n^2$｜二分搜索

冪對數時間｜$(\log n)^{O(1)}$｜$(\log n)^2$

（小於1次）冪時間｜$O(n^c)$，其中$0 < c < 1$｜$n^{\frac{1}{2}}$，$n^{\frac{2}{3}}$｜K-d樹的搜索操作

線性時間｜$O(n)$｜$n$｜無序數組的搜索

線性迭代對數時間｜$O(n\log^{*}n)$｜萊姆德·賽德爾的三角分割多邊形演算法

線性對數時間｜$O(n\log n)$｜$n\log n$，$\log n!$｜最快的比較排序

二次時間｜$O(n^2)$｜$n^2$｜冒泡排序、插入排序

三次時間｜$O(n^3)$｜$n^3$｜矩陣乘法的基本實現，計算偏相關

多項式時間｜P｜$2^{O(\log n)} = n^{O(1)}$｜$n$，$n \log n$，$n^{10}$｜線性規劃中的卡馬卡演演算法，AKS質數測試

准多項式時間｜QP｜$2^{(\log n)^{O(1)}}$｜$n^{\log \log n}$，$n^{\log n}$ |｜關於有向斯坦納樹問題最著名的$O(\log^2 n)$近似算法

次指數時間（第一定義）｜SUBEXP｜$O(2^{n^{\epsilon}})$，對任意的ε > 0｜$O(2^{(\log n)^{\log \log n}})$｜假設複雜性理論推測，BPP 包含在 SUBEXP 中。

次指數時間（第二定義）｜2o(n）｜2n1/3｜用於整數分解與圖形同構問題的著名演演算法

指數時間｜E｜2O(n)｜1.1n, 10n｜使用動態規劃解決旅行推銷員問題

階乘時間｜O(n!)｜n!｜通過暴力搜索解決旅行推銷員問題

指數時間｜EXPTIME｜2poly(n)｜2n, 2n2

雙重指數時間｜2-EXPTIME｜22poly(n)｜22n｜在預膨脹算術中決定一個給定描述的真實性

## 常數時間

若對於一個演算法，$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），而不論對數的底是多少，是對數時間演算法的標準記法。

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

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

快速冪 就是一個經典例子。要計算n次方只需要O(log n)的時間。

```c++
long long power(long long p, long long n)
{
	long long ans = 1;
	while (n)
	{
		if (n & 1) ans = (ans * p) % Mod;
		p = p * p % Mod;
		n >>= 1;
	}
	return ans;
}
```

## 冪對數時間

對於某個常數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的多項式時間來說，線性對數時間卻增長得慢。

## 多項式時間

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

我們先定義一個計算模型，稱作算術模型。在算術模型中，數字之間的算術運算（加減乘除、比較大小）可以在單位時間內完成（即 O(1) 時間內完成，與數字大小無關）。

如果一個演算法在算術模型下的操作數是輸入中的數字個數的多項式，並且空間複雜度是輸入規模（而非數字個數）的多項式，則這個演算法是 強多項式時間 的。由於算術操作在一般的計算模型下可以在輸入規模（即數字大小的對數）的多項式時間內完成，強多項式時間的演算法一定是多項式時間的。

一般來說，強多項式時間的演算法的時間複雜度與值域無關。

如果一個演算法是多項式時間的但不是強多項式時間的，則它是弱多項式時間的，這表明它在圖靈機模型下是多項式的，但在算術模型下不是。

例如，計算最大公約數的歐幾里得演算法，時間複雜度為 O(log a + log b)（a 和 b 為輸入的數的大小），是弱多項式時間的。因為它的實際運行時間是關於a,b的長度（位數）的多項式，而不是關於輸入中的整數數量的（這個數量總是2）。

如果一個演算法的用時是值域的多項式，則稱它是偽多項式時間的。偽多項式時間的演算法可能是多項式時間的也可能不是，可能不是多項式時間是因為表示一個大小為 n 的正整數一般只需要 O(log n) 個二進位位，所以關於值域多項式時間的演算法往往關於輸入長度是指數級時間的。雖然從定義上來說偽多項式時間也可能是多項式時間，但當我們說一個演算法是偽多項式時間的，一般都是說這個演算法不是多項式時間的。

例如，背包問題是 NP-hard 問題，但它有基於動態規劃的偽多項式時間的解法。

### 複雜度類

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

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

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

## 超越多項式時間

如果一個演算法的時間 T(n) 沒有任何多項式上界，則稱這個演算法具有超越多項式（superpolynomial）時間。在這種情況下，對於所有常數 c 我們都有 T(n) = ω(nc)，其中 n 是輸入參數，通常是輸入的數據量（比特數）。指數時間顯然屬於超越多項式時間，但是有些演算法僅僅是很弱的超越多項式演算法。例如，Adleman-Pomerance-Rumely 質數測試對於 n 比特的輸入需要運行 nO(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)$$

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

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