时空复杂度

由于本文面向的人群并不是严苛的数学家或者从事计算机研究的工程师，所以并不打算使用过多的数学描述来谈论时空复杂度，只是讲述作为码农必须知道的部分。如果你有兴趣了解更加复杂、严格的时空复杂度的判别方式，可以自行寻找。

权衡一个算法的优劣，最重要的就是时空复杂度。时空复杂度要从两个方面看，空间复杂度与时间复杂度。要注意的事：一般我们谈论复杂度，都是考虑最坏的情况。

时间复杂度

一个程序执行的时间和它要解决的问题体量的关系叫时间复杂度。这句话或许有点绕口，但我们看一个例子，你就能懂了。

def find(l, item):
    for each in l:
        if each == item:
            return True
    return False

这是一个很简单的函数，如果item在l里就返回True，否则返回False。

当l长度为n时，最坏的情况就是把l遍历了一遍，我们把这一时间复杂度记为O(n)。因为最坏情况的执行时间和长度关系是一比一的。那么可以轻易推知，如果是嵌套的循环两遍，时间复杂度就是O(n²)。如果嵌套循环，一层循环n次，一层m次，那么时间复杂度则是O(n×m)。

当执行时间和要解决的的问题体量没有关系时，也就是无论问题体量有多大，所耗时间都相同时，时间复杂度为O(1)。

至于更为复杂的O(nlog(n))之类的，在后续谈到排序算法的时候会介绍计算方式。

你只需要对时间复杂度有一个概念即可。

空间复杂度

对与程序而言，空间就是内存空间。类似于时间复杂度，一个程序需要使用的额外的空间和它要解决的问题体量的关系叫空间复杂度。不同的是，我们提到空间复杂度的时候，总是说额外空间。

就譬如，你不需要任何额外的空间或者额外空间的大小固定(与列表长度无关)的对一个列表进行排序，那么空间复杂度就是O(1)。

以此类推，如果你需要一个与原列表相同大小的空列表，然后做一些骚操作进行排序，那么空间复杂度就是O(n)。