1.2.1 时间复杂度

时间复杂度T（n）=O（f（n）），其中，f（n）表示代码的执行次数；空间复杂度S（n）=O（f（n）），其中，f（n）表示程序分配的空间。大O表示法并不用于真实代表算法的精确时间和空间，它用来表示代码在执行过程中时间或者空间的增长变化趋势。比如，一个算法的时间复杂度是O（2n+1），另一个算法的时间复杂度是O（10n+1），虽然两个算法的代码执行次数不一样，但是它们的时间复杂度却是一样的，我们都可以说两个算法的时间复杂度都是O（n）。通常算法复杂度有如下几个量级，如表1.1所示。

表1.1 算法复杂度

当n无限大时，算法复杂度之间的关系是

O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n2)<O(n3)<O(nk)<O(2n)<O(n!)

算法复杂度越大，执行的效率越低，通常我们实际编写程序的算法复杂度不会超过O（n3），因此我们选取O（n3）之前的算法复杂度进行讲解。我们先介绍时间复杂度。

常见的时间复杂度有常数阶O（1）、对数阶O（log₂n）、线性阶O（n）、线性对数阶O（nlog₂n）、平方阶O（n2）及立方阶O（n3）。

（1）常数阶O（1）：通常最简单的算法没有循环等复杂结构，那么这个算法的时间复杂度就是O（1），如下代码表示一个加法函数，该函数的时间复杂度就是O（1）。

（2）对数阶O（log₂n）：一般是二分搜索算法的时间复杂度，一个程序可以通过折半的思路不断递归，如猜数游戏的代码就是一个典型的二分搜索算法，该算法的时间复杂度就是O（log₂n），如下所示。

（3）线性阶O（n）：代码中只有一层循环，就是常数阶，常数阶的算法基本进行一次遍历即可求出结果，如下代码表示一个求和函数，该函数的时间复杂度就是O（n）。

（4）线性对数阶O（nlog₂n）：顾名思义，将时间复杂度为O（log₂n）的代码循环n遍就是n O（log₂n），也就是O（nlog₂n）。我们知道二分搜索算法的时间复杂度是对数阶O（log₂n），那么我们现在将数组打乱，找到新数组对应原来数组的对应关系，我们通过循环n遍二分查找来解决这个问题，具体代码如下所示，这样算法的时间复杂度是O（nlog₂n）。

（5）平方阶O（n2）：很容易理解，二维数组的遍历的时间复杂度就是O（n2），如下代码，表示一个二维数组所有元素求和。

（6）立方阶O（n3）：有了平方阶的基础，立方阶O（n3）就更容易理解了，三维数组的遍历的时间复杂度就是O（n3），如下代码表示一个三维数组所有元素求和，时间复杂度是O（n3）。

如果算法的复杂度超过了立方阶，那么在数据量很大的情况下，这个时间复杂度是不可忍受的。