-
指數時間
鎖定
指數時間,計算機算法術語。在計算複雜度理論中,指數時間指的是一個問題求解所需要的計算時間m(n),依輸入資料的大小n而呈指數成長(即輸入資料的數量依線性成長,所花的時間將會以指數成長)。
- 中文名
- 指數時間
- 學 科
- 計算機
指數時間簡介
指數時間表示
以數學術語來説,便是若存在 k > 1,則此m(n) = Θ(kn)且存在c使得m(n) = Ο(cn)
指數時間意義
計算機科學家認為多項式時間是快的,而其他類型的計算時間是慢的。指數時間因此被認為是慢的類型。有很多算法計算時間慢過多項式時間,因此被稱為超多項式時間,但又快過指數時間,也因此又被稱為次指數時間,它們也被認為是慢的算法。此類問題中最著名的便是整數分解。
指數時間計算時間
在計算複雜度理論中,計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題的計算資源。很多重要的複雜度類,都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵,但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明瞭。
最常用以度量計算時間的抽象機器就是圖靈機。任何抽象機器,只要擁有
- 狀態控制能力與
- 可記載狀態控制磁讀寫頭造成的計算時間的磁帶
便可稱做類圖靈機。
計算時間滿足時間譜系理論,也就是説量級漸進大於的計算時間定可准許複雜度類更大的計算問題。
[1]
指數時間多項式時間
多項式時間(英語:Polynomial time)在計算複雜度理論中,指的是一個問題的計算時間
不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類,此類包括可於此機器以多項式時間求解的問題。
[2]
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:6次歷史版本
- 最近更新: 好运伴伴666