指數時間

指數時間，計算機算法術語。在計算複雜度理論中，指數時間指的是一個問題求解所需要的計算時間m(n)，依輸入資料的大小n而呈指數成長（即輸入資料的數量依線性成長，所花的時間將會以指數成長）。

基本介紹

• 中文名：指數時間
• 學科：計算機

簡介

在計算複雜度理論中，指數時間指的是一個問題求解所需要的計算時間m(n)，依輸入數據的大小n而呈指數成長（即輸入數據的數量依線性成長，所花的時間將會以指數成長）。

表示

以數學術語來說，便是若存在 k > 1，則此m（n） = Θ(kn)且存在c使得m（n） = Ο（cn）

意義

計算機科學家認為多項式時間是快的，而其他類型的計算時間是慢的。指數時間因此被認為是慢的類型。有很多算法計算時間慢過多項式時間，因此被稱為超多項式時間，但又快過指數時間，也因此又被稱為次指數時間，它們也被認為是慢的算法。此類問題中最著名的便是整數分解。

計算時間

在計算複雜度理論中，計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題的計算資源。很多重要的複雜度類，都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵，但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明了。

最常用以度量計算時間的抽象機器就是圖靈機。任何抽象機器，只要擁有

1. 狀態控制能力與
   
2. 可記載狀態控制磁讀寫頭造成的計算時間的磁帶
   

便可稱做類圖靈機。

因此為各類的抽象模型，我們可以定義不同的計算資源：在一個確定型圖靈機上是確定型時間；在非確定型圖靈機是非確定型時間，量子圖靈機則是量子時間……等等。輸入資料的計算時間等同於此輸入的計算樹的深度。

計算時間滿足時間譜系理論，也就是說量級漸進大於的計算時間定可準許複雜度類更大的計算問題。

多項式時間

多項式時間（英語：Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。