查看“︁时间复杂度”︁的源代码

{{multiple issues|
{{cleanup-jargon|time=2016-08-09T02:35:14+00:00}}
{{copyedit|time=2016-08-09T02:35:14+00:00}}
{{Expand English|date=2017年3月}}
}}
{{NoteTA
|G1=IT
}}
[[File:Comparison computational complexity.svg|缩略图|223x223像素|常见函数的时间复杂度]]
在[[计算机科学]]中，[[算法]]的'''时间复杂度'''（time complexity）是一个[[函数]]，它定性描述该算法的运行时间。这是一个代表算法输入值的[[字符串]]的长度的函数。时间复杂度常用[[大O符号]]表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是[[渐近分析|渐近]]的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 ''n'' （必須比 ''n<sub>0</sub>'' 大）的输入，它至多需要 {{nowrap|1=5''n''<sup>3</sup> + 3''n''}} 的时间运行完毕，那么它的渐近时间复杂度是 O(''n''<sup>3</sup>)。

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

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

== 常见时间复杂度列表 ==
以下表格統整了一些常用的時間複雜度類別。表中，poly(''x'')&nbsp;=&nbsp;''x''<sup>''O''(1)</sup>，也就是 ''x'' 的多項式。

{| class="wikitable"
|-
! 名称 !! [[复杂度类]] !! 运行时间（<math>T(n)</math>） !! 运行时间举例 !! 算法举例
|-
| [[常数时间]] || || <math>O(1)</math> || 10 || 判断一个二进制数的奇偶
|-
| 反[[阿克曼函数|阿克曼]]时间 || || <math>O(\alpha(n))</math> || || [[并查集]]的单个操作的[[平摊时间]]
|-
| [[迭代对数]]时间 || || <math>O(\log^{*}n)</math> || || [[圖著色問題|分散式圓環著色問題]]
|-
| 对数对数时间 || || <math>O(\log \log n)</math> || || 有界[[优先队列]]的单个操作<ref>{{Cite journal|first1=Kurt |last1=Mehlhorn |first2=Stefan |last2=Naher|year=1990|title=Bounded ordered dictionaries in O(log log N) time and O(n) space|journal=Information Processing Letters|doi=10.1016/0020-0190(90)90022-P|volume=35|issue=4|pages=183}}</ref>
|-
| 对数时间 || [[DLOGTIME]] || <math>O(\log n)</math> || <math>\log n</math>，<math>\log n^2</math>   || [[二分搜索]]
|-
| [[幂对数]]时间 || || <math>(\log n)^{O(1)}</math> || <math>(\log n)^2</math> ||
|-
| （小于1次）幂时间 || || <math>O(n^c)</math>，其中<math>0 < c < 1</math> || <math>n^{\frac{1}{2}}</math>，<math>n^{\frac{2}{3}}</math>|| [[K-d树]]的搜索操作
|-
| [[线性时间]] || || <math>O(n)</math> || <math>n</math> || 无序[[数组]]的搜索
|-
| 线性迭代对数时间 || || <math>O(n\log^{*}n)</math> || || {{link-en|萊姆德·賽德爾|Raimund Seidel}}的{{link-en|三角分割多边形|Polygon triangulation}}算法
|-
| 线性对数时间 || || <math>O(n\log n)</math> || <math>n\log n</math>，<math>\log n!</math> || 最快的[[比较排序]]
|-
| 二次时间 || ||  <math>O(n^2)</math>  || <math>n^2</math> || [[冒泡排序]]、[[插入排序]]
|-
| 三次时间 || || <math>O(n^3)</math>  || <math>n^3</math> || [[矩阵乘法]]的基本实现，计算{{link-en|部分相关性|Partial correlation}}
|-
| 多项式时间 || [[P (复杂性)|P]] ||  <math>2^{O(\log n)} = n^{O(1)}</math> ||  <math>n</math>，<math>n \log n</math>，<math>n^{10}</math> || [[线性规划]]中的{{link-en|卡馬卡演算法|Karmarkar's algorithm}}，[[AKS质数测试]]
|-
| 准多项式时间 || QP || <math>2^{(\log n)^{O(1)}}</math> || <math>n^{\log \log n}</math>，<math>n^{\log n}</math> |
|关于[[有向图|有向]]{{link-en|斯坦纳树问题|Steiner tree problem}}最著名的<math>O(\log^2 n)</math>[[近似算法]]
|-
| 次指数时间（第一定义）|| [[SUBEXP]] || <math>O(2^{n^{\epsilon}})</math>，对任意的ε > 0 || <math>O(2^{(\log n)^{\log \log n}})</math> || 假設複雜性理論推測，[[BPP (複雜度)|BPP]] 包含在 SUBEXP 中。<ref name="bpp" />
|-
| 次指数时间（第二定义） || || 2<sup>''o''(''n''）</sup> || 2<sup>''n''<sup>1/3</sup></sup> || 用於[[整數分解]]與{{link-en|圖形同構問題|Graph isomorphism problem}}的著名演算法 
|-
| [[指数时间]] || [[E (complexity)|E]] || 2<sup>''O''(''n'')</sup> || 1.1<sup>''n''</sup>, 10<sup>''n''</sup> || 使用[[动态规划]]解决[[旅行推销员问题]]
|-
| 阶乘时间 || || ''O''(''n''!) || ''n''! || 通过[[暴力搜索]]解决旅行推销员问题
|-
| [[指数时间]] || [[EXPTIME]] || 2<sup>poly(''n'')</sup> || 2<sup>''n''</sup>, 2<sup>''n''<sup>2</sup></sup> ||
|-
| 双重指数时间 || [[2-EXPTIME]] || 2<sup>2<sup>poly(''n'')</sup></sup> || 2<sup>2<sup>''n''</sup></sup> || 在{{link-en|預膨脹算術|Presburger arithmetic}}中決定一個給定描述的真實性 
|}

==常数时间==
{{Main|常数时间}}
若对于一个算法，<math>T(n)</math>的上界与输入大小无关，则称其具有'''常数时间'''，记作<math>O(1)</math>时间。一个例子是访问[[数组]]中的单个元素，因为访问它只需要一条[[指令]]。但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，或称<math>O(n)</math>时间。但如果预先知道元素的数量并假设数量保持不变，则该操作也可被称为具有常数时间。

虽然被称为「常数时间」，运行时间本身不须与问题规模无关，但它的'''上界'''必须是与问题规模无关的确定值。举例，「如果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

如果<math>T(n) = O(c)</math>，其中<math>c</math>是一个常数，这记法等价于标准记法<math>T(n) = O(1)</math>。

==对数时间==
若算法的''T''(''n'') = '''O(log ''n'')'''，则称其具有'''对数时间'''。计算机使用[[二进制]]的记数系统，[[对数]]常常以2为底（即log<sub>2</sub> ''n''，有时写作lg ''n''）。然而，由对数的[[换底公式]]，log<sub>a</sub> ''n''和log<sub>b</sub> ''n''只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作O（log ''n''），而不论对数的底是多少，是对数时间算法的标准记法。

常见的具有对数时间的算法有[[二叉树]]的相关操作和[[二分搜索]]。

对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。

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

<syntaxhighlight lang="c++" line="1">
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;
}
</syntaxhighlight>

==幂对数时间==
对于某个常数''k''，若算法的''T''(''n'') = O((log ''n'')<sup>''k''</sup>)，则称其具有'''幂对数时间'''。例如，矩阵链排序可以通过一个[[PRAM模型]].<ref>{{Cite journal| last1=Bradford | first1=Phillip G. | last2=Rawlins | first2=Gregory J. E. | last3=Shannon | first3=Gregory E. | title=Efficient Matrix Chain Ordering in Polylog Time | publisher=[[Society for Industrial and Applied Mathematics]] | location=Philadelphia | year=1998 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=27 | issue=2 | pages=466–490 | doi=10.1137/S0097539794270698}}</ref>被在幂对数时间内解决。

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

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

「次线性时间演算法」通常指那些不符合前一段的描述的演算法。它们通常运行于传统电脑架構系列并且不容许任何对输入的事先假设。<ref>{{Cite journal
 | last1 = Kumar
 | first1 = Ravi
 | last2 = Rubinfeld
 | first2 = Ronitt
 | title = Sublinear time algorithms
 | journal = SIGACT News
 | volume = 34
 | issue = 4
 | pages = 57–67
 | url = http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf
 | year = 2003
 | access-date = 2013-05-01
 | archive-date = 2016-03-03
 | archive-url = https://web.archive.org/web/20160303181704/http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf
 | dead-url = no
 }}</ref>但是它们可以是[[随机化算法]]，而且必须是真随机算法除了特殊情况。

==线性时间==
如果一个算法的时间复杂度为O(''n'')，则称这个算法具有线性时间，或'''O(''n'')'''时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。这个描述是稍微不准确的，因为运行时间可能显著偏离一个精确的比例，尤其是对于较小的n。

==线性对数（准线性）时间==
若一个算法时间复杂度T(n) = O(nlog n)，则称这个算法具有线性对数时间。因此，从其表达式我们也可以看到，线性对数时间增长得比线性时间要快，但是对于任何含有n，且n的幂指数大于1的多项式时间来说，线性对数时间却增长得慢。

==多项式时间==

===强多项式时间与弱多项式时间===
一個演算法如果執行時間是 '''輸入數值的大小'''（而非僅僅是輸入長度）的多項式函數，則它運行於'''弱多項式時間'''。例:標準動態規劃求解「0-1 背包問題」。

如果一個演算法的時間複雜度'''僅依賴輸入的長度（bit 數）'''，且不受輸入數值大小影響，那麼它是'''強多項式時間'''。例: 高斯消去法，只依賴於資料長度，不依賴於數字大小。

{{Expand section}}

===复杂度类===

从[[多项式时间]]的概念出发，在[[计算复杂度理论]]中可以得到一些[[复杂度类]]。以下是一些重要的例子。

* '''[[P (复杂度)|P]]'''：包含可以使用[[确定型图灵机]]在多项式时间内解决的[[决定性问题]]。
* '''[[NP (复杂度)|NP]]'''：包含可以使用[[非确定型图灵机]]在多项式时间内解决的决定性问题。
* '''[[ZPP (复杂度)|ZPP]]'''：包含可以使用[[概率图灵机]]在多项式时间内零错误解决的决定性问题。
* '''[[RP (复杂度)|RP]]'''：包含可以使用概率图灵机在多项式时间内解决的决定性问题，但它给出的两种答案中（是或否）只有一种答案是一定正确的，另一种则有几率不正确。
* '''[[BPP (复杂度)|BPP]]'''：包含可以使用概率图灵机在多项式时间内解决的决定性问题，它给出的答案有错误的概率在某个小于0.5的常数之内。
* '''[[BQP (复杂度)|BQP]]'''：包含可以使用[[量子图灵机]]在多项式时间内解决的决定性问题，它给出的答案有错误的概率在某个小于0.5的常数之内。

在机器模型可变的情况下，[[P (复杂度)|P]]在确定性机器上是最小的时间复杂度类。例如，将单带图灵机换成[[多带图灵机]]可以使算法运行速度以二次阶提升，但所有具有多项式时间的算法依然会以多项式时间运行。一种特定的[[抽象机器]]会有自己特定的复杂度类分类。

==超越多项式时间==

如果一個算法的時間 ''T''(''n'') 沒有任何多項式上界，則稱這個算法具有'''超越多項式'''（superpolynomial）時間。在這種情況下，對於所有常數 ''c'' 我們都有 ''T''(''n'') = ω(''n''<sup>''c''</sup>)，其中 ''n'' 是輸入參數，通常是輸入的數據量（比特數）。指數時間顯然屬於超越多項式時間，但是有些算法僅僅是很弱的超越多項式算法。例如，{{Link-en|Adleman-Pomerance-Rumely 質數測試|Adleman–Pomerance–Rumely primality test}}對於 ''n'' 比特的輸入需要運行 ''n''<sup>O(log log ''n'')</sup> 時間；對於足夠大的 ''n''，這時間比任何多項式都快；但是輸入要大得不切實際，時間才能真正超過低階的多項式。

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

==次指數時間==
術語[[次指數時間]]用於表示某些演算法的運算時間可能比任何多項式增長得快，但仍明顯小於指數。在這種狀況下，具有次指數時間演算法的問題比那些僅具有指數演算法的問題更容易處理。“次指數”的確切定義並沒有得到普遍的認同，<ref>{{Cite web |url=http://scottaaronson.com/blog/?p=394 |title=A not-quite-exponential dilemma |author=Aaronson, Scott |date=5 April 2009 |work=Shtetl-Optimized |accessdate=2 December 2009 |archive-date=2019-05-25 |archive-url=https://web.archive.org/web/20190525112826/https://www.scottaaronson.com/blog/?p=394 |dead-url=no }}</ref>我們列出了以下兩個最廣泛使用的。

===第一定义===
如果一個問題解決的運算時間的對數值比任何多項式增長得慢，則可以稱其為次指數時間。更準確地說，如果對於每個 ε> 0，存在一個能於時間 O(2<sup>n<sup>ε</sup></sup>) 內解決問題的演算法，則該問題為次指數時間。所有這些問題的集合是複雜性SUBEXP，可以按照 [[DTIME]] 的方式定義如下。<ref name="bpp">{{Cite journal| last1=Babai | first1=László | author1-link = László Babai | last2=Fortnow | first2=Lance | author2-link = Lance Fortnow | last3=Nisan | first3=N. | author3-link = Noam Nisan | last4=Wigderson | first4=Avi | author4-link = Avi Wigderson | title=BPP has subexponential time simulations unless EXPTIME has publishable proofs | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1993 | journal=Computational Complexity | volume=3 | issue=4 | pages=307–318 | doi=10.1007/BF01275486}}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{Cite journal| last1=Moser | first1=P. | title=Baire's Categories on Small Complexity Classes | publisher=Springer-Verlag | location=Berlin, New York | year=2003 | journal=[[Lecture Notes in Computer Science]] | issn=0302-9743 | pages=333–342}}
</ref><ref>{{Cite journal| last1=Miltersen | first1=P.B. | title=DERANDOMIZING COMPLEXITY CLASSES | publisher=Kluwer Academic Pub | year=2001 | journal=Handbook of Randomized Computing | page=843}}</ref>

:<math>\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)</math>

===第二定义===
一些作者將次指數時間定義為 2<sup>o(''n'')</sup> 的運算時間。<ref name="ETH" /><ref>{{Cite journal| last1=Kuperberg | first1=Greg | title=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem | publisher=[[Society for Industrial and Applied Mathematics]] | location=Philadelphia | year=2005 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=35 | issue=1 | page=188 | doi=10.1137/s0097539703436345}}</ref><ref>{{cite arXiv|eprint=quant-ph/0406151v1|author1=Oded Regev|title=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|year=2004}}</ref>該定義允許比次指數時間的第一個定義更多的運算時間。這種次指數時間演算法的一個例子，是用於整數因式分解的最著名古典演算法——[[普通數域篩選法]]，其運算時間約為 <math>2^{\tilde{O}(n^{1/3})}</math>，其中輸入的長度為 ''n''。另一個例子是{{link-en|圖形同構問題|Graph isomorphism problem}}的最著名演算法，其運算時間為 <math>2^{O(\sqrt{n \log n})}</math>。

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

:<math>\text{EXP} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{n^c}\right)</math>

有時侯，指數時間用來指稱具有 ''T''(''n'') = 2<sup>O(''n'')</sup> 的演算法，其中指數最多為 ''n'' 的線性函數。這引起複雜性等級 '''[[E (複雜度)|E]]'''。
:<math>\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)</math>

==双重指数时间==
若 ''T''(''n'') 是以 2<sup>2<sup>poly(''n'')</sup></sup> 為上界，其中 poly(''n'') 是 ''n'' 的多項式，則演算法被稱為[[雙重指數函數|雙重指數]]時間。這種演算法屬於複雜性等級 [[2-EXPTIME]]。
:<math>\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}\left( 2^{2^{n^c}}\right)</math>

眾所周知的雙重指數時間演算法包括：
* {{link-en|預膨脹算術|Presburger arithmetic}}的決策程序
* 計算{{link-en|葛洛拿基底|Gröbner basis}}（在最差狀況<ref>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</ref>）
* [[實封閉體]]的[[量詞消去]]至少耗費雙重指數時間，<ref>J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential.
''J. Symbolic Comp.'' 5(1988) pp. 29-35.</ref>而且可以在這樣的時間內完成。<ref>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</ref>

==参见==
* [[L符號]]
*[[博弈复杂度]]
*[[計算複雜性理論]]
* [[零一律]]
* [[柯爾莫哥洛夫空間]]
* [[柯氏复杂性]]
* [[空间复杂度]]

==參考資料==
{{Reflist|colwidth=25em|refs=
<ref name="ETH">{{cite journal | last1 = Impagliazzo | first1 = Russell | author1-link = Russell Impagliazzo | last2 = Paturi | first2 = Ramamohan | doi = 10.1006/jcss.2000.1727 | issue = 2 | journal = [[Journal of Computer and System Sciences]] | mr = 1820597 | pages = 367–375 | title = On the complexity of {{mvar|k}}-SAT | url = https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf | volume = 62 | year = 2001 | doi-access = free | access-date = 2021-08-12 | archive-date = 2021-07-10 | archive-url = https://web.archive.org/web/20210710235917/https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf | dead-url = no }}</ref>
}}
{{Wikidata property|1=P3753|2=P3752|3=P3754}}
{{DEFAULTSORT:Time Complexity}}
[[Category:算法分析]]
[[Category:計算複雜性理論]]
[[Category:计算资源]]