ArturoYi
算法学习

算法基础1：复杂度分析

有句话说的好：复杂度分析是数据结构和算法中最重要的知识点，毫不夸张的说，这就是数据结构与算法学习的核心所在。你学会了它你就入的了门，你学不会它，你就永远不知道门儿在哪。

什么是算法复杂度

算法（Algorithm）是用来操作数据、解决程序问题的一组方法。

对于同一个程序问题，使用不同的算法，也许最终得到的结果一样，但是程序执行过程中消耗的资源和时间却会有很大的区别。

我们通常从两个维度衡量算法的效率：

  • 时间复杂度（Time Complexity）：程序执行算法所消耗的时间。
  • 空间复杂度（Space Complexity）：程序执行算法所需要占用的额外内存空间。

然而，时间和空间往往不能同时做到最优，所以需要根据场景取舍。

复杂度关注的是输入规模 n 变大时，资源消耗如何增长，而不是某台机器上的一次实测耗时。

时间复杂度

时间复杂度描述程序运行算法所需要的时间。运行时间越短，通常意味着效率越高。

我们来学习如何计算这个时间复杂度，很多人想的是把这个算法程序运行然后计算时间即可，但是我们得考虑运行环境，比如在不同配置的电脑上运行结果相差很大。

为了便于分析，假设每一行代码的运行时间都为 1 Btime，那么算法的总运行时间就等于代码执行次数的总和。

下面我们来看一下这段代码（提供了各种语言的例子）：

def dogeggs_sum (n):
  sum = 0
    
  for dogegg in range(n):
    sum += dogegg
  return sum

在上面的假设下，这段累加求和代码的总运行时间是多少呢？

  • 第二行代码需要 1 Btime 的运行时间，赋值操作。
  • 第四和第五行代码分别运行了n次，所以这两行各需要n * Btime的运行时间。

所以总的运行时间就是 (1+2n) * Btime。

我们一般用 T 函数来表示总运行时间，所以上面总的运行时间就可以表达为：

  • T(n) = (1+2n)*Btime。

这里用 n 表示数据量，也可以把它理解为数据集的规模或函数参数。

通过上面公式，我们发现T(n)和代码执行行数（次数）成正比关系，发现这个规律很重要，因为这告诉我们数据量和运行时间之间有正向趋势！

大 $O$ 表示法

大 $O$ 表示法不是用来精确计算算法的运行时间，而是用来表示增长趋势：

$$ T(n) = O(f(n)) $$

n 作为数据量大小，可以取 1、100、10000 甚至更大的数。当数据量越来越大时，代码中的某些部分对增长趋势的影响会逐渐变小。

还是以上面代码为例，当n=1000时，1+2n = 2001；当n=10000时，1+2n=20001，当n持续增大时，常数1和系数2对于最后的结果越来越没存在感了，即对趋势的变化影响不大。

这里常数 1 的影响很容易理解，但系数 2 常常让人困惑：明明 2n 看起来比 n 大很多，为什么也可以忽略？

大 $O$ 不是用来比较 2n 和 n 谁在某个具体输入下更快， 它是用来区分：当 n 越来越大时，总量是以什么形式暴涨，如果还不懂，在下面我们会进一步解释。

看完下面两段代码进一步学习一下求时间复杂度。

def dogeggs_sum (n):
  sum = 0

  for dogegg in range(n):
    for i in range(n):
      sum += dogegg * i
  return sum

我们一步步来计算时间复杂度。

  • 第二行代码需要运行 1 次。
  • 第四行代码需要运行 n 次。
  • 第五行代码需要运行 n² 次。
  • 第六行代码也需要运行 n² 次。

所以总的运行次数为 f(n) = 1 + n + 2n²。

当 n = 5 时，f(n) = 1 + 5 + 2 × 25。 当 n = 10000 时，f(n) = 1 + 10000 + 2 × 100000000。

注意到了吗？很明显可以看出，n² 对程序运行次数起到了决定性作用。

反倒是常数 1 和系数 2 对最终趋势影响不大，可以忽略。因此：

分析一段代码的时间复杂度时，优先找出执行次数随 n 增长最快的那一段代码。

所以得到下面的结果：

