时间复杂度

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

名称	复杂度类	运行时间（${\displaystyle T(n)}$）	运行时间举例	算法举例
常数时间		${\displaystyle O(1)}$	10	判断一个二进制数的奇偶
反阿克曼时间		${\displaystyle O(\alpha (n))}$		并查集的单个操作的平摊时间
迭代对数时间		${\displaystyle O(\log ^{*}n)}$		分散式圓環著色問題
对数对数时间		${\displaystyle O(\log \log n)}$		有界优先队列的单个操作[1]
对数时间	DLOGTIME	${\displaystyle O(\log n)}$	${\displaystyle \log n}$，${\displaystyle \log n^{2}}$	二分搜索
幂对数时间		${\displaystyle (\log n)^{O(1)}}$	${\displaystyle (\log n)^{2}}$
（小于1次）幂时间		${\displaystyle O(n^{c})}$，其中${\displaystyle 0<c<1}$	${\displaystyle n^{\frac {1}{2}}}$，${\displaystyle n^{\frac {2}{3}}}$	K-d树的搜索操作
线性时间		${\displaystyle O(n)}$	${\displaystyle n}$	无序数组的搜索
线性迭代对数时间		${\displaystyle O(n\log ^{*}n)}$		萊姆德·賽德爾的三角分割多边形算法
线性对数时间		${\displaystyle O(n\log n)}$	${\displaystyle n\log n}$，${\displaystyle \log n!}$	最快的比较排序
二次时间		${\displaystyle O(n^{2})}$	${\displaystyle n^{2}}$	冒泡排序、插入排序
三次时间		${\displaystyle O(n^{3})}$	${\displaystyle n^{3}}$	矩阵乘法的基本实现，计算部分相关性
多项式时间	P	${\displaystyle 2^{O(\log n)}=n^{O(1)}}$	${\displaystyle n}$，${\displaystyle n\log n}$，${\displaystyle n^{10}}$	线性规划中的卡馬卡演算法，AKS质数测试
准多项式时间	QP	${\displaystyle 2^{(\log n)^{O(1)}}}$		关于有向斯坦纳树问题最著名的${\displaystyle O(\log ^{2}n)}$近似算法
次指数时间（第一定义）	SUBEXP	${\displaystyle O(2^{n^{\epsilon }})}$，对任意的ε > 0	${\displaystyle O(2^{(\log n)^{\log \log n}})}$	假設複雜性理論推測，BPP 包含在 SUBEXP 中。[2]
次指数时间（第二定义）		2o(n）	2n1/3	用於整數分解與圖形同構問題的著名演算法
指数时间	E	2O(n)	1.1n, 10n	使用动态规划解决旅行推销员问题
阶乘时间		O(n!)	n!	通过暴力搜索解决旅行推销员问题
指数时间	EXPTIME	2poly(n)	2n, 2n2
双重指数时间	2-EXPTIME	22poly(n)	22n	在預膨脹算術中決定一個給定描述的真實性

若对于一个算法，${\displaystyle T(n)}$的上界与输入大小无关，则称其具有常数时间，记作${\displaystyle O(1)}$时间。一个例子是访问数组中的单个元素，因为访问它只需要一条指令。但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，或称${\displaystyle 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

如果${\displaystyle T(n)=O(c)}$，其中${\displaystyle c}$是一个常数，这记法等价于标准记法${\displaystyle 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模型.[3]被在幂对数时间内解决。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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