Time-Complexity

定义 Definition

time-complexity（更常写作 time complexity）指算法的运行时间随输入规模增长而变化的趋势，通常用“大 O 记号”等渐进符号来描述（如 **O(n)、O(n log n)、O(n)**）。它强调增长速度，而不依赖具体机器或实现细节。（该术语也常与 space complexity 并列讨论。）

发音 Pronunciation (IPA)

/tam kmplksti/

例句 Examples

Sorting this list has time-complexity of O(n log n).
给这个列表排序的时间复杂度是 O(n log n)。

Although the algorithm seems simple, its worst-case time-complexity grows exponentially, making it impractical for large inputs.
虽然这个算法看起来很简单，但它在最坏情况下的时间复杂度呈指数增长，导致在大规模输入时并不实用。

词源 Etymology

time（时间）来自古英语 tīma，表示“时间、时刻”；complexity（复杂性）源自拉丁语 complexus（“缠绕在一起的、综合的”），经法语进入英语。组合成 time complexity 后，在计算机科学语境中专指“随输入规模变化的时间增长复杂程度”，并逐渐形成标准术语。

相关词 Related Words

• Algorithm
• Big-O
• Complexity
• Efficiency
• Runtime
• Space-Complexity
• Worst-Case
• Asymptotic

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）中大量使用并系统讲解时间复杂度与渐进分析。
• The Art of Computer Programming（Donald E. Knuth，《计算机程序设计艺术》）在算法分析章节中频繁讨论运行时间与复杂度。
• Algorithms（Robert Sedgewick & Kevin Wayne，《算法》）在排序、查找、图算法等章节中反复使用“time complexity / running time”的概念。