Exponential-Time

释义 Definition

指数时间（复杂度）：指算法的运行时间随着输入规模 \(n\) 的增长，按指数函数增长（常见形式如 \(2^n\)、\(c^n\)）。在计算机科学中常用来描述非常不易在大规模输入上高效求解的问题与算法。（也常见写法：exponential time）

例句 Examples

The brute-force solution takes exponential-time in the worst case.
暴力解法在最坏情况下需要指数时间。

Although the algorithm is correct, its exponential-time behavior makes it impractical for large inputs, so researchers look for polynomial-time approximations or heuristic methods.
尽管该算法是正确的，但它的指数时间特性使其在大规模输入下不切实际，因此研究者会寻找多项式时间的近似算法或启发式方法。

发音 Pronunciation (IPA)

/kspnnl tam/

词源 Etymology

Exponential 源自拉丁语词根 exponere（“展示、放出”），在数学语境里发展出“按指数增长”的含义；time 指“时间”。两者合起来在算法分析中表示“运行时间按指数增长”，是复杂度理论中的常用术语。

相关词 Related Words

• Algorithm
• Brute-Force
• Complexity
• Exponential
• Intractable
• NP-Complete
• Polynomial-Time
• Tractable

文学与著作 Literary Works

• Introduction to the Theory of Computation（Michael Sipser）讨论可计算性与复杂度时频繁涉及指数时间算法与复杂度类。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）在NP完全性与“难解性”语境中常出现指数时间的讨论。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）在算法分析章节中会对比指数时间与多项式时间的可行性差异。