第五部分 计算复杂性导引
到现在，在我们讨论决策问题时，我们只考虑问题是否具有可解的性质。在现实生活中，用于解决问题的计算资源是有限的：可获得的时间和空间都是有限的。结果，一些可解的问题的中等规模的实例在实际中都变得很难以解决。在第5部分，我们考虑鉴别难解问题的方法，主要通过描述解决问题的一定规模的实例时，所需要的时间和内存的数量。虽然，强调的重点是运行时间，我们也给出有关空间的基本定义，并提到涉及空间的最基本的结果。
在第14章，我们首先引入涉及增长率的记号和术语，这允许我们在后面章节以合理的方式讨论象“多少时间？”这样的问题。我们把这些数量问题与我们特定的计算模型相联系，然后讨论一些基本的复杂类。这也是根据问题和语言内在的复杂性对它们分类的方法。
为了区分易解问题和难解问题（注意，前面我们讨论的可解问题和无解问题），正如我们将在第15章讨论的，常用的标准是在图林机上是多项式时间可解的。根据这个标准，许多问题是易解的，也有些问题是难解的。我们可以修改第12章的规约技术得到这两类问题的例子。也许更有趣的问题是根据这个标准，至今仍然无法判断的一些问题，没有人发现这些问题的多项式时间解决方法，但是也没有人能够证明不存在多项式时间解决方法。NP完全的概念就是接近这
个主题的一个方法。在第15章的最后两节，我们给出可满足问题的NP完全性的cook证明和一些通过多项式时间规约被证明是NP完全的组合问题的例子。
14 测度和复杂性分类
14.1 函数的增长率
计算问题的复杂性能够通过固定的计算模型来讨论，主要考虑为了解决这个问题，需要多少机器的资源（通常指时间和空间）。为了对两个问题内在复杂性进行有意义的比较，有必要考察一定范围内的实例的解决情况。如果我们把运行时间作为标准，比如，最常用的方法是比较两个运行时间的增长率，每个运行时间都看成是实例规模的函数。我们引入一些处理运行时间的数量的增长率的定义和记号。我们从一个比较4个简单函数的例子开始。
例子14.1 我们考虑函数
p1(n)=2n2
p2(n)=n2+3n+7
P3(n)=n3
q(n)=2n
表14.1显示了这4个函数对应部分变量取值n的各自的函数值，这些函数值很清楚显示了每个函数的增长趋势。对于比较小的值n，p2(n)的值远远大于p1(n)，但是当n=1000时，p2(n)中低阶的项3n+7变得相对可忽略了，而p1中的因子2几乎完全决定了p1和p2之间的差别。p3是更高阶的多项式，尽管没有额外的因子和低阶项，但是它的值的增长速度比前两个函数都要快很多。
    更惊人的增长趋势体现在第4个指数函数q上。我们再次看到对于最前面的几个小数值没有什么特别的地方，但是对于n=10之后的数值，它就比其他3个函数值都要大了，当n=1000时，p3(n)是1百万，而q(n)则是难以想象地大了。如果表中数据的单位是纳秒（nanosecond，又译毫微秒，一秒的10亿分之一），那么p3(1000)表示1秒，而q(1000)表示超过3*10282世纪。
加入表14.1
    表14.1展示了不同增长率的效果，p1和p2有不同的规模，主要是因为p1的因子2，但是它们的增长率是一致的。立方多项式的增长率更大一些，但是这三个多项式的增长率都远远小于指数函数。一旦我们有了能够精确描述增长率的定义，其中一个我们感兴趣的主要区别将是多项式增长率和指数增长率之间的区别。这个例子显示的许多明显的特征将体现在定义中。
    定义14.1 如果f,g: NN是部分函数，每个函数除了在有限个点外，其他值都是有定义的。如果存在常量C和n0，使得对于每个n>=n0，f(n)和g(n)都是有定义的，且f(n)<=Cg(n)，那么我们写
    f(n)=O(g(n))（或者简单地，    f=O(g)）
如果对于每个正常数C，存在一个常量n0，使得对于每个n>=n0，都有f(n)<=Cg(n)，那么我们写
    f(n)=o(g(n))（或者简单地，f=o(g)）
最后，如果f=O(g)且g=O(f)，则写成
    f=(g)
    语句f=O(g)，f=o(g)和f=(g)分别读着“f是g的大O”，“f是g的小o”和“f是g的大”。所有这些语句可以用比率f(n)/g(n)来重新描述，假设g(n)最终会大于0。说f=o(g)意味着当n趋于无穷大时，这个比率的极限为0，而f=O(g)表示这个极限是有界的，而f=(g)，如果两个函数都最终是非0的，则表示f/g和g/f的极限值都是有界的，即f/g的极限值介于两个固定的正数之间。如果f=O(g)不成立，则写成fO(g)，类似地，得到另外两个不成立的表示法。fO(g)意味着不存在常数C，使得对于所有的n的大值，f(n)<=Cg(n)，换句话说，比率f(n)/g(n)是无界的。
    一个语句，比如f=O(g)，描述了两个函数的关系，它不是等式，比如写成O(f)=g是没有意义的。这个记号的定义是很清楚的，但是更精确的写法是把O(g)看成一个集合，因此fO(g)，而不是f=O(g)（为了方便，我们不加区分地使用着两种表示法）。
    语句f=O(g)没有传达任何有关f和g的函数值的信息，它表示长远来看（当n足够大时），也许f不再比g的某个比例大，这个比例常量可能很大，以至f的实际值可能比g要大的多，但是f的增长率并不比g大。这个术语对于非降低的函数f和g更合适，至少最终是非降低的，而大多数我们感兴趣的函数都具备这个性质。如果f=(g)，则说f和g具备相同的增长率，正如我们已
