形式陈述

对时间界 $t:\mathbb{N}\to \mathbb{N}$，$\mathrm{DTIME}(t(n))$ 是由确定性多带图灵机在每个长度 $n$ 输入上至多 $O(t(n))$ 步判定的语言类；通常假设 $t(n)\ge n$ 且时间可构造，以便层级定理成立。常数因子和合理机器模型的多项式模拟不会影响 $P=\bigcup _{k\ge 1}\mathrm{DTIME}(n^k)$ 等粗粒度类别，但会影响精细时间界。

直觉

可计算性只问能否最终完成，时间类进一步按最坏输入需要多少基本步分层。输入长度而非数值大小是资源变量。

例子与边界

比较排序在标准模型上需要 $\mathrm{\Omega }(n\log n)$ 次比较，归并排序属于 $\mathrm{DTIME}(n\log n)$ 的合适 RAM/TM 对应版本。写下全部输入至少要线性扫描，但某些模型允许不读完输入就决定特殊语言，因此下界前提要说明。Big-O 类吸收常数，却不能把 $n^2$ 与 $2^n$ 混为一类。平均运行时间、期望运行时间和摊还时间不是 DTIME 定义中的最坏确定性时间。

推论与应用

DTIME 构成 P、EXP 与时间层级的基本记号，使算法上界、机器模拟开销和复杂性分离能够用同一资源函数表达。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。