指數(shù)時(shí)間，計(jì)算機(jī)算法術(shù)語。在計(jì)算復(fù)雜度理論中，指數(shù)時(shí)間指的是一個(gè)問題求解所需要的計(jì)算時(shí)間m(n)，依輸入資料的大小n而呈指數(shù)成長（即輸入資料的數(shù)量依線性成長，所花的時(shí)間將會(huì)以指數(shù)成長）。
簡介
在計(jì)算復(fù)雜度理論中，指數(shù)時(shí)間指的是一個(gè)問題求解所需要的計(jì)算時(shí)間m(n)，依輸入數(shù)據(jù)的大小n而呈指數(shù)成長（即輸入數(shù)據(jù)的數(shù)量依線性成長，所花的時(shí)間將會(huì)以指數(shù)成長）。
表示
以數(shù)學(xué)術(shù)語來說，便是若存在 k > 1，則此m（n） = Θ(kn)且存在c使得m（n） = Ο（cn）
意義
計(jì)算機(jī)科學(xué)家認(rèn)為多項(xiàng)式時(shí)間是快的，而其他類型的計(jì)算時(shí)間是慢的。指數(shù)時(shí)間因此被認(rèn)為是慢的類型。有很多算法計(jì)算時(shí)間慢過多項(xiàng)式時(shí)間，因此被稱為超多項(xiàng)式時(shí)間，但又快過指數(shù)時(shí)間，也因此又被稱為次指數(shù)時(shí)間，它們也被認(rèn)為是慢的算法。此類問題中最著名的便是整數(shù)分解。
計(jì)算時(shí)間
在計(jì)算復(fù)雜度理論中，計(jì)算時(shí)間是種計(jì)算抽象機(jī)器必須在某些特定計(jì)算中花費(fèi)的步驟數(shù)。任何抽象機(jī)器花費(fèi)的計(jì)算時(shí)間都是一種用以解決計(jì)算問題的計(jì)算資源。很多重要的復(fù)雜度類，都是依照在某些抽象機(jī)器上花費(fèi)特定量級(jí)的計(jì)算時(shí)間而定義的。這些時(shí)間復(fù)雜度類別共想許多特征，但它們的相互關(guān)系以及復(fù)雜度類對(duì)其他計(jì)算資源的影響仍未充份明了。
最常用以度量計(jì)算時(shí)間的抽象機(jī)器就是圖靈機(jī)。任何抽象機(jī)器，只要擁有
1.狀態(tài)控制能力與
2.可記載狀態(tài)控制磁讀寫頭造成的計(jì)算時(shí)間的磁帶
便可稱做類圖靈機(jī)。
因此為各類的抽象模型，我們可以定義不同的計(jì)算資源：在一個(gè)確定型圖靈機(jī)上是確定型時(shí)間；在非確定型圖靈機(jī)是非確定型時(shí)間，量子圖靈機(jī)則是量子時(shí)間……等等。輸入資料的計(jì)算時(shí)間等同于此輸入的計(jì)算樹的深度。
計(jì)算時(shí)間滿足時(shí)間譜系理論，也就是說量級(jí)漸進(jìn)大于的計(jì)算時(shí)間定可準(zhǔn)許復(fù)雜度類更大的計(jì)算問題。
多項(xiàng)式時(shí)間
多項(xiàng)式時(shí)間（英語：Polynomial 時(shí)間）在計(jì)算復(fù)雜度理論中，指的是一個(gè)問題的計(jì)算時(shí)間 不大于問題大小n的多項(xiàng)式倍數(shù)。任何抽象機(jī)器都擁有一復(fù)雜度類，此類包括可于此機(jī)器以多項(xiàng)式時(shí)間求解的問題。
參考資料 >