大千世界,问题千万. 世间的一切都可以是我们的问题:

1. 天上有没有神仙
2. 地下有没有地府
3. 明天会不会下雨
4. 考试会不会及格
5. 那个妹子会不会接受我
6. 这个数组的最大值是不是42
7. 那个数组的从小到大的排序结果是不是1,2,3,4,5

诸如此类的问题我们都可以称之为问题. 可以看出我们的问题都是有一个特定的问法

就是指某个事件/事物是否符合/满足一个特定的预期?

像这样的问题我们称之为决定性问题/是非问题,答案只有两种可能性,要么是真/是/true的,要么是假/非/false的

指时间复杂度用函数表示形如以下公式所表示:

$$an^x + bn^{x-1} + cn ^{x-2}... + z n + C$$

在这里定义

1. $a,b,c,...,z,C, x$都是常数, $x$是指数
2. $n$是自变量,是数据的规模

对于以上定义,如果一个算法的时间复杂度明确到具体的参数 $a,b,c,...,z,C,x$, 只要以这个形式表达出来,那么就可以说这个算法的时间复杂度取最高次项,可以写作 $$O(n^x)$$

对于任意一个算法,只要某个算法A的时间复杂度小于等于这个值,就可以称这个算法A的时间复杂度在多项式时间之内 例如快排$O(nlogn)$, 顶堆取极值$O(1)$, 遍历一个数组$O(n)$,统统都属于多项式时间之内这个定义.

复杂度分类是特指算法复杂度的分类,大体上分为两大类,一个是$x$,另一个$Nx$. 这里的x代表的是不同的复杂度,N代表的是非确定性, 例如P 和 NP, exp和Nexp, 甚至 fac和Nfac等等

在算法教学中,我们一般都是用P和NP作为举例,其他复杂度其实也是类似,只不过教学过程中不太用得到,因为复杂度实在是太高,人类比较难以想象,很难举出例子.甚至NP的例子在NPC的情况下就已经非常难以理解了,具体NPC是什么我们下面也会讲解.

1. $x$是指在$x$的时间复杂度内存在一个算法能够解决这个问题,具体我们会在下面用P来举例
2. $Nx$是指在$x$的时间复杂度内存在一个算法能够验证这个问题,具体我们也会在下面用NP来举例

下面我们以P作为例子来进行具体的讲解.

polynomial time, 指存在一个算法能在多项式时间之内解决 所谓的解决是指,对于一个问题的任何设置,总能在规定的时间范围内找到答案,在P问题的定义下当然就变成了在多项式时间内找到问题的解.

对于一个数组[3,1,2,5], 请问这个数组的最大值是否是$5$?

注意我们的题目全都是是非/决定性问题.
对于这个问题,我们只需要把数组进行遍历,每次记录当前已知的最大值$max$,如果遍历过程中发现当前元素比目前已知的最大值要大则更新当前最大值$max$.
非常容易看出,只需要$O(4)$(4为问题中数组的元素个数)的时间我们就能找到问题的解.对于这个问题,我们发现数组的最大值是$5$,正好符合题目中的预期,因此问题的结果为真/true

我们也可以延伸扩展这个问题到更加通用的一个问题,即: 给定一个长度为n数组A, 请问其中的最大值是否为$x$? 我们可以用同样的算法,对这个通用的问题进行解答,从而获得问题的真假性. 我们发现对于任意一个符合条件的这样的问题,我们都可以在$O(n)$时间内找到问题的解. 因此我们说,这样的问题可以在多项式时间内得到解决,因此这样的问题是属于P类问题.

事实上我们可以直接把这个问题归结为"在数组中找最大值"的问题这样更好理解,但由于要符合问题的通用性,我在这里并没有直接这么说.

对于一个连通图$G$,请问他的最小生成树(MST)的总权值是否小于等于$x$?

与上一个不同,这个例题我直接把问题的抽象形式写了出来,这样一是鼓励大家进行抽象思考,第二是图论问题要用文字简洁的写出来还是有点麻烦的,所以就偷了点懒.

对于这个问题来说,我们只需要找到这个$G$的MST, 无论是使用prim还是kruskal算法,然后将MST的权值加起来,和$x$进行比较即可.得到的答案就是我们的最终是非结果.

例如按照prim算法的性能最差为:

O(VlogV + ElogV) = O(ElogV)

可以近似的看成 $n(log n)$, 因此这个问题的求解时间也是在多项式时间之内.故而我们称,求解G内MST权值和的问题也是属于P类的.

有一点要注意,对于P类问题来说,我们的最终解可以是真也可以是假,一切都要根据具体的题目和问题来进行回答.即使在规定时间内只能回答出假,由于这个是题目的条件约束导致的,并不会影响我们对于这个题目时间复杂度的判定标准.

全称为nondeterministic polynomial time