表达式大 $O$ 类型n = 10n = 100n = 1000特点
1 + 2nO(n) 线性212012001随 n 等比例增长
1 + n + 2n²O(n²) 平方211201012001001随 n 平方增长

大 $O$ 时间复杂度并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。复杂度分析通常遵循以下原则：

  • 复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示同样的复杂度。
  • 多项式复杂度相加时，保留增长更快的项，例如 O(n²) + O(n) = O(n²)。

我们再看下面代码：

def dogeggs_sum (n):
    sum1 = 0
    for dogegg1 in range(n):
        sum1 += dogegg1

    sum2 = 0
    for dogegg2 in range(n):
        for i in range(n):
            sum2 += dogegg2 * i

    sum3 = 0
    for dogegg3 in range(n):
        for i in range(n):
            for j in range(n):
                sum3 += dogegg3 * i * j

    return sum1 + sum2 + sum3

根据上面学习的知识：

这段代码的 T(n) = O(n) + O(n²) + O(n³)，按照我们取“主导”部分，显然前面两个都不及第三个，所以 T(n) = O(n³)。

身下的我们就是要多去练习找一下时间复杂度，加强记忆即可。

常见时间复杂度

算法学习过程中，我们会遇到各种各样的时间复杂度，当常见的时间复杂度都在下面之列：

复杂度名称增长特点典型例子
O(1)常数复杂度输入再大，操作次数不变取数组第 k 个元素；简单加减赋值
O(log n)对数复杂度n 翻倍，只多固定几步，增长极慢从 1 开始每次乘 2
O(n)线性复杂度操作数和 n 成正比遍历一次数组，单循环
O(n log n)线性对数比线性慢、比平方快归并排序、快速排序（平均）
O(n²)平方复杂度n 扩大 10 倍，工作量 ×100双层 for 循环，冒泡排序
O(n³)立方复杂度n 扩大 10 倍，工作量 ×1000三层嵌套循环
O(2ⁿ)指数复杂度n 稍微增加，计算量爆炸暴力枚举全部子集；朴素递归求斐波那契
O(n!)阶乘复杂度比指数增长更快，n 很小就跑不动全排列暴力枚举

其中复杂度大小比较：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

下面每个复杂度我们看一下。例子都按同一件事来写，方便对照循环是怎么把规模抬上去的。

O(1) 常数：按下标取值

注意这是一个特殊的复杂度，不是只执行一次的代码时间复杂度就是 O(1)，只要你说常熟，像O(2),O(3),O(1000)在复杂度上的表示都是 O(1)。

def get_kth(nums, k):
  return nums[k]

数组按下标取值，不管里面有 10 个数还是 1000 万个数，都只做一次。没有跟着 n 走的循环，所以是常数复杂度。k 必须落在下标范围内。

O(log n) 对数：每次翻倍

dogegg 从 1 开始，每次乘 2，直到不小于 n。循环转几圈，就是 log2(n)。

def dogegg_double(n):
  dogegg = 1              # 从 1 开始

  while dogegg < n:       # 还没长到 n，就再乘一次 2
    dogegg = dogegg * 2   # 1 → 2 → 4 → 8，圈数就是 log2(n)
  return dogegg

dogegg 的变化是 1 → 2 → 4 → 8 → …。每转一圈就多乘一个 2，停下来时，是 x 个 2 连乘，结果不小于 n：

2 × 2 × … × 2 >= n

这 x 个 2 连乘，就是 2 的 x 次方对应 n：

2ˣ >= n

两边取以 2 为底的对数，圈数就是：

x = log2(n)

n 正好是 2 的整数次方时等号成立。对不齐时，x 比 log2(n) 略大，向上取整，趋势不变。

  • n = 8：2 × 2 × 2 = 8，x = 3，也就是 log2(8) = 3
  • n 大约 1000：2¹⁰ = 1024，x 大约 10
  • n 大约 100 万：2²⁰ ≈ 104万，x 大约 20

n 从 1000 涨到 100 万，圈数只从大约 10 变成大约 20。底数是 2 还是 10 不用写进大 O，换底只差一个固定倍数，固定倍数会被抹掉，所以写成 O(log n)。

O(n) 线性：找最大值

每个元素都要看一眼，看完一遍就是 O(n)。数据量翻倍，比较次数也大约翻倍。下面默认数组里至少有一个数。

