查看“︁指數時間”︁的源代码

{{noteTA
|G1=IT
}}
{{unreferenced|time=2013-08-13T13:58:40+00:00}}
在[[計算複雜度理論]]中，'''指數時間'''指的是一個問題求解所需要的[[計算時間]]''m''(''n'')，依輸入-{zh-hans:数据;zh-hant:資料}-的大小<math>n</math>而呈[[指數]]成長（即輸入-{zh-hans:数据;zh-hant:資料}-的數量依[[線性]]成長，所花的時間將會以指數成長）。

以數學術語來說，便是若存在 ''k'' > 1，則此''m''（''n''） = [[大Θ符號|Θ(''k''<sup>''n''</sup>)]]且存在''c''使得''m''（''n''） = [[大O符號|Ο（''c''<sup>''n''</sup>）]]

-{zh-hans:计算机科学家;zh-hant:資訊科學家}-認為[[多項式時間]]是'''快'''的，而其他類型的計算時間是'''慢'''的。指數時間因此被認為是慢的類型。有很多演算法計算時間慢過多項式時間，因此被稱為'''超多項式時間'''，但又快過指數時間，也因此又被稱為'''次指數時間'''，它們也被認為是慢的演算法。此類問題中最著名的便是[[整數分解]]。

== 參閱 ==
* [[計算複雜度理論]]
* [[多項式時間]]
* [[常數時間]]
* [[線性時間]]
* [[演算法]]
* [[大O符號]]

[[Category:計算複雜性理論]]
[[Category:指数]]

[[en:Exponential time]]
[[he:סיבוכיות זמן#זמן ריצה מעריכי]]