时间复杂度 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 "n" （必须比 "n0" 大）的输入，它至多需要 5"n"3 + 3"n" 的时间运行完毕，那么它的渐近时间复杂度是 O("n"3)。 为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元执行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。 相同大小的不同输入值仍可能造成算法的执行时间不同，因此我们通常使用算法的，记为 "T"("n") ，定义为任何大小的输入 "n" 所需的最大执行时间。另一种较少使用的方法是，通常有特别指定才会使用。时间复杂度可以用函数 "T"("n") 的自然特性加以分类，举例来说，有著 "T"("n") = "O"("n") 的算法被称作「线性时间算法」；而 "T"("n") = "O"("M""n") 和 "M""n"= O("T"("n")) ，其中 "M" ≥ "n" > 1 的算法被称作「指数时间算法」。 常见时间复杂度列表. 以下表格统整了一些常用的时间复杂度类别。表中，poly("x") = "x""O"(1)，也就是 "x" 的多项式。 常数时间. 若对于一个算法，formula_1的上界与输入大小无关，则称其具有常数时间，记作formula_2时间。一个例子是访问数组中的单个元素，因为访问它只需要一条指令。但是，找到无序数组中的最小元素则不是，因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作，或称formula_3时间。但如果预先知道元素的数量并假设数量保持不变，则该操作也可被称为具有常数时间。 虽然被称为「常数时间」，运行时间本身不须与问题规模无关，但它的上界必须是与问题规模无关的确定值。举例，「如果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 如果formula_4，其中formula_5是一个常数，这记法等价于标准记法formula_6。 对数时间. 若算法的"T"("n") = O(log "n")，则称其具有对数时间。计算机使用二进制的记数系统，对数常常以2为底（即log2 "n"，有时写作lg "n"）。然而，由对数的换底公式，loga "n"和logb "n"只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作O（log "n"），而不论对数的底是多少，是对数时间算法的标准记法。 常见的具有对数时间的算法有二叉树的相关操作和二分搜索。 对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。 递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O（log n）的时间因为每次输出之前我们都将字符串砍半。 这意味着，如果我们想增加输出的次数，我们需要将字符串长度加倍。 // 递归输出一个字符串的右半部分 var right = function(str) var length = str.length; // 辅助函数 var help = function(index) // 递归情况：输出右半部分 if(index 0，存在一个能于时间 O(2nε) 内解决问题的演算法，则该问题为次指数时间。所有这些问题的集合是复杂性SUBEXP，可以按照 DTIME 的方式定义如下。 formula_9 第二定义. 一些作者将次指数时间定义为 2o("n") 的运算时间。该定义允许比次指数时间的第一个定义更多的运算时间。这种次指数时间演算法的一个例子，是用于整数因式分解的最著名古典演算法——普通数域筛选法，其运算时间约为 formula_10，其中输入的长度为 "n"。另一个例子是的最著名演算法，其运算时间为 formula_11。 指数时间. 若"T"("n") 是以 2poly("n")为上界，其中 poly("n") 是 "n" 的多项式，则演算法被称为指数时间。更正规的讲法是：若 "T"("n") 对某些常数 "k"是由 O(2"n""k") 所界定，则演算法被称为指数时间。在确定性图灵机上认定为指数时间演算法的问题，形成称为EXP的复杂性级别。 formula_12 有时侯，指数时间用来指称具有 "T"("n") = 2O("n") 的演算法，其中指数最多为 "n" 的线性函数。这引起复杂性等级 E。 formula_13 双重指数时间. 若 "T"("n") 是以 22poly("n") 为上界，其中 poly("n") 是 "n" 的多项式，则演算法被称为双重指数时间。这种演算法属于复杂性等级 2-EXPTIME。 formula_14 众所周知的双重指数时间演算法包括：