NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 19 题

在下列关于算法复杂性的说法中，正确的有（ ）。

这题考算法复杂度与NP类概念辨析。拿到题先看A是否混淆‘理论次数’与‘实测时间’，再看D是否把NP整体当成NPC。核心是记住复杂度描述的是主要运算次数随规模n的变化规律，而NPC只是NP中最难的那部分，P≠NP至今未证。

最容易掉进A的坑，把时间复杂度当成某台机器上的实际运行秒数，其实它只跟输入规模n和运算次数有关，跟硬件无关；D也常错，把NP类整体当成NPC类，其实NP包含P类和NPC类，NPC是NP里最硬的那部分，不能把NPC的结论（无多项式算法）直接套到整个NP上。

这道题考查算法时间复杂度的定义、NPC问题的含义以及NP与NPC的区别。命题人喜欢在这里挖‘概念偷换’的坑，比如把理论上的运算次数偷换成具体机器的运行时间，或者把NP类整体当成NPC类来推论。

先说时间复杂度。它不是指算法在某台计算机上具体实现时的运行时间（那是实测值，受硬件、编译器、操作系统影响），而是指对于该算法的一种或几种主要运算，运算的次数与问题规模n之间的函数关系。所以A错，B对。

再看NP与NPC。NP类是指那些能在多项式时间内验证解的问题集合，它包含P类（本身就能多项式时间求解）和NPC类（NP中最难的那部分）。NPC问题的特点是：如果存在一个多项式时间算法能解决某个NPC问题，那么所有NP问题都能在多项式时间内解决，即P=NP；反之，若P≠NP，则NPC问题不存在多项式时间算法。但P≠NP至今未被证明，也未被否定，因此我们只能说‘NPC类目前没有已知多项式时间算法，但这一点尚未得到理论上的证实，也没有被否定’。所以C对。

D选项说‘一个问题如果是NP类的，与C有相同的结论’，这明显混淆了NP与NPC。NP类里有很多P类问题，它们显然存在多项式时间算法，不能说它们‘不存在多项式时间算法’。因此D错。

做题心法：看到‘时间复杂度’先想‘主要运算次数与n的函数关系’；看到‘NP’要立刻区分‘能验’和‘最难’，NPC才是那个‘最难’的子集。这样就不会把A、D这类陷阱当成正确答案了。

从考频看，计算机发展史相关题目在NOIP初赛中出现频率较高，2007-2020年间共考过29题，其中NOIP提高组初赛就占了15题，历年分布较均匀，2012年曾出现9题的小高峰。这类概念辨析题属于基础但易错考点，未来仍可能以类似形式出现，继续考察对复杂度定义和NP类关系的精准理解。暂无足够依据预测具体年份或题型变化，但掌握上述辨析逻辑足以应对同类题目。