算法的性能评价

一个算法的优劣往往通过算法复杂度来衡量，算法复杂度包括时间复杂度和空间复杂度两个方面。时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

时间复杂度

时间复杂度描述的是一个算法执行时间与数据规模的增长关系，通常用 T(n) = O(f(n)) 来表示， n 表示数据的规模，f(n) 每行代码执行的次数总和。
这里的重点在于增长关系这几个字，一个算法的时间复杂度，通常只需要考虑 n 的增长规模，这里的 n 指的是每段代码的执行次数，所以时间复杂度大多都只看循环、递归来分析，而与那些常数、系数等无关。

def calc(n):
    sum = 0 
    i = 1
    for i in range(n+1):
        sum += i
    return sum

print(calc(5))

这段代码可以累加从 0 到 n 的和，我们这样对它进行分析：第 2、3 行代码需要执行一次，第 4、5 行需要执行 n 次，所以它的时间复杂度为 O(n + 2)。但是因为系数、常数这些对 n 的增长规模没有影响（如果是 n² 那就有影响了，都已经到平方阶了），不需要考虑，可以忽略，所以这样看其时间复杂度为 O(n) 。

def calc(n):
    sum = 0 
    i = 1
    for i in range(n+1):
        for j in range(n+1):
            sum += i*j
    return sum

print(calc(5))

像这种嵌套了两层 for 循环的代码，两行代码分别执行了 n 遍，并且是嵌套，时间复杂度就是 O(n²)。

def calc(n):
    return math.log(n)

print(calc(5))

像这样的一段代码里没有循环啊、递归等语句的，通常时间复杂度都是 O(1)。

时间复杂度计算小技巧
1、如果没有循环或递归，都是常量级的代码，时间复杂度就是 O(1)
2、只关注循环次数最多的一段代码，它的量级就可作为整段代码的时间复杂度
3、如果是for循环嵌套的代码，采用乘法计算其内外复杂度；如果是一个函数里有多段代码，则分析出每一段代码的时间复杂度，在将它们相加，最后去掉系数以及常数，取最大量级的作为整段代码的时间复杂度。例如，O(2n²+n+2) 可简化为 O(n²)。

空间复杂度

类比时间复杂度，空间复杂度的概念在几个字上不一样，完整表述为:描述一个算法占用空间与数据规模的增长关系。

def calc(n):
    i = 1
    result = np.zeros(n)
    for i in range(n):
        result[i] += i*i
    return result

print(calc(5))

第二行代码申请了存储空间 i，但它是常量阶的，跟数据的增长规模没有关系，所以不用理；第三行代码申请了一个容量为 n 的数组，剩下的代码都没有涉及到占用空间了，所以整段代码的空间复杂度为 O(n) 。

常见的复杂度

常见的复杂度从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)