def find_max(nums):
  best = nums[0]
  for x in nums:
    if x > best:
      best = x
  return best

O(n log n) 线性对数：归并排序

先把数组对半拆开，拆到底再两两合并。拆分大约有 log n 层，每一层都要把 n 个数扫一遍，合起来就是 O(n log n)。归并排序每次都是这个量级。

def merge_sort(nums):
  if len(nums) <= 1:
    return nums
  mid = len(nums) // 2
  left = merge_sort(nums[:mid])
  right = merge_sort(nums[mid:])
  merged = []
  i = j = 0
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      merged.append(left[i])
      i += 1
    else:
      merged.append(right[j])
      j += 1
  merged.extend(left[i:])
  merged.extend(right[j:])
  return merged

O(n²) 平方：冒泡排序

相邻两个数比大小，较大的往后换。外层走 n 轮，内层每一轮也跟着 n 走，所以是平方复杂度。n 扩大 10 倍，比较次数大约变成 100 倍。下面的实现会改原数组。

def bubble_sort(nums):
  n = len(nums)
  for i in range(n):
    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(n³) 立方：朴素矩阵乘法

两个 n×n 的矩阵相乘，结果里一共有 n² 个格子，每个格子都要做 n 次乘加。三层循环套在一起，就是 O(n³)。n 扩大 10 倍，工作量大约变成 1000 倍。

