第2天：算法复杂度

前言

  作为一名合格的计算机人员，无论是做开发还是研究算法，一个程序的算法复杂度显得尤为重要。因此，一般我们在大一的时候，无论在学哪门编程语言之前都会提到算法的时间复杂度。但是均不会提的太深。但是作为一名从事计算机开发人员，我们应该深入了解时间复杂度是特别有必要的。接下来就给大家深入的分析一下时间复杂度。
  *是这样介绍算法的时间复杂度：在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。说的通俗一点就是：时间复杂度指的是程序运行所占用的时间，并且在执行程序过程中执行的操作数。空间复杂度指的是程序所占用的空间。

主定理(Master Theorem)

  我们在计算时间复杂度时，经常会用到递归树和主定理，接下来给大家介绍主定理的内容以及用法。以下是主定理的内容：

  这里需要我们注意的是下面的三个条件；如果写成详细的数学公式如下：

具体我们举几个案例来掌握这个公式和三个条件的应用
1、求T(n) = 3T(n/2) + n^2的时间复杂度

2、求T(n) = 4T(n/2) + n^2的时间复杂度

3、求T(n) = 16T(n/4) + n的时间复杂度

  从这三道题中我们可以得出其实这三个条件，就是比较n^(log_b_a)和f(n)，谁大谁就是最终的时间复杂度，如果相等的话，就在时间复杂度的基础上添加一个logn。

递归树

  相信大家都知道斐波那契数，那个通项公式就是f(n) = f(n-1)+f(n-2), 其中n>=3;当n为1, 2时，f(n) = 1; 那么它的时间和空间复杂度应该怎么计算呢？
  首先我们应该弄清楚其计算方式。
假如我们要计算f(6)，以下是计算过程：

  由此递归树可知，计算f(6)需要计算f(1)和f(2)的次数为2^6.因此计算斐波那契数列需要的时间复杂度为O(2 ^n).空间复杂度可以通过一个栈来模拟其操作，因此需要O(n)。但是，我们要知道之所以时间复杂是指数型的，是因为在计算过程中有很多重复项需要计算，因此，我们将递归改为迭代，通过一个数组来存储计算好的数据，如果是这样，我们的时间复杂度为O(n)，如果直接定义两个变量存储，则只需要空间复杂度为O(1)。

P vs. NP vs. NPC vs. NPH

  知道时间复杂度计算之后，我们应该了解算法中经常遇到的这四种问题：
1、首先就是P问题，通俗的将就是一个问题可以在多项式（O(n^k)）的时间复杂度内解决，即计算机比较容易算出答案的问题。
2、NP问题：问题的解可以在多项式的时间内被验证；简单来说就是已知答案以后计算机可以比较容易地验证答案的问题。
3、NPH问题：任意np问题都可以在多项式时间内归约为该问题，但该问题本身不一定是NP问题；也就是给出一个答案，计算机可能验证也可能验证不了。
4、NPC问题：既是NP问题，也是NP-hard问题。
最后我们可以通过一张图来清晰的看出这四者之间的关系。

总结

  本文详细的介绍了时间复杂度，以及在设计一个算法时，经常遇到的四类问题。计算一个算法的时间复杂度，是我们作为一名算法的设计者应该具备的知识，因此，需要我们熟练掌握本文给出的方法，尤其是主定理，是递归中最常用的方法。当然，我们也理解了P、NP、NPH和NPC四类问题的大致情况，最后通过一张图将其清晰的展现出来。希望对初学者在算法复杂度上有所帮助。

参考文献

  本文主要参考以下资料
[1] *
[2] 主定理（Master Theorem）与时间复杂度
[3] 面试_什么是P、NP、NPC、NPH问题
[4] NP问题、NP难问题(NPH)和NP完全问题(NPC)理解