Time Complexity

释义 Definition

时间复杂度：衡量算法运行时间随输入规模 (n) 增长而变化的趋势，通常用 Big-O（大 O 记号）等渐近符号表示（如 (O(n))、(O(n\log n))、(O(n^2))）。它关注增长速度而非具体秒数。（该术语也常与最坏/平均/最好情况一起讨论。）

发音 Pronunciation (IPA)

/taɪm kəmˈplɛksɪti/

例句 Examples

The time complexity of this loop is O(n).
这个循环的时间复杂度是 O(n)。

Although quicksort is fast in practice, its worst-case time complexity is O(n²) without good pivot selection.
尽管快速排序在实践中通常很快，但如果主元选择不佳，其最坏时间复杂度会达到 O(n²)。

词源 Etymology

time 源自古英语 tīma（“时间、时机”）；complexity 源自拉丁语 complexus（“交织在一起的”），经法语进入英语，含“复杂程度”。组合成 time complexity，在计算机科学语境中指“与时间增长相关的复杂程度”，用于描述算法随输入变大时的运行时间增长规律。

相关词 Related Words

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

文学与经典著作 Literary Works

• Introduction to Algorithms（《算法导论》，Cormen / Leiserson / Rivest / Stein）：系统讲解时间复杂度与渐近分析。
• The Art of Computer Programming（《计算机程序设计艺术》，Donald E. Knuth）：大量使用并讨论复杂度与算法效率。
• Algorithms（《算法》，Robert Sedgewick & Kevin Wayne）：以实例介绍时间复杂度与性能分析。
• Computational Complexity: A Modern Approach（《计算复杂性：现代方法》，Arora & Barak）：将时间复杂度与复杂性理论中的类（如 P、NP）联系起来。