数据结构与算法学习--复杂度分析

什么是复杂度分析

1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4. 复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

为什么需要复杂度分析

1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

如何进行复杂度分析

对于时间复杂度的分析，通常使用大O复杂度表示法，表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

用公式表示，就是 T(n) = O(f(n))表示，其中 T(n) 表示算法执行总时间，f(n) 表示每行代码执行总次数，而 n 表示数据的规模。

由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时可以忽略这些项。

具体分析的时候，有下列三个方法：

1. 单段代码只看循环次数最多的部分；
2. 多段代码取复杂度最高的：即有个多个循环，但只看循环次数量级最高的那段代码
3. 乘法法则--嵌套代码进行乘积：多个循环嵌套，就是相乘

常见的时间复杂度

按照数量级递增，常见的时间复杂度量级有：

• 常量阶 O(1)
• 对数阶 O(logn)
• 线性阶 O(n)
• 线性对数阶 O(nlogn)
• 平方阶 O(n^2)，立方阶 O(n^3)...k次阶 O(n^k)
• 指数阶 O(2^n)
• 阶乘阶 O(n!)

其中，最后两种情况是非常糟糕的情况，当然 O(n^2) 也是一个可以继续进行优化的情况。

接下来简单介绍上述复杂度中的几种比较常见的：

O(1)

O(1) 表示的是常量级时间复杂度，也就是只要代码的执行时间不随 n 的增大而增长，都记作 O(1) 。一般只要算法不包含循环语句和递归语句，时间复杂度都是 O(1)

像下列代码，有 3 行，但时间复杂度依然是O(1)，而非 O(3)。

a = 3
b = 4
print(a + b)

O(logn)、O(nlogn)

O(logn) 也是一个常见的时间复杂度，下面是一个 O(logn) 的代码例子：

i = 1
count = 0
n = 20
while i <= n:
    count += 1
    i *= 2
print(‘while 循环运行了 {} 次‘.format(count))

这段代码其实就是每次循环都让变量 i 乘以 2，直到其大于等于 n，这里我设置 n=20，然后运行了后，输出结果是循环运行了 5 次。

实际上这段代码的结束条件，就是求 2^x=n 中的 x 是等于多少，那么循环次数也就知道了，而求 x 的数值，方法就是 ，那么时间复杂度就是

假如上述代码进行简单的修改，将 i *= 2 修改为 i *= 3 ，那么同理可以得到时间复杂度就是 。

但在这里，无论是以哪个为对数的底，我们都把对数阶的时间复杂度记为 O(logn) 。

这里主要原因有两个：

1. 对数可以互换，比如 ，也就是 ，常量
2. 基于前面的理论，系数可以被忽略，也就是这里的常量 C 可以忽略

基于这两个原因，对数阶的时间复杂度都忽略了底，统一为 O(logn) 。

至于 O(nlogn) ，根据乘法法则，只需要将对数阶复杂度的代码，运行 n 次，就可以得到这个线性对数阶复杂度了。

注意， O(nlogn) 是非常常见的时间复杂度，常用的排序算法如归并排序、快速排序的时间复杂度都是 O(nlogn)

O(m+n)、O(m*n)

前面介绍的情况都是只有一个数据规模 n ，但这里介绍有两个数据规模的情况--m 和 n。

# O(m+n)
def cal(n, m):
    result = 0
    for i in range(n):
        result += i

    for j in range(m):
        result += j * 2

    return result

简单的代码示例如上述所示，如果事先无法评估 m 和 n 的量级大小，那么这里的时间复杂度就没法选择量级最大的，所以其时间复杂度就是 O(m+n) 。

同理，对于嵌套循环，就是 O(m*n) 的时间复杂度了。

最好、最坏、平均、均摊时间复杂度

这四种复杂度的定义如下：

• 最好情况时间复杂度：代码在最理想的情况下执行的时间复杂度；
• 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度；
• 平均情况时间复杂度：代码在所有情况下执行的次数的加权平均值表示；
• 均摊时间复杂度：代码执行的所有复杂度情况中，绝大多数都是低级别的复杂度，个别情况会发生最高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊复杂度就等于低级别复杂度，也可以看作是特殊的平均时间复杂度。

为什么会有这四种复杂度呢？原因是：

同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面、更准确描述代码的时间复杂度，引入这四种复杂度的概念；

但通常除非代码是出现量级差别的时间复杂度，才需要区分这四种复杂度，大多数情况都不需要区分它们。

下面是给出第一个代码例子：

# 在数组 arr 中查找目标数值 x
def find(arr, x):
    for val in arr:
        if val == x:
            return True
    return False

这个例子假设数组 arr 的长度是 n ，那么它最好的情况，就是第一个数值就是需要查找的 x ，此时复杂度是 O(1) ，但最坏情况就是最后一个数值或者不存在需要查找的 x ，那么此时就遍历一遍数组，复杂度就是 O(n) ，因此这段代码最好和最坏情况是会出现量级差别的，O(1) 和 O(n) 分别是最好情况复杂度和最坏情况复杂度。

而这段代码的平均情况时间复杂度是 O(n) ，具体分析就是首先考虑所有可能的情况以及对应出现的概率，可能发生的情况先分为两种，存在和不存在需要查找的数值 x ，也就是分别是 1/2 的概率，然后对于存在的情况下，又有 n 种情况，即出现在数组任意位置的概率都是均等的，那么它们的概率乘以存在的概率就是 1/2n ，接着再考虑每种情况需要搜索的元素个数，其实就是代码执行的次数，这个分别就是从 1 到 n，并且对于不存在的情况，也是 n ，需要遍历一遍数组才发现不存在，所以平均时间复杂度的计算过程如下：

计算得到的就是概率论中的加权平均值，也叫期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

这里用大 O 表示法表示，并且去掉常量和系数后，就是 O(n)。

最后介绍下均摊时间复杂度，需要满足以下两个条件才使用：

1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；

2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

空间复杂度分析

和时间复杂度的定义类似，空间复杂度全称就是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。

简单介绍下一个程序所需要的空间主要由以下几个部分构成：

• 指令空间：是值用来存储经过编译之后的程序指令所需要的空间。
• 数据空间：是指用来存储所有常量和变量值所需的空间。其主要由两个部分构成：

  • 存储常量和简单变量所需要的空间
  • 存储复合变量所需要的空间。这一类空间包括数据结构所需要的动态分配的空间
• 环境栈空间：用来保存函数调用返回时恢复运行所需要的信息。例如，如果函数 fun1 调用了函数 fun2，那么至少必须保存 fun2 结束时 fun1 将要继续执行的指令的地址。

参考：

• 极客时间数据结构课程