经看到，它表示当n很大时，两个函数的值趋于一个恒定的比例。如果f=o(g)，那么f的增长率小于g，因为根据定义，当n很到时，f和g的比例比任何一个正常数都要小。注意在这里我们不关心当n要大到什么值是，上面的情况才发生。
    我们已经引入了一个与其他函数增长率相当（或小、或大）的函数的想法，有必要检验这些术语在语义上不会有误导，即这两个关系（大O和小o）满足绝大多数相应的数值关系的性质。根据定义很清楚，如果f=o(g)，那么f=O(g)，符合“小于”蕴涵“不大于”的语义。显然，我们还希望“大于”可以排除“不大于”的可能性，即如果f=o(g)，则gO(f)。这是容易检验的。定理14.1包含了这些关系的其他一些直观的性质。
    定理14.1 关系R1定义如下
    fR1g当且仅当f=O(g)
即函数f的增长率不大于g。R1满足自反性和传递性。
    关系R2定义如下
    fR2g当且仅当f=o(g)
即f的增长率小于g。R2满足传递性和反对称性（如果fR2g，则gR2f）。
    关系R3定义如下
    fR3g当且仅当f=(g)
即f和g的增长率相当。R3是一个等价关系。
    证明：我们只证明R1的性质，其他两个留作练习。关系R1的自反性是显然的，根据定义，只要选择常数C=1，n0=0就可以了。下面证明它的传递性。
    假设f=O(g)，且g=O(h)。那么存在常数C1, n1, C2, n2使得
    f(n)<=C1g(n), n>=n1
    g(n)<=C2h(h), n>=n2
    令n0=max(n1,n2)，那么当n>=n0，上面的两个不等式都成立，得到
    f(n)<=C1g(n)<=C1C2h(n)
取常数C=C1C2，因此f=O(h)。
    一个多项式函数要么是0，要么是下面的形式
    p(n)=
其中ak0。k是多项式的度（degree），容易发现如果的第一个系数ak>0，那么当n足够大时，p(n)>0。我们将对这类多项式感兴趣，而且如果ak<0，我们可以简单地把p(n)看成是未定义的函数。指数函数的形式如下
    q(n)=an
其中a是一个大于1的固定数值。如果多项式函数的系数或指数函数的底数a不是整数，我们可以忽略函数值的小数部分，从而得到一个整数函数。这两种情况都不会影响函数的增长率。
    基于例子    14.1，我们可能猜测任何一个平方多项式的增长率小于立方多项式，而且它们的增长率都小于指数函数。下面的定理概括了上面的猜测。
    定理14.2 令p是多项式函数
    p(n)=aknk+...+a1n+a0
其中k>=0，ak>1，令q是指数函数
    q(n)= an
其中a>1，则
    p(n)=(nk)，p=o(q)
    证明：首先我们证明p(n)=(nk)。我们可以写
=
我们能够发现n0，使得对于任意的n>=n0，下面k项的每一项
, ,..., , 字符串长度测量函数
都小于1/k。因此
    -1<<1
则
    0ak-1<ak+1
令C=ak+1，则符合O的定义，即p(n)=O(nk)。
    另一方面，可以类似证明nk=O(p(n))。选择n0，使得下面k项的每一项
    |ak-1/n|,...,|a0/nk|
当n>=n0，都小于或等于1/(2k)，因此
>=ak-1/2
即
    nk<=
现在为了证明p=o(q)，只需要说明nk=o(q(n))。因为
nk+1=(z(n))n
其中
    (z(n))n=e(k+1)(logn/n)
既然n趋于无穷大时，logn/n趋于0，z(n)趋于1，那么存在n0，使得当n>=n0，有
    nk+1=z(n)n<=an
因此
    nk<=an/n
这证明了nk=o(an)。
    根据例子14.1的表，容易发现多项式的度不同或指数函数的底数不同，增长的速度也不同。比如对于(1.01)n，n=1000时，它的值仅有20,959。然而它仍然是指数函数，只是需要稍大一点的数才能看到这个效果，当n=10,000时，(1.01)n>1043，而(10,000)3=1012。
14.2 图林机的时间和空间复杂性
我们选择的计算模型是图林机（有时为了方便，我们可能使用多个磁带或非确定的图林机），当一个图林机执行一个计算去回到一个判定问题的实例时，我们可以测量计算所需的时间（移动次数）和空间（磁带的格子数）。实例规模的最明显的测量标准是作为实例编码的输入字符串的长度，最常用的方法是考虑最坏的情况，即同样长度的输入字符串可能需要的最大时间和空间的开销。有了上面的说明，我们可以在一个普通的确定型图林机上定义时间和空间的复杂性。
定义14.2（图林机的时间和空间的复杂性）令T是一个图林机，T的时间复杂性是一个定义在自然数集上的函数T。对于一个自然数n，T(n)是在所有长度为n的输入字符串上引发的T的最多的移动次数。如果存在一个长度为n的输入字符串，使得T无限循环，那么T(n)无定义。
空间复杂性函数sT定义如下。如果没有长度为n的输入字符串导致T使用无限多的磁带格子，sT(n)是所有长度为n的输入字符串上引发的T的使用最多的格子数目（如果T是多个磁带的图林机，“磁带格子数目”的含义是单个磁带的最大格子数）。否则如果某个长度为n的输入字符串导致T无限循环，并且这个无限循环导致无限多的磁带格子被占用，那么sT(n)无定义。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。