Loading AI tools
来自维基百科,自由的百科全书
在計算複雜度理論中,指數時間指的是一個問題求解所需要的計算時間m(n),依輸入資料的大小而呈指數成長(即輸入資料的數量依線性成長,所花的時間將會以指數成長)。
此條目沒有列出任何參考或來源。 (2013年8月13日) |
以數學術語來說,便是若存在 k > 1,則此m(n) = Θ(kn)且存在c使得m(n) = Ο(cn)
資訊科學家認為多項式時間是快的,而其他類型的計算時間是慢的。指數時間因此被認為是慢的類型。有很多演算法計算時間慢過多項式時間,因此被稱為超多項式時間,但又快過指數時間,也因此又被稱為次指數時間,它們也被認為是慢的演算法。此類問題中最著名的便是整數分解。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.