数据结构与算法 / 系统课时

时间复杂度的基本概念

时间复杂度的基本概念

学习目标

  • 理解时间复杂度描述的是操作次数随输入规模增长的趋势。
  • 掌握 O(1)、O(log n)、O(n)、O(n log n) 和 O(n²) 的基本含义。
  • 能根据顺序语句、循环、嵌套循环和范围缩减判断复杂度。
  • 区分理论复杂度、实际耗时和性能测试之间的关系。
  • 输入规模
    • 数组长度
    • 节点数量
    • 字符串长度
    • 图的顶点和边
  • 基本操作
    • 比较
    • 赋值
    • 访问
    • 交换
  • 渐进复杂度
    • O(1)
    • O(log n)
    • O(n)
    • O(n log n)
    • O(n²)
    • O(2ⁿ)
  • 分析规则
    • 常数忽略
    • 低阶项忽略
    • 顺序执行取最大阶
    • 嵌套执行通常相乘
    • 分支取主要或最坏路径
  • 工程理解
    • 理论增长趋势
    • 常数开销
    • 数据分布
    • 硬件与语言实现

问题背景或应用场景

假设需要在一组数据中查找目标值。线性查找会从第一个元素开始逐个比较。如果数据有一百万个元素,最坏情况下需要进行一百万次比较。

二分查找每次检查中间元素,并排除一半搜索范围。如果数据有序,一百万个元素大约只需要二十次比较。

两种算法都能得到正确结果,但随着数据规模增大,执行成本增长方式完全不同。实际运行时间会受到以下因素影响:

  • CPU 性能。
  • 内存速度。
  • 编程语言。
  • 编译器或解释器优化。
  • 操作系统调度。
  • 输入数据分布。
  • 缓存命中情况。
  • 当前机器负载。

因此,不能只用某次运行的毫秒数描述算法本身。时间复杂度提供了一种更稳定的理论分析方式。

核心原理

1. 输入规模是什么

时间复杂度中的 n 表示输入规模,但 n 的含义取决于问题。例如:

  • 数组算法中,n 通常表示元素数量。
  • 字符串算法中,n 通常表示字符数量。
  • 树算法中,n 通常表示节点数量。
  • 图算法中,可能同时使用顶点数 V 和边数 E。
  • 矩阵算法中,可能使用行数 m 和列数 n。

在分析之前,必须先明确 n 代表什么。

2. 选择基本操作

时间复杂度通常不逐条统计所有机器指令,而是选择能代表主要成本的基本操作。常见基本操作包括:

  • 比较两个值。
  • 访问一个元素。
  • 交换两个元素。
  • 执行一次循环体。
  • 处理一个节点。
  • 检查一条边。

例如,分析查找算法时,可以统计比较次数。

3. 大 O 表示增长上界

如果操作次数为:

text
3n² + 5n + 20

当 n 很大时:

  • n² 项增长最快。
  • 3 是常数系数。
  • 5n 和 20 相比 n² 增长更慢。

因此,复杂度写为:

text
O(n²)

大 O 关注增长数量级,而不是精确操作次数。

4. 常见复杂度

O(1):常数复杂度

执行次数不随输入规模增长。例如,根据已知索引读取数组元素。

python
def first_value(values: list[int]) -> int:
    return values[0]

即使数组从 10 个元素增加到 100 万个元素,读取第一个位置仍是固定操作。

O(log n):对数复杂度

每一步把问题规模缩小为固定比例。二分查找每次将搜索范围缩小一半,因此是 O(log n)。

O(n):线性复杂度

处理每个元素一次。

python
def total(values: list[int]) -> int:
    result = 0

    for value in values:
        result += value

    return result

元素数量翻倍,操作次数大致也翻倍。

O(n log n):线性对数复杂度

常见于归并排序、堆排序以及平均情况下的高效比较排序。

可以理解为:需要处理 n 个元素,同时存在 log n 层的分解或合并。

O(n²):平方复杂度

常见于两个都与 n 相关的嵌套循环。

python
def print_pairs(values: list[int]) -> None:
    for first in values:
        for second in values:
            print(first, second)

元素数量翻倍,操作次数大约变为四倍。

O(2ⁿ):指数复杂度

常见于没有剪枝的组合枚举或某些递归算法。输入规模稍大时,成本会快速失控。

5. 顺序执行的分析规则

如果一段代码先执行 O(n),再执行 O(n²),总复杂度为:

text
O(n + n²)

忽略低阶项后得到:

text
O(n²)

6. 嵌套循环的分析规则

如果外层循环执行 n 次,内层循环每次也执行 n 次,总次数为:

text
n × n = n²

复杂度为 O(n²)。但嵌套循环不一定都是 O(n²)。如果内层循环每次只执行固定次数,总体仍可能是 O(n)。

7. 循环变量变化决定复杂度

下面循环每次加 1:

python
index = 0

while index < n:
    index += 1

执行 n 次,因此为 O(n)。下面循环每次乘 2:

python
value = 1

while value < n:
    value *= 2

执行次数约为 log₂n,因此为 O(log n)。

基础用法

示例一:固定次数操作

python
def get_ends(values: list[int]) -> tuple[int, int]:
    return values[0], values[-1]

