第21章 P/NP问题的本质（2 / 2）

它描述了算法运行时间或空间使用量随输入规模增加时的增长速度。

计算复杂度是对算法效率的一种度量，可以帮助我们比较不同算法之间的效率，并选择最适合特定问题的算法。

常见的计算复杂度包括时间复杂度和空间复杂度。

时间复杂度是描述算法执行所需的时间量。

它通常用大o符号表示，表示算法执行时间随着输入规模增长的上界。时间复杂度可分为以下常见类别：

常数时间复杂度：o(1)，算法的执行时间与输入规模无关。

线性时间复杂度：o(n)，算法的执行时间与输入规模成正比。

对数时间复杂度：o(logn)，算法的执行时间随输入规模的增加而增加，但增长速率较慢。

平方时间复杂度：o(n2)，算法的执行时间与输入规模的平方成正比。

指数时间复杂度：o(2^n)，算法的执行时间随输入规模呈指数级增长。

更高阶复杂度如o(n!)（ps：多项式复杂度和o(n^n)（ps：指数复杂度等。

而空间复杂度是描述算法执行所需的额外空间或内存量。

类似于时间复杂度，它也用大o符号表示，表示算法所需的额外空间随着输入规模增长的上界。

理解计算复杂度的重要性在于能够评估和比较不同算法之间的效率，以选择最适合解决问题的算法。

通常情况下，我们希望选择时间复杂度低且空间复杂度较小的算法，以实现更高效的计算和资源利用。

计算复杂度还可以指导算法设计和优化，以提高算法的性能和效率。

而从计算复杂度的角度来说，试除法是一种简单但相对较慢的素数验证方法。

因为试除法需要逐个检查每个可能的除数，当待检查数非常大时，该过程变得非常耗时。

试除法的时间复杂度随待检查数的大小呈指数增长，亦即其时间复杂度是指数级的。

通过试除法来验证素数，不要说是对付上千万位的数，就算是对付一些超大数，试除法也只会很乏力。

对于超大规模的素数，实际应用中是不适用应用试除法验证如此大的数是否为素数。

实际应用中，对于超大规模的数，如果要验证其是不是素数一般都采用别的更高效的方式。

至少该方式所对应的复杂度也不能是指数复杂度。

指数复杂度通常意味着问题的解决时间会随着问题规模的增长呈指数级增长。

这并不一定意味着问题无解，而是指在实际计算上，对于较大规模的问题，找到解决方案所需的计算资源和时间可能是不可行的。

对于某些问题，尽管其具有指数复杂度，但仍然存在有效的解决方案。

例如，某些组合优化问题，如旅行商问题（tsp，在理论上是指数难解的，但有许多启发式算法和近似算法可以在实践中找到接近最优解的解决方案。

然而，对于某些问题，指数复杂度可能意味着找到精确解决方案是困难的或不切实际的。

例如，对于某些特定的组合优化问题，如子集和问题（subsetsum，由于其指数复杂度，当问题规模较大时，无法通过穷举搜索所有可能的解决方案来找到最优解。

因此，指数复杂度并不直接表示问题无解，而是指在实际情况下，对于大规模问题找到精确解决方案可能非常困难。

在这种情况下，如果可以要尽量避免一个问题其计算复杂度是指数复杂度。