時間複雜度

常見函式的時間複雜度

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

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

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

常見時間複雜度列表

以下表格統整了一些常用的時間複雜度類別。表中，poly(x) = x^O(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)}}$		關於有向斯坦納樹問題最著名的$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為底（即log₂ n，有時寫作lg n）。然而，由對數的換底公式，log_a n和log_b n只有一個常數因子不同，這個因子在大O記法中被丟棄。因此記作O（log n），而不論對數的底是多少，是對數時間演算法的標準記法。

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

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

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

// 递归输出一个字符串的右半部分
var right = function(str)
{
    var length = str.length;

    // 辅助函数
    var help = function(index)
    {

        // 递归情况：输出右半部分
        if(index < length){

            // 输出从index到数组末尾的部分
            console.log(str.substring(index, length));

            // 递归调用：调用辅助函数，将右半部分作为参数传入
            help(Math.ceil((length + index)/2));
        }

        // 基本情况：什么也不做
    }
    help(0);
}

冪對數時間

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

次線性時間

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

常見的非合次線性時間演算法都採用了諸如平行處理（就像NC₁ 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(2^nε) 內解決問題的演算法，則該問題為次指數時間。所有這些問題的集合是複雜性SUBEXP，可以按照 DTIME 的方式定義如下。

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

第二定義

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

指數時間

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

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

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

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

雙重指數時間

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

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

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

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

參見

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