时间复杂度与空间复杂度

目录

• 时间复杂度
• • 从简单例子认识时间复杂度
  • 如何快速简单判断时间复杂度
  • 时间复杂度详解
• 空间复杂度
• • 空间复杂度简单理解
  • 空间复杂度详解
• 时空权衡

算法复杂度旨在计算：输入数据量为 n n n的情况下，算法的使用时间和空间情况，体现了算法运行时间和空间随数据大小 n n n增大的速度。

时间复杂度 从简单例子认识时间复杂度

对于这四组代码，很明显第一组代码运行时间最短。

但是我们不能知道第一组代码到底运行了多长时间，所以我们需要用时间复杂度反映代码的运行快慢。

对于 O ( 1 ) O(1) O(1)， O O O代表值的上届，我们其实可以理解为取数量级的大约。

1 1 1是一个数量级单位；对于 O ( n ) O(n) O(n)， n n n是数量级为 n n n的单位；所以对于上面四组代码，时间复杂度分别为： O ( 1 ) O(1) O(1)， O ( n ) O(n) O(n)， O ( n 2 ) O(n^{2}) O(n2)， O ( n 3 ) O(n^{3}) O(n3)；

注意， 1 1 1， n n n， n 2 n^{2} n2， n 3 n^{3} n3都是数量级单位，所以下面有：

时间复杂度不是 O ( 3 ) O(3) O(3)， O ( n × ( 1 + n ) ) = O ( n 2 + n ) O(n\times(1+n))=O(n^{2}+n) O(n×(1+n))=O(n2+n)，我们只取单位的基本与主要的数量级，因此是： O ( 1 ) O(1) O(1)， O ( n 2 ) O(n^{2}) O(n2)；

对于下面的情况：

由于 2 6 = 64 2^{6}=64 26=64，所以有 l o g 2 64 = 6 log_{2}64=6 log2​64=6，时间复杂度记作 O ( l o g 2 n ) O(log_{2}n) O(log2​n)或者 O ( l o g n ) O(logn) O(logn)，通常，当算法中出现循环并且规模折半时，复杂度中会出现 l o g n logn logn；

常见的时间复杂度有： O ( 1 ) < O ( l o g n ) < O ( n ) < O ( n l o g n ) < O ( n 2 ) < O ( n 2 l o g n ) < O ( n 3 ) O(1)O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)复杂问题的时间复杂度有： O ( n ! ) , O ( 2 n ) , O ( n n ) O(n!),O(2^{n}),O(n^{n}) O(n!),O(2n),O(nn)

如何快速简单判断时间复杂度

该方法适用于绝大多数的简单情况：

• 首先确定问题规模 n n n；比如对列表排序， n n n应该是列表的长度（因为可能要对每个元素进行 *** 作，一共 n n n个元素）
• 循环减半过程通常有 l o g n logn logn；
• K K K层关于 n n n的循环通常有 n k n^{k} nk；比如下图后两组代码就是 O ( n 2 ) O(n^{2}) O(n2)， O ( n 3 ) O(n^{3}) O(n3)，因为分别是两层和三层关于 n n n的循环。
  

  
  

时间复杂度详解

根据定义，时间复杂度指输入数据大小为 N N N时，算法运行所需花费的时间，需要注意：

• 统计的是算法的「计算 *** 作数量」，而不是「运行的绝对时间」。
  

  计算 *** 作数量和运行绝对时间呈正相关关系，并不相等。
  

  算法运行时间受到「编程语言 、计算机处理器速度、运行环境」等多种因素影响。
  

• 体现的是计算 *** 作数量随数据大小 N N N 变化时的变化情况。
  

  假设算法运行总共需要「 1次 *** 作」、「 100 次 *** 作」，此两情况的时间复杂度都为常数级 O ( 1 ) O(1) O(1) ；需要「 N N N 次 *** 作」、「 100 N 100N 100N 次 *** 作」的时间复杂度都为 O ( N ) O(N) O(N) 。
  

