指数时间

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

以数学术语来说,便是若存在 k > 1,则此mn) = Θ(kn)且存在c使得mn) = Ο(cn

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

参阅