Myujth

常见函数的时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必須比 n₀ 大）的输入，它至多需要 5n³ + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n³)。

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

相同大小的不同輸入值仍可能造成算法的執行時間不同，因此我們通常使用算法的最壞情況複雜度（英语：Worst-case complexity），記為 T(n) ，定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是平均情況複雜度（英语：average-case complexity），通常有特別指定才會使用。時間複雜度可以用函數 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)$		有界优先队列的单个操作^[1]
对数时间	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 12$ ， $n^frac 23$	K-d树的搜索操作
线性时间		$O(n)$	$n$	无序数组的搜索
线性迭代对数时间		$O(nlog ^*n)$		萊姆德·賽德爾（英语：Raimund Seidel）的三角分割多边形（英语：Polygon triangulation）算法
线性对数时间		$O(nlog n)$	$nlog n$ ， $log n!$	最快的比较排序
二次时间		$O(n^2)$	$n^2$	冒泡排序、插入排序
三次时间		$O(n^3)$	$n^3$	矩阵乘法的基本实现，计算部分相关性（英语：Partial correlation）
多项式时间	P	$2^O(log n)=n^O(1)$	$n$ ， $nlog n$ ， $n^10$	线性规划中的卡馬卡演算法（英语：Karmarkar's algorithm），AKS质数测试
准多项式时间	QP	$2^(log n)^O(1)$		关于有向斯坦纳树问题（英语：Steiner tree problem）最著名的 $O(log ^2n)$ 近似算法
次指数时间（第一定义）	SUBEXP	$O(2^n^epsilon )$ ，对任意的ε > 0	$O(2^(log n)^log log n)$	假設複雜性理論推測，BPP 包含在 SUBEXP 中。^[2]
次指数时间（第二定义）		2^o(n）	2^{n^1/3}	用於整數分解與圖形同構問題（英语：Graph isomorphism problem）的著名演算法
指数时间	E	2^O(n)	1.1ⁿ, 10ⁿ	使用动态规划解决旅行推销员问题
阶乘时间		O(n!)	n!	通过暴力搜索解决旅行推销员问题
指数时间	EXPTIME	2^poly(n)	2ⁿ, 2^n²
双重指数时间	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	在預膨脹算術（英语：Presburger arithmetic）中決定一個給定描述的真實性

常数时间

若对于一个算法， $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_an和log_bn只有一个常数因子不同，这个因子在大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模型.^[3]被在幂对数时间内解决。

次线性时间

对于一个演算法，若其符合T(n) = o(n)，则其时间复杂度为次线性时间（sub-linear time或sublinear time）。实际上除了符合以上定义的演算法，其他一些演算法也拥有次线性时间的时间复杂度。例如有O(n^½) 葛羅佛搜尋（英语：Grover's algorithm）演算法。

常见的非合次线性时间演算法都采用了诸如平行处理（就像NC₁ matrix行列式计算那样）、非古典處理（英语：Quantum algorithm）（如同葛羅佛搜尋那樣），又或者选择性地对有保证的输入结构作出假设（如幂对数时间的二分搜尋）。不过，一些情况，例如在头 log(n) 位元中每个字串有一个位元作为索引的字串组就可能依赖于输入的每个位元，但又符合次线性时间的条件。

「次线性时间演算法」通常指那些不符合前一段的描述的演算法。它们通常运行于传统电脑架構系列并且不容许任何对输入的事先假设。^[4]但是它们可以是随机化算法，而且必须是真随机算法除了特殊情况。

线性时间

如果一个算法的时间复杂度为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 質數測試（英语：Adleman–Pomerance–Rumely primality test）對於 n 比特的輸入需要運行 n^{O(log log n)} 時間；對於足夠大的 n，這時間比任何多項式都快；但是輸入要大得不切實際，時間才能真正超過低階的多項式。

准多项式时间

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

次指數時間

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

第一定义

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

displaystyle textSUBEXP=bigcap _varepsilon >0textDTIMEleft(2^n^varepsilon right)

第二定义

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

指数时间

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

displaystyle textEXP=bigcup _cin mathbb N textDTIMEleft(2^n^cright)

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

displaystyle textE=bigcup _cin mathbb N textDTIMEleft(2^cnright)

双重指数时间

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

displaystyle mbox2-EXPTIME=bigcup _cin mathbb N mboxDTIMEleft(2^2^n^cright)

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

預膨脹算術（英语：Presburger arithmetic）的決策程序

計算葛洛拿基底（英语：Gröbner basis）（在最差狀況^[12]）

實封閉體的量詞消去至少耗費雙重指數時間，^[13]而且可以在這樣的時間內完成。^[14]

参见

L-notation

游戏复杂度

計算複雜性理論

參考資料

^ Mehlhorn, Kurt; Naher, Stefan. Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 1990, 35 (4): 183. doi:10.1016/0020-0190(90)90022-P.

^ ^2.0^2.1 Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity (Berlin, New York: Springer-Verlag). 1993, 3 (4): 307–318. doi:10.1007/BF01275486.

^ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. Efficient Matrix Chain Ordering in Polylog Time. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics). 1998, 27 (2): 466–490. ISSN 1095-7111. doi:10.1137/S0097539794270698.