根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 O O O , Θ \Theta Θ , Ω \Omega Ω 三种符号表示。

以下借助一个查找算法的示例帮助理解。

时间复杂度的常见类别：

下面对不同时间复杂度举例解析，对所有示例，输入数据大小为 N N N，计算 *** 作数量为 c o u n t count count；

首先对于常数 O ( 1 ) O(1) O(1)，运行次数与 N N N大小呈常数关系，即不随输入数据大小 N N N 的变化而变化：

def algorithm(N):
    a = 1
    b = 2
    x = a * b + N
    return 1

对于下面代码，无论 a a a取值多少，计算 *** 作数量都与输入数据大小 N N N无关，因此，时间复杂度依然是 O ( 1 ) O(1) O(1)：

def algorithm(N):
    count = 0
    a = 10000
    for i in range(a):
        count += 1
    return count

对于线性 O ( N ) O(N) O(N)，循环运行次数与 N N N大小呈线性关系：

def algorithm(N):
    count = 0
    for i in range(N):
        count += 1
    return count

对于以下代码，虽然是两层循环，但第二层与 N N N 大小无关，因此整体仍与 N N N 呈线性关系：

def algorithm(N):
    count = 0
    a = 10000
    for i in range(N):
        for j in range(a):
            count += 1
    return count

对于平方 O ( N 2 ) O(N^{2}) O(N2)，两层循环相互独立，都与 N N N 呈线性关系，因此总体与 N N N 呈平方关系：

def algorithm(N):
    count = 0
    for i in range(N):
        for j in range(N):
            count += 1
    return count

以「冒泡排序」为例，其包含两层独立循环：

• 第一层复杂度为 O ( N ) O(N) O(N)；
• 第二层平均循环 N / 2 N/2 N/2次，复杂度为 O ( N ) O(N) O(N)；

因此，冒泡排序的时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)：

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):
        for j in range(N - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

对于指数 O ( 2 N ) O(2^{N}) O(2N)，生物学科中的 “细胞分裂” 即是指数级增长。

初始状态为 1 个细胞，分裂一轮后为 2 个，分裂两轮后为 4 个，……，分裂 N N N 轮后有 2 N 2^{N} 2N 个细胞。

在算法中，指数阶常出现于递归，算法原理图与代码如下所示：

def algorithm(N):
    if N <= 0: return 1
    count_1 = algorithm(N - 1)
    count_2 = algorithm(N - 1)
    return count_1 + count_2

对于阶乘 O ( N ! ) O(N!) O(N!)，阶乘阶对应数学上常见的 “全排列” 。

即给定 N N N 个互不重复的元素，求其所有可能的排列方案，则方案数量为： N ( N − 1 ) ( N − 2 ) . . . 1 = N ! N(N-1)(N-2)...1=N! N(N−1)(N−2)...1=N!如下图与代码所示，阶乘常使用递归实现，算法原理：第一层分裂出 N N N 个，第二层分裂出 N − 1 N−1 N−1 个，…… ，直至到第 N N N 层时终止并回溯。

def algorithm(N):
    if N <= 0: return 1
    count = 0
    for _ in range(N):
        count += algorithm(N - 1)
    return count

对于对数 O ( l o g N ) O(logN) O(logN)，对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况” 。

对数阶常出现于「二分法」、「分治」等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想。

设循环次数为 m m m，则输入数据大小 N N N与 2 m 2^{m} 2m呈线性关系，两边同时取 l o g 2 log_{2} log2​对数，则得到循环次数 m m m与 l o g 2 N log_{2}N log2​N呈线性关系，即时间复杂度为 O ( l o g N ) O(logN) O(logN)：

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        count += 1
    return count

如以下代码所示，对于不同 a a a 的取值，循环次数 m m m 与 l o g a N log_{a}N loga​N 呈线性关系 ，时间复杂度为 O ( l o g a N ) O(log_{a} N) O(loga​N)。

而无论底数 a a a 取值，时间复杂度都可记作 O ( l o g N ) O(log N) O(logN)，根据对数换底公式的推导如下： O ( l o g a N ) = O ( l o g 2 N ) O ( l o g 2 a ) = O ( l o g N ) O(log_{a}N)=\frac{O(log_{2}N)}{O(log_{2}a)}=O(logN) O(loga​N)=O(log2​a)O(log2​N)​=O(logN)

def algorithm(N):
    count = 0
    i = N
    a = 3
    while i > 1:
        i = i / a
        count += 1
    return count

如下图所示，为二分查找的时间复杂度示意图，每次二分将搜索区间缩小一半：

对于线性对数 O ( N l o g N ) O(NlogN) O(NlogN)，两层循环相互独立，第一层和第二层时间复杂度分别为 O ( l o g N ) O(logN) O(logN)和 O ( N ) O(N) O(N)，则总体时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)：

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        for j in range(N):
            count += 1

