计算理论导引 (8-时间复杂性)
时间复杂性
度量复杂性
在 最坏情况分析（worst-case analysis) 中，即这里考察的形式，考虑在某特定长度的所有输人上的最长运行时间。在 平均情况分析(average-case analysis) 中，考虑在某特定长度的所有输入上的运行时间的平均值。
令$M$是一个在所有输入上都停机的确定型图灵机。$M$的运行时间或者 时间复杂度，是一个函数$f:N→N$,其中$N$是非负整数集合，$f(n)$是M在所有长度为$n$的输入上运行时所经过的最大步数。若$f(n)$是$M$的运行时间，则称$M$在时间$f(n)$内运行，$M$是$f(n)$时间图灵机。通常使用$n$表示输入的长度。
大O和小o记法
渐近分析（asymptotic analysis)
函数$f(n)=6n^3+2n^2+20n+45$有四项，最髙次项是$6n^3$。忽略系数6,称$f$渐近地不大于$n^3$。表达这种关系的 渐近记法 或 大$O$记法 是$f(n)=O(n^3)$。
我们经常导出形如$n^c$的界，$c$是大于0的常数。这种界称为 多项式界（polynomial bound) 。形如$2^{(n^δ)}$的界，当$δ$是大于0的实数时，称为 指数界（exponentialbound) 。
与大$O$记法相伴的有小$o$记法。大$O$记法指一个函数渐近地不大于另一个函数。要说一个函数渐近地小于另一个函数，用小$o$记法。
分析算法
P类
一方面，问题的时间复杂性在确定型单带和多带图灵机上揚多是平方或多项式的差异；另一方面，在确定型和非确定型图灵机上，问题的时间复杂性最多是指数的差异。
多项式时间
所有合理的确定型计算模型都是 多项式等价的(polynomially equivalent) ，也就是说，它们中任何一个模型都可以模拟另一个，而运行时间只增长多项式倍。
$P$是确定型单带图灵机在多项式时间内可判定的语言类。在理论中，$P$类扮演核心的角色，它的重要性在于：
- 对于所有与确定型单带图灵机多项式等价的计算模型来说，$P$是不变的。
- $P$大致对应于在计算机上实际可解的那一类问题。
第1条表明，在数学上，$P$是一个稳健的类，它不受所采用的具体计算模型的影响。
第2条表明，从实用的观点看，$P$是恰当的。当一个问题在$P$中的时候，就有办法在时间$n^k(k是常数)$内求解它。
P中的问题举例
每一个上下文无关语言都是P的成员。
NP类
许多问题可以避免蛮力搜索而获得多项式时间解法。但是，在某些其他问题中，包括许多有趣而有用的问题，避免蛮力搜索的努力还没有成功，求解它们的多项式时间算法还没有找到。
$NP$即 非确定型多项式时间（nondeterministic polynomial time)，来源于使用非确定型多项式时间图灵机的另一特征。在NP中的问题有时被称为NP问题。
一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定。
P与NP问题
P=成员资格可以快速地 判定 的语言类。
NP=成员资格可以快速地 验证 的语言类。
P=NP是否成立的问题是理论计算机科学和当代数学中最大的悬而未决的问题之一。如果这两个类相等，那么所有多项式可验E的问题都将是多项式可判定的。大多数研究者相信这两个类是不相等的，因为人们已经投人了大量的精力为NP中的某些问题寻找多项式时间算法，但没人取得成功。研究者还试图证明这两个类是不相等的，但是这要求证明不存在快速算法来代替蛮力搜索。目前科学研究还无法做到这一步。
NP完全性
在P与NP问题上的一个重大进展是在20世纪70年代初由斯蒂芬•库克(Stephen Cook)和列奥尼德•列文(Leonid Levin)完成的。他们发现 NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。这些问题称为 NP完全的（NP-complete) 。
在理论方面，试图证明P不等于NP的研究者可以把注意力集中到一个NP完全问题上。如果NP中的某个问题需要多于多项式时间，那么NP完全问题也一定如此。而且，试图证明P等于NP的研究者只霈为一个NP完全问题找到多项式时间算法就可以达到目的了。
在实践方面，NP完全性现象可以防止为某一具体问题浪费时间，寻找本不存在的多项式时间算法。虽然，可能缺乏足够的数学依据来证明该问题在多项式时间内不可解，但是我们相信P不等于NP，所以，证明一个问题是NP完全的，就成为它的非多项式性的一个强有力的证据。
多项式时间可归约性
NP完全性的定义
转载请注明：转载自srzyhead的博客(https://srzyhead.github.io)
本文链接地址: 计算理论导引 (8-时间复杂性)