def multiply(a, b):
  n = len(a)
  c = [[0] * n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        c[i][j] += a[i][k] * b[k][j]
  return c

O(2ⁿ) 指数：朴素递归斐波那契

fib(n) 要先算出 fib(n - 1) 和 fib(n - 2)，同一次调用会拆成两支。n 每增加 1，调用次数大约翻倍，所以是指数复杂度。教材里常写成 O(2ⁿ)。n 稍微大一点就慢到不能用，它只适合拿来看增长趋势。

def fib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

O(n!) 阶乘：全排列

n 个互不相同的元素，第一个位置有 n 种选法，第二个位置剩 n − 1 种，一直乘到 1。路径总数就是 n!。n = 10 已经是三百多万，n = 12 接近 5 亿，所以只能枚举很小的 n。

def permutations(nums):
  result = []
  used = [False] * len(nums)
  path = []

  def dfs():
    if len(path) == len(nums):
      result.append(path[:])
      return
    for i in range(len(nums)):
      if used[i]:
        continue
      used[i] = True
      path.append(nums[i])
      dfs()
      path.pop()
      used[i] = False

  dfs()
  return result

平均复杂度

除了数据规模，输入数据的具体情况也会影响算法的运行时间。

我们来看这么一段代码：

def find_word(lst, word):
  flag = -1

  for i in range(len(lst)):
    if lst[i] == word:
      flag = i
      break

  return flag

上面这段代码用于查找变量 word 在列表 lst 中出现的位置，可以用来解释“数据的具体情况”是什么意思。

拿 lst = ['a', 'b', 'c', 'd'] 来数一遍。循环碰到 word 就 break，所以比几次完全看 word 落在哪：

word停在哪循环次数
'a'第 1 个就命中1
'b'第 2 个命中2
'c'第 3 个命中3
'd'最后一个才命中4
'e'列表里没有，只能走完4
  • 第 1 个就命中时，后面都不用看，这是最好情况，时间复杂度是 O(1)。
  • word 在末尾，或者像 'e' 这样根本不在列表里，都要把整个列表走完，这是最坏情况，时间复杂度是 O(n)。

这就是数据具体情况不同，代码的时间复杂度不同。我们得出下面 3 种情况：

  • 最好时间复杂度（Best Case）：最理想情况下的复杂度，例如 word 恰好是列表 lst 的第 1 个元素，对应 O(1)。
  • 最坏时间复杂度（Worst Case）：最差情况下的复杂度，例如 word 在列表末尾或不存在，对应 O(n)。
  • 平均时间复杂度（Average Case）：综合各种输入情况及其发生概率得到的期望复杂度。

那么怎么计算平均时间复杂度呢？需要用到概率论的知识。

我们仍然用上面的例子来说明：

  • 从整体看，查找变量 x 在列表 lst 中的位置有两种情况：存在或不存在。假设两种情况的概率都是 1/2。
  • 如果 x 出现在列表 lst 中，那么它可能出现在 0 到 n - 1 的任意位置，假设每个位置的概率都相同，都是 1/n。

每个出现的概率（即权重）知道了，所以平均时间复杂度为：

“在列表里”的概率是 1/2，这一半还要再平分给 n 个位置，所以 x 落在某个具体位置的概率是 1/2 × 1/n = 1/(2n)；不在列表里的概率仍然是 1/2。

落在第 1 个位置要循环 1 次，第 2 个位置要循环 2 次，一直到第 n 个位置要循环 n 次；不在列表里也要循环 n 次。平均循环次数就是这些情况的加权和：

平均循环次数是这些情况的加权和：

$$ \begin{aligned} T(n) &= \frac{1}{2n} + \frac{2}{2n} + \cdots + \frac{n}{2n} + \frac{n}{2} \ &= \frac{1 + 2 + \cdots + n}{2n} + \frac{n}{2} \ &= \frac{n(n + 1)}{4n} + \frac{n}{2} \ &= \frac{3n + 1}{4} \end{aligned} $$

在 (3n + 1) / 4 中，系数 3/4 和常数 1/4 都不改变增长趋势，所以平均时间复杂度是 O(n)。

大多数情况下优先关注最坏时间复杂度，因为它能帮助我们评估算法性能的下限。

空间复杂度

空间复杂度和时间复杂度一样，关注的是增长趋势；它描述代码运行过程中额外占用的内存空间。

代码在计算机中运行所占用的存储空间主要分为 3 部分：

  • 代码本身所占用的
  • 输入数据所占用的
  • 临时变量所占用的

前面两个部分是本身就要占用这些空间，与代码性能无关，所以我们在衡量代码的空间复杂度时，只关心运行过程中临时占用的内存空间。

空间复杂度记作 S(n)，表达形式与时间复杂度一样：

$$ S(n) = O(f(n)) $$

这里 n 表示数据集大小，f(n) 表示规模 n 对应的存储空间函数。

我们用下面代码来学习如何分析空间复杂度：

def dogeggs_sum(lst):
  sum = 0

  for i in range(len(lst)):
    sum += lst[i]

  return sum

上述代码用于求列表 lst 的所有元素之和。根据前面的约定，这里只计算临时变量占用的额外空间。

形参 lst 所占用的空间不计，那么剩下的临时变量只有 sum 和 i。它们都是常数阶，与规模 n 无关，因此整段代码的空间复杂度是 S(n) = O(1)。

常见空间复杂度

常见的空间复杂度和时间复杂度类似，也可以按照增长速度从小到大排列：

O(1) < O(log n) < O(n) < O(n²)

除非题目特别说明，算法题里说的空间复杂度通常指额外空间复杂度，也就是不计算输入数据本身所占的空间。是否计算返回结果，要看题目讨论的是辅助空间还是总空间。
复杂度名称典型情况文章中的例子
O(1)常数空间只使用固定数量的变量，额外空间不随 n 增长求和、原地冒泡排序
O(log n)对数空间递归调用每次把问题规模缩小一半，调用栈深度是 log n归并排序的递归调用栈
O(n)线性空间临时数组、递归调用栈或辅助结构的大小和 n 成正比归并排序的临时数组、全排列的 path
O(n²)平方空间需要保存 n × n 规模的表格或结果矩阵乘法的结果矩阵

下面分别看这些空间复杂度是怎么产生的。

O(1) 常数空间：只保存固定数量的变量

前面的 dogeggs_sum(lst) 只使用了 sum 和 i 两个临时变量。无论列表里有 10 个元素还是 1000 万个元素，这两个变量占用的空间都不会随 n 增长，所以空间复杂度是 O(1)。

前面的冒泡排序也是 O(1) 额外空间：它只使用了 n、i、j 和交换时的 tmp。虽然时间复杂度是 O(n²)，但它直接在原数组上交换元素，没有另建一个和 n 一样大的数组，所以空间复杂度仍然是 O(1)。

这里要注意“输入数据所占用的空间”和“额外空间”的区别。冒泡排序输入的数组本身可能有 n 个元素，但那是调用者已经提供的输入空间，通常不计入这段算法的额外空间复杂度。

O(log n) 对数空间：递归调用栈

归并排序每次把数组分成两半。虽然递归调用总共会处理 n 个元素，但沿着其中一条递归路径，规模是：

n → n / 2 → n / 4 → ... → 1

因此递归深度是 O(log n)。如果只计算递归调用栈，不计算合并时创建的临时数组，那么归并排序的栈空间是 O(log n)。

下面这个函数每次把 n 除以 2，直到 n 不大于 1。它没有创建和 n 相关的数组，但递归调用栈最多有 log n 层，所以额外空间复杂度是 O(log n)。

def halve_count(n):
  if n <= 1:
    return 1
  return 1 + halve_count(n // 2)

不过，文章中的归并排序实现还会创建 left、right 和 merged 等数组。它们在同一层合计最多保存 O(n) 个元素，所以整个实现的额外空间复杂度应记为 O(n)，而不是只看递归栈写成 O(log n)。

O(n) 线性空间：辅助数组或线性递归

参考下面的代码，result 每循环一次就多保存一个元素，最多保存 n 个元素，因此额外空间复杂度是 O(n)。

def create_list(n):
  result = []
  for i in range(n):
    result.append(i)
  return result

文章中的归并排序需要一个和输入规模相近的 merged 数组，因此额外空间是 O(n)。这也是归并排序和原地排序的一个重要区别：它用更多空间换取了稳定且规整的排序过程。

前面的全排列代码也会使用线性空间保存当前状态：

  • used 数组需要保存 n 个布尔值，是 O(n)。
  • path 最深时保存 n 个元素，是 O(n)。
  • 递归调用栈最多有 n 层，是 O(n)。

所以，如果不把最终返回的 result 计算在内，全排列的辅助空间复杂度是 O(n)。但是这段代码会把所有排列都保存下来，结果本身有 n! 个排列，每个排列长度为 n，因此返回结果占用的空间是 O(n × n!)。是否把输出结果计入空间复杂度，要看题目讨论的是“辅助空间”还是“总空间”。

朴素递归斐波那契也是一个容易混淆的例子。它的时间复杂度接近 O(2ⁿ)，但同一时刻沿着一条递归路径最多只有 n 层调用，所以调用栈空间是 O(n)。时间增长很快，并不代表空间也一定是指数增长。

O(n²) 平方空间：保存二维数据

下面的代码先创建 n 个一维列表，再让每个列表保存 n 个元素。最终得到的是一个 n × n 的二维列表，需要保存 n² 个元素，所以空间复杂度是 O(n²)。

def create_matrix(n):
  matrix = []
  for i in range(n):
    row = []
    for j in range(n):
      row.append(j)
    matrix.append(row)
  return matrix

前面的矩阵乘法创建了结果矩阵 c：它有 n 行、每行 n 个元素，所以需要保存 n² 个元素，空间复杂度是 O(n²)。

如果题目只计算“除输出以外的辅助空间”，那么可以把已经返回的结果矩阵 c 排除，此时三层循环本身只使用 i、j、k 等固定数量的变量，辅助空间是 O(1)。但如果讨论算法运行期间占用的总空间，或者把输出空间也算进去，就应写成 O(n²)。

如何分析空间复杂度

分析空间复杂度时，可以按下面的顺序检查：

找出随规模增长的数据结构

检查代码中新建的数组、列表、哈希表或矩阵，并判断它们的大小是否随着 n 增长。

计算递归调用栈

找出递归函数，计算一条递归路径上最多同时存在多少层调用。

确认是否计算输出空间

判断题目是否把返回结果计入空间复杂度。没有特别说明时，通常讨论的是额外空间复杂度。

合并同时存在的空间

同一时间同时存在的空间取总和；不同阶段先后使用、不会同时存在的空间，取占用量最大的阶段。

求和和原地冒泡排序是 O(1)；归并排序整体是 O(n)；全排列的辅助空间是 O(n)，但保存全部结果时是 O(n × n!)；矩阵乘法包含输出矩阵时是 O(n²)。空间复杂度的关键不是数循环执行了多少次，而是看运行过程中同时保存了多少与 n 有关的数据。

算法学习

数据结构、复杂度与经典题的学习笔记。

Copyright © 2026