复杂度分析

复杂度分析在我看来是数据结构与算法学习入门知识，尤为重要。

为什么复杂度分析重要？

数据结构与算法的出现本就是为了花更少的时间和空间（储存）来解决问题。复杂度分析就是为解决如何“花更少的时间和空间（储存）”的问题。

现在各种编译工具，代码跑完就能显示用了多少时间，占了多少内存。但是这些数据都是在完成代码编写之后才能得到的，这是事后统计方法。

事后统计法得到的结果会因计算机性能和测试数据规模不同而有较大差异。这并不能体现出代码本身的效率、优劣程度，而且很可能写出的代码本身就不太行。。。

而复杂度分析不依赖软硬件性能、数据规模等就能直接估算算法的效率、优劣，这就是其重要性。

时间复杂度

时间复杂度即算法的运行时间。

用运行时间去描述算法的效率时，算法的执行总步数越多算法越慢，总步数越少则越快。

假设每一行代码运行时间都为X，则算法的总运行时间等于运行的总代码行数。

1 def sum(n):
2     sum = 0
3 
4     for i in range(n):
5         sum += i
6     return sum

在上面代码中，假设运行一行需要 1t，则第二行运行时间为 1t，第四行、第五行执行了n遍，每行运行时间为 nt，则运行总时间就是（1+2n）t

用函数来表示就是 T(n) = (1+2n) t，可以看出T(n)和总步数成正比关系。

用 大O表示法 就是 T(n) = O(f(n))，f(n)为执行总步数。

n可以是1到+∞，当其非常大的时候，一些相对于n来说小的部分就可以忽略了。

拿前面的 1+2n 来说，当n = 100000时，1+2n = 2000001，n持续变大，常数1和系数2对结果影响就很微小了，直接忽略，最终变成了 T(n) = O(n)。

下面例子作为练习：

1 def sum(n):
2     sum = 0
3 
4     for i in range(n):
5         for j in range(n):
6             sum += i + j
7     return sum

其中有个嵌套for循环，第四行执行1次，第五行、第六行执行n次

第二行需要运行1次，第四行运行n次，第五行、第六行执行n2次，总步数 f(n) = 1 +n +2n2

当n非常大的时候，对运算结果有影响的是n2，常数1、n、系数2都可以忽略，则 f(n) = n2，代码运行时间 T(n) = O(n2)。

常见时间复杂度

最好情况、最坏情况和平均情况时间复杂度

一段代码中，数据的具体情况也会影响运行时间

def test(list, num):

    index = -1
    for i in range(len(list)):
        if list[i] == num:
            index = i
            break

    return index

这段代码是求 变量num 在上列表 list 中的索引

假设输入的 list = [1,2,3,4,5]

当 num = 1 时，自第一次执行时就在list中找到了，后面不再遍历，此时时间复杂度为 O(1)。

当 num = 5 时，全部遍历完才找到，此时时间复杂度为 O(n)。

当 num = 6 时，全部遍历完也没找到，此时时间复杂度也为 O(n)。

这就是数据情况不同，时间复杂度不同。

这样就出现 最好情况、最坏情况时间复杂度。

最好情况时间复杂度就是最理想情况下代码复杂度，对应上面例子最好时间复杂度就是O(1)；

最坏情况时间复杂度就是最不理想情况下代码复杂度，对应上面例子最好时间复杂度就是O(n)；

平均时间复杂度根据加权平均值求得。拿上面例子来说就是 O((3n+1)/4) = O(n)

像最好情况时间复杂度，平均时间复杂度并没有太大参考价值，一般都是拿最坏时间复杂度当时间复杂度，因为不会有比最坏的情况再坏的了，可以说最坏时间复杂度就是一个底线。

空间复杂度

空间复杂度反应的是代码运行过程中临时变量占用的内存空间。

代码运行所占空间分为三种：1、代码本身所占空间；2、输入数据所占空间；3、临时变量所占空间

1和2与代码性能无关，所以空间复杂度只考虑运行过程临时占用空间

空间复杂度记作S(n)，表示形式同样为O(f(n))

def sum(list):
    sum = 0
    for i in range(len(list)):
        sum += list[i]

    return sum

该代码求输入列表list中所有元素的和。

其中，输入的list空间不计，sum存储和，i存储元素索引，都是常数，其所占空间与n没有关系，所以该代码空间复杂度S(n) = O(1)

常见空间复杂度

O(n):

def createList(n):
    list = []
    for i in range(n):
        list.append(i)

    return list

其中临时变量有 list和i

list为空列表，所占用空间根据for循环次数增加，最大为n，所以list的空间复杂度为O(n)，i为常数阶，与n无关，则整个代码空间复杂度为O(n)

O(n2):

def createList(n):
    list1 = []
    for i in range(n):
        list2 = []
        for j in range(n):
            list2.append(j)
        list1.append(list2)
    return list1

这段代码比上面那个多了一层嵌套for循环，list1的空间占用为n，list2的空间占用为n2，则整个代码空间复杂度为O(n2)

本文作者： mmsmd