Polynomial-Time

Definition / 定义

polynomial-time（多项式时间）：指一个算法的运行时间可以用输入规模 \(n\) 的某个多项式来上界表示（如 \(O(n)\)、\(O(n^2)\)、\(O(n^3)\) 等）。在计算机科学中，通常把多项式时间可解视为“可高效计算/可行（tractable）”的一个重要标准。（在复杂性理论里常与 P 类问题相关。）

Pronunciation / 发音（IPA）

/plinomil tam/（美式常见）

Examples / 例句

Many sorting algorithms run in polynomial time.
许多排序算法都能在多项式时间内运行。

Although the search space is huge, the problem can still be solved in polynomial time using dynamic programming.
尽管搜索空间很大，这个问题仍然可以用动态规划在多项式时间内解决。

Etymology / 词源

polynomial 来自 *poly-*（“多、许多”）与 -nomial（与“项/名称/符号”相关的构词成分），在数学中表示“由若干项组成的代数表达式（多项式）”。polynomial-time 则把这一数学概念借用到算法分析中：用“多项式函数”来刻画运行时间随输入规模增长的速度，强调其增长相对可控；与之相对的是 exponential-time（指数时间），增长更快，通常被视为不够高效。

Related Words / 相关词汇

• Algorithm
• Complexity
• Polynomial
• Tractable
• Efficient
• P
• NP
• Exponential-Time
• Reduction

Literary Works / 文献与著作中的用例

• Introduction to the Theory of Computation（Michael Sipser）：讨论 P、NP 等复杂性类别时频繁使用 “polynomial time”。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：以“多项式时间可解/可约”为核心术语。
• Computational Complexity（Christos H. Papadimitriou）：系统阐述多项式时间、归约与复杂性理论框架。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在算法分析章节中常以多项式时间作为效率衡量标准。