无论列表多长,都只读取两个位置,因此为 O(1)。

示例二:单层遍历

python
def contains_negative(values: list[int]) -> bool:
    for value in values:
        if value < 0:
            return True

    return False

最坏情况下需要检查全部元素,因此为 O(n)。

示例三:两段顺序循环

python
def print_twice(values: list[int]) -> None:
    for value in values:
        print(value)

    for value in values:
        print(value)

操作次数约为 2n,忽略常数后为 O(n)。

示例四:三角形循环

python
def print_upper_pairs(values: list[int]) -> None:
    for first in range(len(values)):
        for second in range(first + 1, len(values)):
            print(values[first], values[second])

虽然内层循环次数逐渐减少,但总次数仍与 n² 同阶,因此为 O(n²)。

完整可运行示例

python
from collections.abc import Sequence

def linear_search(
    values: Sequence[int],
    target: int,
) -> tuple[int, int]:
    comparisons = 0

    for index, value in enumerate(values):
        comparisons += 1

        if value == target:
            return index, comparisons

    return -1, comparisons

def binary_search(
    values: Sequence[int],
    target: int,
) -> tuple[int, int]:
    left = 0
    right = len(values) - 1
    comparisons = 0

    while left <= right:
        middle = left + (right - left) // 2
        comparisons += 1
        value = values[middle]

        if value == target:
            return middle, comparisons

        if value < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1, comparisons

def compare_for_size(size: int) -> None:
    values = list(range(1, size + 1))
    target = size

    linear_index, linear_count = linear_search(values, target)
    binary_index, binary_count = binary_search(values, target)

    print(
        f"size={size}, "
        f"linear=({linear_index}, {linear_count}), "
        f"binary=({binary_index}, {binary_count})"
    )

def main() -> None:
    compare_for_size(16)
    compare_for_size(128)
    compare_for_size(1024)
    compare_for_size(1_048_576)

if __name__ == "__main__":
    main()

运行命令:

bash
python lesson_01_03.py

预期输出

text
size=16, linear=(15, 16), binary=(15, 5)
size=128, linear=(127, 128), binary=(127, 8)
size=1024, linear=(1023, 1024), binary=(1023, 11)
size=1048576, linear=(1048575, 1048576), binary=(1048575, 21)

结果分析

当数据规模从 16 增加到 1,048,576 时:

  • 线性查找比较次数从 16 增加到 1,048,576。
  • 二分查找比较次数从 5 增加到 21。

这说明:

  • 线性查找的操作次数与 n 同阶增长。
  • 二分查找的操作次数与 log n 同阶增长。
  • 数据规模越大,增长趋势差异越明显。

但二分查找有前提:数据必须有序。如果数据原本无序,还需要考虑排序成本。

Tips

  • 时间复杂度不是精确运行时间。
  • 大 O 关注输入规模趋大时的增长趋势。
  • 必须先定义 n 的含义。
  • 必须选择合适的基本操作。
  • 顺序执行通常相加,最后保留最高阶。
  • 嵌套循环通常相乘,但要看每层实际次数。
  • 每次将范围减半通常对应 O(log n)。
  • 二分查找要求输入有序。
  • 相同复杂度的算法仍可能有不同常数开销。
  • 对小规模数据,简单算法可能更实用。
  • 理论分析和基准测试应结合使用。
  • 性能测试应预热、多次运行并控制环境变量。
  • 不要用一次偶然耗时证明算法复杂度。

常见错误

错误一:看到一层循环就直接判断为 O(n)

如果循环变量每次乘 2,复杂度可能是 O(log n)。

错误二:看到两层循环就直接判断为 O(n²)

需要分析每层执行次数。固定次数内层循环不会使复杂度变成 O(n²)。

错误三:保留常数系数

O(2n) 应化简为 O(n)。

错误四:保留低阶项

O(n² + n + 1) 应化简为 O(n²)。

错误五:只分析主函数,忽略被调用函数

如果循环内部调用了一个 O(n) 函数,总复杂度可能上升为 O(n²)。

错误六:忽略前置成本

对无序数据使用二分查找之前,需要先排序。排序成本不能忽略。

错误七:把最好情况当成整体复杂度

查找首元素可能是 O(1),但最坏情况下仍可能是 O(n)。

错误八:用代码行数判断复杂度

代码行数少不代表运行成本低,代码行数多也不一定复杂度高。

本课练习

  1. 判断读取数组第一个元素的复杂度。
  2. 判断遍历数组求和的复杂度。
  3. 判断两个连续遍历的复杂度。
  4. 判断两个完整嵌套循环的复杂度。
  5. 判断循环变量每次乘 3 的复杂度。
  6. 编写一个 O(1) 函数。
  7. 编写一个 O(n) 函数。
  8. 编写一个 O(log n) 循环。
  9. 编写一个 O(n²) 函数。
  10. 分析以下操作次数:
    • 3n + 10。
    • n² + 100n。
    • n log n + n。
    • 5。
  11. 修改示例,将目标值改为第一个元素,观察最好情况。
  12. 修改示例,将目标值改为不存在的元素,观察最坏情况。
  13. 思考无序列表只查询一次时,是否值得先排序再二分查找。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

时间复杂度的基本概念

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通