Exponential Time

定义 Definition

“exponential time（指数时间）”指算法的运行时间随输入规模 \(n\) 按指数级增长，常见表示为 \(O(2^n)\)、\(O(c^n)\)（\(c>1\)）。这类算法在 \(n\) 稍大时就会变得非常慢，通常被认为在计算上“不够可行/难以处理”（intractable）。除算法复杂度外，也可泛指“耗时呈指数式上升”的过程。

发音 Pronunciation (IPA)

/ˌekspəˈnenʃəl taɪm/

例句 Examples

The naive solution takes exponential time.
这个朴素的解法需要指数时间。

Although the algorithm is correct, its exponential time complexity makes it impractical for large inputs, so we prefer a polynomial-time approximation.
虽然该算法是正确的，但它的指数时间复杂度使其在大规模输入下不现实，因此我们更倾向于选择多项式时间的近似算法。

词源 Etymology

exponential 来自“exponent（指数）”，与拉丁语 exponere（“展示、列出、提出”）相关，后来在数学中发展为“用指数表示的增长/变化”。exponential time 作为计算机科学术语，源于对算法运行时间随输入规模增长方式的分析，用来强调“增长速度像指数函数一样快”。

相关词 Related Words

• Algorithm
• Big-O Notation
• Brute Force
• Complexity
• Intractable
• NP-Complete
• Polynomial Time
• Time Complexity

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Thomas H. Cormen 等，常称 CLRS）——讨论时间复杂度分类时常与 polynomial time 对比提及。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Michael R. Garey & David S. Johnson）——在 NP 完全性与不可解性语境中频繁出现。
• The Art of Computer Programming（Donald E. Knuth）——分析算法效率时会涉及指数级时间行为与其影响。
• Computational Complexity: A Modern Approach（Sanjeev Arora & Boaz Barak）——在复杂性理论中系统讨论指数时间与相关复杂度类。