形式陈述

若机器 $M$ 对每个长度为 $n$ 的输入至多运行 $T(n)$ 步，则称其时间复杂度为 $O(T(n))$。通常取最坏情况，并用统一计算模型忽略常数级实现差异。

直觉

时间复杂度不预测某台机器的秒数，而是描述输入变大时工作量如何增长，便于比较算法的可扩展性。

例子与边界

顺序扫描长度 $n$ 的数组需 $O(n)$ 次检查，归并排序需 $O(n\log n)$ 时间。复杂度表达式隐藏常数和低阶项，小规模输入下未必更快。

推论与应用

多项式时间、指数时间以及 P、NP 等复杂度类都由时间资源界定义。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §1.2.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §7.1.