线性对数阶常出现于排序算法，例如「快速排序」、「归并排序」、「堆排序」等，其时间复杂度原理如下图所示：

空间复杂度 空间复杂度简单理解

空间复杂度用于评估算法的内存占用大小，通常：

• 算法只占用几个变量： O ( 1 ) O(1) O(1)；
• 算法使用了长度为 n n n的一维数组： O ( n ) O(n) O(n)；
• 算法使用了 m m m行 n n n列的二维数组： O ( m n ) O(mn) O(mn)；

空间复杂度详解

空间复杂度涉及的空间类型有：

• 输入空间： 存储输入数据所需的空间大小；
• 暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
• 输出空间： 算法运行返回时，存储输出数据所需的空间大小；

通常情况下，空间复杂度指在输入数据大小为 N N N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。

而根据不同来源，算法使用的内存空间分为三类：

• 指令空间：编译后，程序指令所使用的内存空间。
  

• 数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。
  

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def algorithm(N):
    num = N         # 变量
    nums = [0] * N  # 动态数组
    node = Node(N)  # 动态对象

• 栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。
  

  如以下代码所示，在循环中调用函数，每轮调用 test() 返回后，栈帧空间已被释放，因此空间复杂度仍为 O ( 1 ) O(1) O(1)：

def test():
    return 0

def algorithm(N):
    for _ in range(N):
        test()

算法中，栈帧空间的累计常出现于递归调用。

如以下代码所示，通过递归调用，会同时存在 N N N 个未返回的函数 algorithm() ，此时累计使用 O ( N ) O(N) O(N) 大小的栈帧空间：

def algorithm(N):
    if N <= 1: return 1
    return algorithm(N - 1) + 1

通常情况下，空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号 O O O 表示。

最差情况有两层含义，分别为「最差输入数据」、算法运行中的「最差运行点」。

例如以下代码：

根据从小到大排列，常见的算法空间复杂度有： O ( 1 ) < O ( l o g N ) < O ( N ) < O ( N 2 ) < O ( 2 N ) O(1)O(1)<O(logN)<O(N)<O(N2)<O(2N)

对于以下所有示例，设输入数据大小为正整数 N N N ，节点类 Node 、函数 test() 如以下代码所示：

# 节点类 Node
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# 函数 test()
def test():
    return 0

对于常数 O ( 1 ) O(1) O(1)，普通常量、变量、对象、元素数量与输入数据大小 N N N 无关的集合，皆使用常数大小的空间：

def algorithm(N):
    num = 0
    nums = [0] * 10000
    node = Node(0)
    dic = { 0: '0' }

如以下代码所示，虽然函数 test() 调用了 N N N 次，但每轮调用后 test() 已返回，无累计栈帧空间使用，因此空间复杂度仍为 O ( 1 ) O(1) O(1) ：

