算法分析笔记:复杂度分析与NP完全性理论

1. 算法复杂度分析

算法复杂度说明了该算法占用计算机资源的多少。由此我们能知道，算法复杂度有时间和空间之分。而在如今计算机存储空间普遍较大的情况下，我们往往更加注重算法时间复杂度，即算法效率的优化。因此在算法复杂度分析时，我们主要讨论算法的时间复杂度。

1.1 算法复杂度函数的具体化

   我们使用来分别表示一个算法需要解的问题的规模、算法的输入和算法本身，使用来表示算法复杂性。那么我们可以令。其中的就是复杂度函数，其一般由算法本身特性得出，因此我们可以将省略。为了方便理解，我们将用来替换，表示时间复杂度，得到函数，并将该函数具体化分析。

   我们假设有一台抽象的计算机，并在上面运行一个算法。算法中执行的最小运算我们称为元运算。我们设有种元运算，分别记为，每一种元运算单词执行时间分别为。经过统计，算法中元运算使用的次数为。需要注意的是，使用次数往往和问题的规模以及算法输入有关，因此我们可以得出，其中即为关系函数。由此可得:

其中是与和无关的常数。

  进一步具体化的，我们可以考虑最好，最坏情况和平均的时间复杂度。一般情况下，同种算法的复杂度好坏是根据其输入条件变化的。因此我们很容易得出其三种状况的复杂度情况。我们设是能使算法时间复杂度达到的合法输入，是能使时间复杂度达到的合法输入，是输入为的概率。那么我们能得到:

其中,是规模为的合法输入集合。

1.2 渐进复杂度的分析

   在面对一些较大规模的算法时，我们很难去计算其具体的复杂度。因此需要引入渐进复杂度的概念来方便我们比较两种算法的效率。同样以时间复杂度为例。对于，如果存在，当时，可以使得，就称为该算法当时的渐进复杂度。一般我们认为就是式子中去掉常数项和低次项后的简单结果。

   例如，有，那么就是的一种情况。我们可以知道，当时，我们可以使用来近似，由此来分析对比算法复杂度。所以在上面的例子中，这个式子可以代替来分析时间复杂度。针对一个函数的在不同情况渐进意义，在数学上会给出五种符号来定义常见的情况:

• 上界: (big O)。令和是定义在正数集上的正函数，如果存在正数和，使得当时有，那么我们就说 在 时，是的一个上界:。

• 下界: (big Omega)。令和是定义在正数集上的正函数，如果存在正数和，使得当时，有，那么我们就说在时，是的一个下界:。

• 同阶: (theta)。定义当且仅当且时，称和是同阶的。

• 严格上界: (little o)。对于任意给定的正数,都存在正数，使得当时，有，那么我们就说在时，是的一个非紧上界:。

• 严格下界: (little omega)。对于任意给定的正数,都存在正数，使得当时，有，那么我们就说在时，是的一个非紧下界:。

2. NP完全性理论

在上面的内容中，我们了解了如何去分析一个算法的复杂度，此时我们就要来确认和评价一个算法的计算复杂性。与复杂度估算类似的，我们很难去判断一个问题中算法的实际计算时间，但可以通过对算法复杂度的分类来评价一个算法是“简单”还是“困难”。NP(Non-deterministic Polynomial)完全性理论就是用于区分计算求解“难易度”的理论方法。

2.1 P类问题

P类问题(Polynomial Problem)是指所有可以在多项式时间内求解的判定问题。

   计算机计算所涉及的数据量通常是十分巨大的，因此算法复杂度是否是在多项式时间以内往往决定了该种算法是否具备讨论的价值。对于P类问题而言，因为其求解时间在多项式时间内，且解决的问题是只针对true和flase的判断问题，因此可以认为P类问题是比较容易求解的问题。我们将P类问题归类于确定性模型下的易解决问题类。

2.2 NP类问题

NP类问题(Non-deterministic Polynomial Problem)是指所有可以在多项式时间内验证的判定问题。

   上面提到，P类问题是可以在多项式时间内求解的判断问题。而NP类问题则是将问题的解的正确性作为一个判断问题。这个问题的解是非确定性的，我们无法在多项式时间内求出它的解。但是我们可以在多项式时间内验证一个已经给出的解是否为正解。例如：对于一个给定的图，我们可以在多项式时间内验证一个给定的路径是否为该图的哈密顿路径。

2.3 NP-C类问题

NP完全类问题(Non-deterministic Polynomial Complete Problem)是NP类问题的特殊情况。

   NP-C类问题实际上是NP类问题中更加特殊的情况。这些问题的复杂度与整个类都有关联。如果这些问题中任何一个存在着可以多项式时间内的算法，那么所有的NP问题都可以在多项式时间内求解出来。或者说所有的NP类问题都可以约化(reduce to)为它。

2.4 NP-hard问题

   NP-hard问题较为特殊，它指的是所有NP类问题都可以约化为它，但其本身却不属于NP类的问题。

2.5 上四类问题的关系

   对于P类和NP类问题，目前还没有找到其具体准确的关系，针对这个式子的正确性的问题目前仍然在争论。这里先给出两种可能的关系维恩图: