指数时间

指数时间，计算机算法术语。在计算复杂度理论中，指数时间指的是一个问题求解所需要的计算时间m(n)，依输入资料的大小n而呈指数成长（即输入资料的数量依线性成长，所花的时间将会以指数成长）。

简介在计算复杂度理论中，指数时间指的是一个问题求解所需要的计算时间m(n)，依输入数据的大小n而呈指数成长（即输入数据的数量依线性成长，所花的时间将会以指数成长）。

表示以数学术语来说，便是若存在 k > 1，则此m（n） = Θ(kn)且存在c使得m（n） = Ο（cn）

意义计算机科学家认为多项式时间是快的，而其他类型的计算时间是慢的。指数时间因此被认为是慢的类型。有很多算法计算时间慢过多项式时间，因此被称为超多项式时间，但又快过指数时间，也因此又被称为次指数时间，它们也被认为是慢的算法。此类问题中最著名的便是整数分解。

计算时间在计算复杂度理论中，计算时间是种计算抽象机器必须在某些特定计算中花费的步骤数。任何抽象机器花费的计算时间都是一种用以解决计算问题的计算资源。很多重要的复杂度类，都是依照在某些抽象机器上花费特定量级的计算时间而定义的。这些时间复杂度类别共想许多特征，但它们的相互关系以及复杂度类对其他计算资源的影响仍未充份明了。

最常用以度量计算时间的抽象机器就是图灵机。任何抽象机器，只要拥有

状态控制能力与

可记载状态控制磁读写头造成的计算时间的磁带

便可称做类图灵机。

因此为各类的抽象模型，我们可以定义不同的计算资源：在一个确定型图灵机上是确定型时间；在非确定型图灵机是非确定型时间，量子图灵机则是量子时间……等等。输入资料的计算时间等同于此输入的计算树的深度。

计算时间满足时间谱系理论，也就是说量级渐进大于的计算时间定可准许复杂度类更大的计算问题。1

多项式时间多项式时间（英语：Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。2

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学