时间复杂度

✍ dations ◷ 2025-04-02 12:42:07 #时间复杂度
在计算机科学中,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度(英语:Worst-case complexity),记为 T(n) ,定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度(英语:average-case complexity),通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类,举例来说,有着 T(n) = O(n) 的算法被称作“线性时间算法”;而 T(n) = O(Mn) 和 Mn= O(T(n)) ,其中 M ≥ n > 1 的算法被称作“指数时间算法”。以下表格统整了一些常用的时间复杂度类。表中,poly(x) = xO(1),也就是 x 的多项式。若对于一个算法, T ( n ) {displaystyle T(n)} 的上界与输入大小无关,则称其具有常数时间,记作 O ( 1 ) {displaystyle O(1)} 时间。一个例子是访问数组中的单个元素,因为访问它只需要一条指令。但是,找到无序数组中的最小元素则不是,因为这需要遍历所有元素来找出最小值。这是一项线性时间的操作,或称 O ( n ) {displaystyle O(n)} 时间。但如果预先知道元素的数量并假设数量保持不变,则该操作也可被称为具有常数时间。虽然被称为“常数时间”,运行时间本身并不必须与问题规模无关,但它的上界必须是与问题规模无关的确定值。举例,“如果a > b则交换a、b的值”这项操作,尽管具体时间会取决于条件“a > b”是否满足,但它依然是常数时间,因为存在一个常量t使得所需时间总不超过t。以下是一个常数时间的代码片段:如果 T ( n ) = O ( c ) {displaystyle T(n)=O(c)} ,其中 c {displaystyle c} 是一个常数,这记法等价于标准记法 T ( n ) = O ( 1 ) {displaystyle T(n)=O(1)} 。若算法的T(n) = O(log n),则称其具有对数时间。计算机使用二进制的记数系统,对数常常以2为底(即log2 n,有时写作lg n)。然而,由对数的换底公式,loga n和logb n只有一个常数因子不同,这个因子在大O记法中被丢弃。因此记作O(log n),而不论对数的底是多少,是对数时间算法的标准记法。常见的具有对数时间的算法有二叉树的相关操作和二分搜索。对数时间的算法是非常有效的,因为每增加一个输入,其所需要的额外计算时间会变小。递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O(log n)的时间因为每次输出之前我们都将字符串砍半。 这意味着,如果我们想增加输出的次数,我们需要将字符串长度加倍。对于某个常数k,若算法的T(n) = O((log n)k),则称其具有幂对数时间。例如,矩阵链排序可以通过一个PRAM模型.被在幂对数时间内解决。对于一个算法,若其符合T(n) = o(n),则其时间复杂度为次线性时间(sub-linear time或sublinear time)。实际上除了符合以上定义的算法,其他一些算法也拥有次线性时间的时间复杂度。例如有O(n½) 葛罗佛搜索(英语:Grover's algorithm)算法。常见的非合次线性时间算法都采用了诸如平行处理(就像NC1 matrix行列式计算那样)、非古典处理(英语:Quantum algorithm)(如同葛罗佛搜索那样),又或者选择性地对有保证的输入结构作出假设(如幂对数时间的二分搜索)。不过,一些情况,例如在头 log(n) 比特中每个字符串有一个比特作为索引的字符串组就可能依赖于输入的每个比特,但又符合次线性时间的条件。“次线性时间算法”通常指那些不符合前一段的描述的算法。它们通常运行于传统电脑架构系列并且不容许任何对输入的事先假设。但是它们可以是随机化算法,而且必须是真随机算法除了特殊情况。如果一个算法的时间复杂度为O(n),则称这个算法具有线性时间,或O(n)时间。非正式地说,这意味着对于足够大的输入,运行时间增加的大小与输入成线性关系。例如,一个计算列表所有元素的和的程序,需要的时间与列表的长度成正比。这个描述是稍微不准确的,因为运行时间可能显著偏离一个精确的比例,尤其是对于较小的n。若一个算法时间复杂度T(n) = O(nlog n),则称这个算法具有线性对数时间。因此,从其表达式我们也可以看到,线性对数时间增长得比线性时间要快,但是对于任何含有n,且n的幂指数大于1的多项式时间来说,线性对数时间却增长得慢。从多项式时间的概念出发,在计算复杂度理论中可以得到一些复杂度类。以下是一些重要的例子。在机器模型可变的情况下,P在确定性机器上是最小的时间复杂度类。例如,将单带图灵机换成多带图灵机可以使算法运行速度以二次阶提升,但所有具有多项式时间的算法依然会以多项式时间运行。一种特定的抽象机器会有自己特定的复杂度类分类。如果一个算法的时间 T(n) 没有任何多项式上界,则称这个算法具有超越多项式(superpolynomial)时间。在这种情况下,对于所有常量 c 我们都有 T(n) = ω(nc),其中 n 是输入参数,通常是输入的数据量(比特数)。指数时间显然属于超越多项式时间,但是有些算法仅仅是很弱的超越多项式算法。例如,Adleman-Pomerance-Rumely 质数测试(英语:Adleman–Pomerance–Rumely primality test)对于 n 比特的输入需要运行 nO(log log n) 时间;对于足够大的 n,这时间比任何多项式都快;但是输入要大得不切实际,时间才能真正超过低端的多项式。准多项式时间算法是运算慢于多项式时间的算法,但不会像指数时间那么慢。对一些固定的 c > 0 {displaystyle c>0} ,准多项式时间算法的最坏情况运行时间是 2 O ( ( log ⁡ n ) c ) {displaystyle 2^{O((log n)^{c})}} 。如果准多项式时间算法定义中的常量“c”等于1,则得到多项式时间算法;如果小于1,则得到一个次线性时间算法。术语次指数时间用于表示某些算法的运算时间可能比任何多项式增长得快,但仍明显小于指数。在这种状况下,具有次指数时间算法的问题比那些仅具有指数算法的问题更容易处理。“次指数”的确切定义并没有得到普遍的认同,我们列出了以下两个最广泛使用的。如果一个问题解决的运算时间的对数值比任何多项式增长得慢,则可以称其为次指数时间。更准确地说,如果对于每个 ε> 0,存在一个能于时间 O(2nε) 内解决问题的算法,则该问题为次指数时间。所有这些问题的集合是复杂性SUBEXP,可以按照 DTIME 的方式定义如下。一些作者将次指数时间定义为 2o(n) 的运算时间。该定义允许比次指数时间的第一个定义更多的运算时间。这种次指数时间算法的一个例子,是用于整数因式分解的最著名古典算法——普通数域筛选法,其运算时间约为 2 O ~ ( n 1 / 3 ) {displaystyle 2^{{tilde {O}}(n^{1/3})}} ,其中输入的长度为 n。另一个例子是图形同构问题(英语:Graph isomorphism problem)的最著名算法,其运算时间为 2 O ( n log ⁡ n ) {displaystyle 2^{O({sqrt {nlog n}})}} 。若T(n) 是以 2poly(n)为上界,其中 poly(n) 是 n 的多项式,则算法被称为指数时间。更正规的讲法是:若 T(n) 对某些常量 k是由 O(2nk) 所界定,则算法被称为指数时间。在确定性图灵机上认定为指数时间算法的问题,形成称为EXP的复杂性级别。有时侯,指数时间用来指称具有 T(n) = 2O(n) 的算法,其中指数最多为 n 的线性函数。这引起复杂性等级 E。若 T(n) 是以 22poly(n) 为上界,其中 poly(n) 是 n 的多项式,则算法被称为双重指数时间。这种算法属于复杂性等级 2-EXPTIME。众所周知的双重指数时间算法包括:

相关

  • 道尔顿原子质量单位(Atomic mass unit,amu),现称统一原子质量单位(Unified atomic mass unit,u)或道尔顿(dalton,Da),是用来衡量原子质量的单位,定义为静止未键结且处于基态碳12原子质量的1/12
  • 植物配种植物配种(英语:Plant breeding)是指透过改变植物的特征而产生所期望的特性的艺术和科学。植物配种现使用于为人类和动物改善产品中营养的品质。
  • 地屈孕酮地屈孕酮(英语:Dydrogesterone,商品名为Duphaston等)是一种黄体制剂药物,用于治疗一系列疾病,包括妊娠期的习惯性流产,黄体期缺陷(LPD)造成的功能失调性子宫出血和不孕,经痛,子宫内膜异
  • 大平原大平原(英语:Great Plains),多称北美大平原、北美大草原,是北美洲中部一块广袤的平原地区,大致位于密西西比河以西、落基山脉以东、格兰德河以北。自然植被以草为主。大平原东西长
  • 河姆渡文化河姆渡文化是分布于中国浙江杭州湾南岸平原地区至舟山群岛的新石器时代文化,其年代大约在距今6000年到7000年之前,因以浙江余姚河姆渡遗址发掘最早,故称作河姆渡文化。该文化最
  • 莱洛伊尔卢伊斯·弗德里科·莱洛伊尔(西班牙语:Luis Federico Leloir,法语名勒卢瓦尔,1906年9月6日-1987年12月2日),阿根廷籍法裔生物化学家。因研究了核苷酸糖及其在碳水化合物合成中的作
  • Vilsmeier-Haack反应维尔斯迈尔-哈克反应(Vilsmeier-Haack reaction)是指芳香化合物与二取代甲酰胺在三氯氧磷作用下,反应生成芳环上甲酰化产物。该反应只适于活泼底物,如苯酚、苯胺。维尔斯迈尔-哈克
  • 马克斯·恩斯特马克斯·恩斯特(德语:Max Ernst,1891年4月2日-1976年4月1日),德国画家、雕塑家、图像艺术家及诗人。作为一名多产的艺术家,恩斯特是达达运动和超现实主义运动的主要领军人物。马克
  • 大狐猴大狐猴(学名: Indri indri),是大狐猴属唯一的一种。大狐猴一般体长可达70厘米,体重可达13公斤,是一种树栖息的狐猴,是马达加斯加的特有种。孕期为5个月,五月或六月产仔,每胎一仔。食
  • 黄酮类黄酮类化合物(英语:Flavonoid,又称类黄酮)基于2-苯基色原酮-4-酮(2-苯基-1-苯并吡喃(英语:Benzopyran)-4-酮)骨架的黄酮类化合物,如右图所示,基本母核为2-苯基色原酮类化合物,现在则泛指