时间复杂度

阐述

根据分析的输入不同，可以分为两种情况：

• 最差情况分析：特定长度输入中运行时间最长的
• 平均情况分析：特定长度输入的运行时间的平均

时间复杂度通常用渐近分析表达。

时间复杂度可以归为时间复杂度类以描述一组类似的问题。

确定性 Turing 机

设 $M$ 是一个确定性的 Turing 机且对所有输入停机，则它的时间复杂度是函数 $f:\mathbb N\to\mathbb N$，其中 $f(n)$ 是输入长度为 $n$ 时 $M$ 使用的步数。等价的表述为：

• $M$ 在 $f(n)$ 时间内运行
• $M$ 是一个 $f(n)$ 时间的 Turing 机

非确定性 Turing 机

设 $M$ 是一个非确定性的 Turing 机且对所有输入停机，则它的时间复杂度是函数 $f:\mathbb N\to\mathbb N$，其中 $f(n)$ 是输入长度为 $n$ 时 $M$ 在所有分支上使用的最大步数。

实例

性质

相关内容

计算模型的选取对时间复杂度的影响

对大多数确定性计算模型来说它们的区别不大。

单纸带和多纸带 Turing 机的联系

设函数 $t(n)\ge n$，则每个在 $t(n)$ 时间内运行的多纸带 Turing 机都有一个等价的在 $O(t^2(n))$ 时间内运行的单纸带 Turing 机。

确定性和非确定性 Turing 机的联系

设函数 $t(n)\ge n$，则每个在 $t(n)$ 时间内运行的非确定性 Turing 机都有一个等价的在 $2^{O(t(n))}$ 时间内运行的单纸带 Turing 机。

确定性计算模型的多项式等价性

所有合乎情理的确定性计算模型都可以在不超过多项式时间增长的代价下互相模拟。

参考文献