时间复杂度

在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大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 的多项式。

名称	复杂度类	运行时间（${\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)}$		莱姆德·赛德尔（英语：Raimund Seidel）的三角分割多边形（英语：Polygon triangulation）算法
线性对数时间		${\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}}$	矩阵乘法的基本实现，计算部分相关性（英语：Partial correlation）
多项式时间	P	${\displaystyle 2^{O(\log n)}=n^{O(1)}}$	${\displaystyle n}$，${\displaystyle n\log n}$，${\displaystyle n^{10}}$	线性规划中的卡马卡算法（英语：Karmarkar's algorithm），AKS质数测试
准多项式时间	QP	${\displaystyle 2^{(\log n)^{O(1)}}}$		关于有向斯坦纳树问题（英语：Steiner tree problem）最著名的${\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	用于整数分解与图形同构问题（英语：Graph isomorphism problem）的著名算法
指数时间	E	2O(n)	1.1n, 10n	使用动态规划解决旅行推销员问题
阶乘时间		O(n!)	n!	通过暴力搜索解决旅行推销员问题
指数时间	EXPTIME	2poly(n)	2n, 2n2
双重指数时间	2-EXPTIME	22poly(n)	22n	在预膨胀算术（英语：Presburger arithmetic）中决定一个给定描述的真实性

常数时间

主条目：常数时间

若对于一个算法，${\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），而不论对数的底是多少，是对数时间算法的标准记法。

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

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

快速幂 就是一个经典例子。要计算n次方只需要O(log n)的时间。

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;
}

幂对数时间

对于某个常数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行列式计算那样）、非古典处理（如同葛罗佛搜索那样），又或者选择性地对有保证的输入结构作出假设（如幂对数时间的二分查找）。不过，一些情况，例如在头 log(n) 比特中每个字符串有一个比特作为索引的字符串组就可能依赖于输入的每个比特，但又符合次线性时间的条件。

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

线性时间

如果一个算法的时间复杂度为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) = ω(n^c)，其中 n 是输入参数，通常是输入的数据量（比特数）。指数时间显然属于超越多项式时间，但是有些算法仅仅是很弱的超越多项式算法。例如，Adleman-Pomerance-Rumely 质数测试（英语：Adleman–Pomerance–Rumely primality test）对于 n 比特的输入需要运行 n^{O(log log n)} 时间；对于足够大的 n，这时间比任何多项式都快；但是输入要大得不切实际，时间才能真正超过低端的多项式。

准多项式时间

准多项式时间算法是运算慢于多项式时间的算法，但不会像指数时间那么慢。对一些固定的 ${\displaystyle c>0}$，准多项式时间算法的最坏情况运行时间是 ${\displaystyle 2^{O((\log n)^{c})}}$。如果准多项式时间算法定义中的常量“c”等于1，则得到多项式时间算法；如果小于1，则得到一个次线性时间算法。

次指数时间

术语次指数时间用于表示某些算法的运算时间可能比任何多项式增长得快，但仍明显小于指数。在这种状况下，具有次指数时间算法的问题比那些仅具有指数算法的问题更容易处理。“次指数”的确切定义并没有得到普遍的认同，^[5]我们列出了以下两个最广泛使用的。

第一定义

如果一个问题解决的运算时间的对数值比任何多项式增长得慢，则可以称其为次指数时间。更准确地说，如果对于每个 ε> 0，存在一个能于时间 O(2^nε) 内解决问题的算法，则该问题为次指数时间。所有这些问题的集合是复杂性SUBEXP，可以按照 DTIME 的方式定义如下。^[2][6][7][8]

${\displaystyle {\text{SUBEXP}}=\bigcap _{\varepsilon >0}{\text{DTIME}}\left(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 {n\log n}})}}$。

指数时间

若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)}$

众所周知的双重指数时间算法包括：

• 预膨胀算术（英语：Presburger arithmetic）的决策程序
• 计算葛洛拿基底（英语：Gröbner basis）（在最差状况^[12]）
• 实封闭体的量词消去至少耗费双重指数时间，^[13]而且可以在这样的时间内完成。^[14]

参见

• L符号
• 博弈复杂度
• 计算复杂性理论
• 零一律
• 柯尔莫哥洛夫空间
• 柯氏复杂性
• 空间复杂度