时间复杂性

时间复杂度(time complexity)简而言之就是对于某个问题计算机需要多少基础操作才能够解决。如果使用 $n$ 来代表问题的规模，则时间复杂度形式化表示为 $f (n)$

简化建模

首先全面分析哪些因素会影响一个问题的计算时间：

在给定问题算法和计算机配置的情况下，我们可以非常精确地表示出时间复杂度，例如通过精密的计算，可以得出归并排序的时间复杂度：

T (n) = c n + n lo g_{2} n

尽管这看着很简单，但是对于某些复杂的算法或者复杂的计算机体系，精确表达时间复杂度将会十分麻烦！并且这也偏离了复杂性理论的初衷：研究的是计算本身的性质，而非计算机配置或者算法问题。

渐进时间复杂度的目的就是为了忽略计算机配置对于计算时间的影响，简化问题的复杂性。

常用的渐进时间复杂度分析方法有：大 O 表示法和小 o 表示法。其中大 O 表示法表示时间复杂度不大于特定的上界函数，而小 o 表示法表示时间复杂度小于某个函数。

在一个固定的计算机配置上能够在多项式时间内解决的问题的集合。简便起见固定的计算机配置一般默认为单带图灵机。

注意

有定理单带图灵机和多带图灵机的时间复杂度差别只可能是多项式级别的，但是确定型和非确定型图灵机的差别可能是指数级的

表示一类能够在多项式时间内解决的问题，P 表示 polinomial。多项式时间复杂度一般作为问题可解性的标志，如果一个问题的时间复杂度是多项式级别的，那么从实践的角度来说，这个问题是可解的。

NP(nondeterministic polinomial)，非确定型多项式时间。NP 问题表示：不能在多项式时间内解决，但是可以在多项式时间内被验证的问题。

多项式时间能验证这个性质从哲学的角度来说暗示了问题可能是能够在多项式时间内解决的，尽管可能需要某些到现在还没有被发现的原理。

P 类与 NP 类是否相等是理论计算机科学和当代数学的一个悬而未决的问题：到现在还没有发现一个属于 NP 类而不属于 P 类的问题；但是对于一些 NP 问题投入大量研究却没有发现其多项式解法。

但是目前大部分学者都倾向于认为二者是不等的。

参考映射可归约性的定义，其中归约被定义为一个可计算函数。如果归约的计算时间复杂度是指数级别甚至更高的，那么虽然理论上可计算，但是从工程上来说是不可计算的。

而多项式时间可归约性就限制了归约的时间复杂度是多项式级别的。

NP 中的某些问题的复杂性与整个 NP 类相关联，这个性质被称为 NP 完全性。也就是说，如果一个 NP 完全问题存在多项式解法，那么整个 NP 类都存在多项式解法。

具体定义，如果一个问题满足以下两个条件，那么则称这个问题具有 NP 完全性：

这个现象的存在从侧面暗示了 NP 类与 P 类的不等价性，也是证明一个问题不存在多项式解法的有力证据。