多项式时间复杂度和指数时间复杂度相差多少？

姜咏江

    如果以问题条件中对象数量n做为考察标准，随着n的增大，什么样的算法耗时增长速度快？这就是解题当中的时间复杂度问题。同一个问题，寻找耗时增长速度最慢的算法，无疑具有十分重要的意义。

    从数学知识知道，一次函数y=an+b随着n的变大，y的增长速度是不变的。还知道，k和c是大于1的正常整数时，y=a₀n⁰+ a₁n¹+ ...+a_kn^k和z=a₀c⁰+ a₁c¹+ ...+a_n-1c^n-1+a_nkⁿ比较，当n大到一定程度后，z的增长速度要比y快得多。y的表达式称为多项式型，z的表达式称为指数型。

    在计算机编程的算法中，如果对n的重复操作是可以用多项式型计算，避开指数型无疑是人们所希望的。在计算机中对n的重复操作是可以用多项式型计算就是多项式时间复杂度O(n^k)，用指数型计算的过程，就是指数时间复杂度O(cⁿ)。有许多实际问题，人们只是找到了指数型的算法，没有找到多项式型算法。对于后者能否找到多项式型算法的研究成为了世界难题，这就是P与NP问题。

    指数型最简单的是z=2ⁿ。我这里就举求集合子集的例子，来说明这两者的关系。

A. 求n个元素集合的全部子集数。

用元素添加法知，包括空集有C_n⁰+C_n¹+...+C_nⁿ=2ⁿ.

B. 求n个元素集合的不超过3个元素的子集数。

包括空集有C_n⁰+C_n¹+...+C_n³.

    由此可见多项式型和指数型之间的关系。多项式型的幂指数一定是不超过一个常数，这是二者区别的关键。在n增大的时侯，k是不能够也跟着n增大。很多人混淆了这种约定，因而陷入了无法自拔的境地。

    不可否认，多项式型在k相当大的时侯，随着n的增大，用计算机计算仍然耗时庞大，但与指数型最小的2ⁿ比起来也会是“小巫见大巫”。

证明C_n⁰+C_n¹+...+C_nⁿ=2ⁿ如下：

添右定理：n元集合用添右组合法得到全部非空子集为2ⁿ-1个。

    这个定理需要证明全部非空子集不少，且都不相同。

    这里用归纳法来证明。

设n=2，那么A=｛a₁,a₂｝，则A的转移组合得到的子集为｛a₁｝｛a₂｝｛a₁,a₂｝子集数为2²-1=3说明子集数正好且不重复。

设n=k时得到的子集｛a₁｝｛a₂｝...｛a₁,a₂,...,a_k｝满足条件子集数为2^k-1，且不重复。那么当n=k+1时，则除添加子集｛a_k+1｝之外，需要将n=k时得到2^k-1个子集全部添加a_k+1，形成的全部子集为

｛a₁｝｛a2｝...｛a_k｝｛a_k+1｝...｛a₁,a₂,...,a_k｝｛a₁,a₂,...,a_k,a_k+1｝

子集总数应为2^k-1+2^k=2×2^k-1=2^k+1-1,说明子集总数正确。

假设n=k+1时出现了重复子集，不妨设有子集B_i=B_j，i≠j，它们之中都包含a_k+1。那么将a_k+1从它们之中取出，则应有B_i｛a_k+1｝=B_j｛a_k+1｝，这与n=k时得到的子集不重复子集矛盾。故没有重复子集产生。

证毕。

2016-12-1