在计算机科学中，算法的时间复杂度（time complexity）是一个函数，用于定性描述算法的运行时间随输入长度增长而变化的情况；这里的输入长度通常指表示输入值的字符串长度。时间复杂度常用大O符号表述，并忽略函数中的低阶项和首项系数。采用这种表述时，时间复杂度也可称为渐近时间复杂度，即考察输入规模趋近无穷时的情况。例如，如果一个算法对于任何大小为 n（且 n 大于某个 n0）的输入，至多需要 的时间运行完毕，则该算法的渐近时间复杂度是 O(n3)。
為了計算時間複雜度，通常會估計算法的操作單元數量，每個單元執行的時間都是相同的。因此，總運行時間和算法的操作單元數量最多相差一个常量系数。
相同大小的不同輸入值仍可能造成算法的執行時間不同，因此通常使用算法的，記為 *T(n)* ，定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是，通常有特別指定才會使用。時間複雜度可以用函數 T(n) 的自然特性加以分類，舉例來說，有著 T(n) = O(n) 的算法被稱作「線性時間算法」；而 T(n) = O(M*n) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被稱作「指數時間算法」。
常见时间复杂度列表
以下表格統整了一些常用的時間複雜度類別。表中，poly(x) = xO(1)，也就是 x 的多項式。
{| class="wikitable"
|-
! 名称 !! 复杂度类 !! 运行时间（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 || 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 中。被在幂对数时间内解决。
次线性时间
对于一个演算法，若其符合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 是輸入參數，通常是輸入的數據量（比特數）。指數時間顯然屬於超越多項式時間，但是有些算法僅僅是很弱的超越多項式算法。例如，對於 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)
眾所周知的雙重指數時間演算法包括：
- 的決策程序
- 計算（在最差狀況）
- 實封閉體的量詞消去至少耗費雙重指數時間，而且可以在這樣的時間內完成。
参见
- L符號
*博弈复杂度
*計算複雜性理論
- 零一律
- 柯爾莫哥洛夫空間
- 柯氏复杂性
- 空间复杂度
參考資料
评论 (0)