def algorithm(N):
    for _ in range(N):
        test()

对于线性 O ( N ) O(N) O(N)，元素数量与 N N N 呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等），皆使用线性大小的空间：

def algorithm(N):
    nums_1 = [0] * N
    nums_2 = [0] * (N // 2)

    nodes = [Node(i) for i in range(N)]
    
    dic = {}
    for i in range(N):
        dic[i] = str(i)

如下图与代码所示，此递归调用期间，会同时存在 N N N 个未返回的 algorithm() 函数，因此使用 O ( N ) O(N) O(N) 大小的栈帧空间：

def algorithm(N):
    if N <= 1: return 1
    return algorithm(N - 1) + 1

对于平方 O ( N 2 ) O(N^{2}) O(N2)，元素数量与 N N N 呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间：

def algorithm(N):
    num_matrix = [[0 for j in range(N)] for i in range(N)]
    node_matrix = [[Node(j) for j in range(N)] for i in range(N)]

如下图与代码所示，递归调用时同时存在 N N N 个未返回的 algorithm() 函数，使用 O ( N ) O(N) O(N) 栈帧空间；每层递归函数中声明了数组，平均长度为 N / 2 N/2 N/2，使用 O ( N ) O(N) O(N)空间；因此总体空间复杂度为 O ( N 2 ) O(N^{2}) O(N2)：

def algorithm(N):
    if N <= 0: return 0
    nums = [0] * N
    return algorithm(N - 1)

对于平方 O ( 2 N ) O(2^{N}) O(2N)，指数阶常见于二叉树、多叉树。

例如，高度为 N N N 的「满二叉树」的节点数量为 2 N 2^{N} 2N，占用 O ( 2 N ) O(2^{N}) O(2N) 大小的空间；同理，高度为 N N N 的「满 m m m 叉树」的节点数量为 m N m^{N} mN，占用 O ( m N ) = O ( 2 N ) O(m^{N})=O(2^{N}) O(mN)=O(2N) 大小的空间：

对于对数 O ( l o g N ) O(logN) O(logN)，对数阶常出现于分治算法的栈帧空间累计、数据类型转换等，例如：

• 快速排序，平均空间复杂度为 Θ ( l o g N ) \Theta(logN) Θ(logN)，最差空间复杂度为 O ( N ) O(N) O(N)。
  

• 数字转化为字符串，设某正整数为 N N N，则字符串的空间复杂度为 O ( l o g N ) O(logN) O(logN)。
  

  推导如下：正整数 N N N 的位数为 l o g 10 N log_{10}N log10​N，即转化的字符串长度为 l o g 10 N log_{10}N log10​N，因此空间复杂度为 O ( l o g N ) O(logN) O(logN)。
  

时空权衡

对于算法的性能，需要从时间和空间的使用情况来综合评价。

优良的算法应具备两个特性，即时间和空间复杂度皆较低。

而实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。

降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然。

由于当代计算机的内存充足，通常情况下，算法设计中一般会采取「空间换时间」的做法，即牺牲部分计算机存储空间，来提升算法的运行速度。

以 两数之和 为例，「暴力枚举」和「辅助哈希表」分别为「空间最优」和「时间最优」的两种算法。

• 方法一：暴力枚举，时间复杂度 O ( N 2 ) O(N^{2}) O(N2)，空间复杂度 O ( 1 ) O(1) O(1) ；属于「时间换空间」，虽然仅使用常数大小的额外空间，但运行速度过慢：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return i, j
        return

• 方法二：辅助哈希表，时间复杂度 O ( N ) O(N) O(N) ，空间复杂度 O ( N ) O(N) O(N) ；属于「空间换时间」，借助辅助哈希表 dic ，通过保存数组元素值与索引的映射来提升算法运行效率，是本题的最佳解法。
  

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(len(nums)):
            if target - nums[i] in dic:
                return dic[target - nums[i]], i
            dic[nums[i]] = i
        return []