指數時間 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 指數時間.

指數時間

维基百科,自由的百科全书

此條目没有列出任何参考或来源。 (2013年8月13日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而移除。

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

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

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

參閱

{{bottomLinkPreText}} {{bottomLinkText}}
指數時間
Listen to this article