^ Kumar, Ravi; Rubinfeld, Ronitt. Sublinear time algorithms (PDF). SIGACT News. 2003, 34 (4): 57–67.

^ Aaronson, Scott. A not-quite-exponential dilemma. Shtetl-Optimized. 5 April 2009 [2 December 2009].

^ Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time

^ Moser, P. Baire's Categories on Small Complexity Classes. Lecture Notes in Computer Science (Berlin, New York: Springer-Verlag). 2003: 333–342. ISSN 0302-9743.

^ Miltersen, P.B. DERANDOMIZING COMPLEXITY CLASSES. Handbook of Randomized Computing (Kluwer Academic Pub). 2001: 843.

^ 引用错误：没有为名为ETH的参考文献提供内容

^ Kuperberg, Greg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics). 2005, 35 (1): 188. ISSN 1095-7111. doi:10.1137/s0097539703436345.

^ Oded Regev. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. 2004. arXiv:quant-ph/0406151v1 [quant-ph].

^ Mayr,E. & Mayer,A.: The Complexity of the Word Problem for Commutative Semi-groups and
Polynomial Ideals. Adv. in Math. 46(1982) pp. 305-329

^ J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential.
J. Symbolic Comp. 5(1988) pp. 29-35.

^ G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic
Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture
Notes in Computer Science 33) pp. 134-183

[1] Mehlhorn, Kurt; Naher, Stefan. Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 1990, 35 (4): 183. doi:10.1016/0020-0190(90)90022-P.

[bpp-2] 2.0^2.1 Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity (Berlin, New York: Springer-Verlag). 1993, 3 (4): 307–318. doi:10.1007/BF01275486.

[3] Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. Efficient Matrix Chain Ordering in Polylog Time. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics). 1998, 27 (2): 466–490. ISSN 1095-7111. doi:10.1137/S0097539794270698.

[4] Kumar, Ravi; Rubinfeld, Ronitt. Sublinear time algorithms (PDF). SIGACT News. 2003, 34 (4): 57–67.

[5] Aaronson, Scott. A not-quite-exponential dilemma. Shtetl-Optimized. 5 April 2009 [2 December 2009].

[6] Complexity Zoo: Class SUBEXP: Deterministic Subexponential-Time

[7] Moser, P. Baire's Categories on Small Complexity Classes. Lecture Notes in Computer Science (Berlin, New York: Springer-Verlag). 2003: 333–342. ISSN 0302-9743.

[8] Miltersen, P.B. DERANDOMIZING COMPLEXITY CLASSES. Handbook of Randomized Computing (Kluwer Academic Pub). 2001: 843.

[ETH-9] 引用错误：没有为名为ETH的参考文献提供内容

[10] Kuperberg, Greg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. SIAM Journal on Computing (Philadelphia: Society for Industrial and Applied Mathematics). 2005, 35 (1): 188. ISSN 1095-7111. doi:10.1137/s0097539703436345.

[11] Oded Regev. A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. 2004. arXiv:quant-ph/0406151v1 [quant-ph].

[12] Mayr,E. & Mayer,A.: The Complexity of the Word Problem for Commutative Semi-groups and
Polynomial Ideals. Adv. in Math. 46(1982) pp. 305-329

[13] J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential.
J. Symbolic Comp. 5(1988) pp. 29-35.

[14] G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic
Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture
Notes in Computer Science 33) pp. 134-183

搜尋此網誌