至于计算理论中的时间复杂度，简单来说，就是解决一个问题的某种算法，所需要的计算量，随着这个问题的规模增长而增长的速度。

　　这个概念，更多的被应用在信息学的计算机算法上。

　　在算法中，时间复杂度本质上，是指计算量增长的速度，而不是这个算法运行的时间。

　　自然的，对于同样的一个问题。

　　如果采用不同的算法，其时间复杂度也是不一定相同的。

　　而如果某个问题，能够找到的最优算法的时间复杂度，是n的多项式函数。

　　那么，这个问题就被称之为P类问题。

　　P也就是多项式的英文首字母。

　　此外，还有一些问题，无论其是否能够在多项式时间复杂度内求解，如果知道一个随便给出的可能解，能够在多项式时间复杂度内验证其是否为所求的解。

　　那么，这类问题就被称之为NP类问题。

　　至于为什么要研究一个问题，是否有多项式时间复杂度的算法。

　　则是因为，多项式时间复杂度的计算量增长速度，有些过于“快”了。

　　随着n的增大，其计算量远远小于O(2^n)、O(n！)、O(n^n)这些时间复杂度问题。

　　就好比那个很有名的大整数质因数分解问题。

　　给出一个2048位的二进制整数，要找出它的某个质因数。

　　一般来说，可能举全世界的计算能力，也需要上百年的时间，才能完成这个求解计算过程。

　　但是，如果知道某一个质数的话。

　　却可以用最普通的计算机，在几秒钟时间内，确定这个质数，是不是这个2048位二进制整数的一个因数。

　　而这，便是不同时间复杂度，在实际计算过程中的差别！

　　虽说有时候快了不好，可是在时间复杂度上，还是快一点比较有应用价值。

　　自然的，全部的P类问题，都属于NP类问题。

　　看着草稿纸上的内容，陈舟已经给出了这一显而易见的解释。

　　【一个问题可以在多项式时间复杂度内求解，当然可以在多项式时间复杂度内验证。】

　　只不过，写完这行文字的陈舟，又在下面加了一个“？”。

　　问号的旁边，陈舟写到：“反过来呢？”

　　没错，反过来呢？

　　一个可以在多项式时间复杂度内验证的问题，又是否能够通过多项式时间复杂度的算法求解呢？

　　陈舟暂时不知道。

　　所以，他在这个反问的话下面，划上了两道横线。

　　实际上，这个反问的话，其实也就是，是否全部的NP类问题，都属于P类问题呢？

　　而这，便是著名的NP完全问题，也就是“NP=P？”。

　　陈舟虽然还不知道这个问题的答案。

　　但是，已经不是信息学小白的陈舟，自然知道这个问题的答案，所具有的现实意义。

　　如果“NP=P？”没有了问号。

　　也就意味

　　请收藏：https://m.dm22.cc

（温馨提示：请关闭畅读或阅读模式，否则内容无法正常显示）