数据结构与算法 / 系统课时
时间复杂度的基本概念
时间复杂度的基本概念
学习目标
- 理解时间复杂度描述的是操作次数随输入规模增长的趋势。
- 掌握 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 表示增长上界
如果操作次数为:
3n² + 5n + 20当 n 很大时:
- n² 项增长最快。
- 3 是常数系数。
- 5n 和 20 相比 n² 增长更慢。
因此,复杂度写为:
O(n²)大 O 关注增长数量级,而不是精确操作次数。
4. 常见复杂度
O(1):常数复杂度
执行次数不随输入规模增长。例如,根据已知索引读取数组元素。
def first_value(values: list[int]) -> int:
return values[0]即使数组从 10 个元素增加到 100 万个元素,读取第一个位置仍是固定操作。
O(log n):对数复杂度
每一步把问题规模缩小为固定比例。二分查找每次将搜索范围缩小一半,因此是 O(log n)。
O(n):线性复杂度
处理每个元素一次。
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 相关的嵌套循环。
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²),总复杂度为:
O(n + n²)忽略低阶项后得到:
O(n²)6. 嵌套循环的分析规则
如果外层循环执行 n 次,内层循环每次也执行 n 次,总次数为:
n × n = n²复杂度为 O(n²)。但嵌套循环不一定都是 O(n²)。如果内层循环每次只执行固定次数,总体仍可能是 O(n)。
7. 循环变量变化决定复杂度
下面循环每次加 1:
index = 0
while index < n:
index += 1执行 n 次,因此为 O(n)。下面循环每次乘 2:
value = 1
while value < n:
value *= 2执行次数约为 log₂n,因此为 O(log n)。
基础用法
示例一:固定次数操作
def get_ends(values: list[int]) -> tuple[int, int]:
return values[0], values[-1]无论列表多长,都只读取两个位置,因此为 O(1)。
示例二:单层遍历
def contains_negative(values: list[int]) -> bool:
for value in values:
if value < 0:
return True
return False最坏情况下需要检查全部元素,因此为 O(n)。
示例三:两段顺序循环
def print_twice(values: list[int]) -> None:
for value in values:
print(value)
for value in values:
print(value)操作次数约为 2n,忽略常数后为 O(n)。
示例四:三角形循环
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²)。
完整可运行示例
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()运行命令:
python lesson_01_03.py预期输出
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)。
错误八:用代码行数判断复杂度
代码行数少不代表运行成本低,代码行数多也不一定复杂度高。
本课练习
- 判断读取数组第一个元素的复杂度。
- 判断遍历数组求和的复杂度。
- 判断两个连续遍历的复杂度。
- 判断两个完整嵌套循环的复杂度。
- 判断循环变量每次乘 3 的复杂度。
- 编写一个 O(1) 函数。
- 编写一个 O(n) 函数。
- 编写一个 O(log n) 循环。
- 编写一个 O(n²) 函数。
- 分析以下操作次数:
- 3n + 10。
- n² + 100n。
- n log n + n。
- 5。
- 修改示例,将目标值改为第一个元素,观察最好情况。
- 修改示例,将目标值改为不存在的元素,观察最坏情况。
- 思考无序列表只查询一次时,是否值得先排序再二分查找。