指数时间查看源代码讨论查看历史
| 指数时间 |
|
中文名 : 指数时间 |
指数时间，计算机算法术语。在计算复杂度理论中，指数时间指的是一个问题求解所需要的计算时间m(n)，依输入资料的大小n而呈指数成长(即输入资料的数量依线性成长，所花的时间将会以指数成长)。[1]
表示
以数学术语来说，便是若存在 k > 1，则此m(n) = Θ(kn)且存在c使得m(n) = Ο(cn)
意义
资讯科学家认为多项式时间是快的，而其他类型的计算时间是慢的。指数时间因此被认为是慢的类型。有很多算法计算时间慢过多项式时间，因此被称为超多项式时间，但又快过指数时间，也因此又被称为次指数时间，它们也被认为是慢的算法。此类问题中最著名的便是整数分解。