时间 / 空间复杂度

Mr.xupengboo2025年2月14日大约 3 分钟

1. 什么是时间/空间复杂度？

时间复杂度和空间复杂度是用于时间复杂度和空间复杂度是用于评估算法效率的两个重要指标，它们帮助我们量化算法在不同输入规模下的资源消耗情况。，它们帮助我们量化算法在不同输入规模下的资源消耗情况。

总结

示例：

# O(n) 时间复杂度：遍历长度为 n 的数组
for num in array:
    print(num)

# O(n²) 时间复杂度：双重循环
for i in range(n):
    for j in range(n):
        print(i, j)

定义：表示算法运行所需的额外内存空间与输入规模 n 的增长关系。
核心思想：计算算法使用的 额外存储空间 （不包括输入数据本身占用的空间）。
常见类型：
- O(1)：常数空间。仅使用固定数量的变量（如交换两个数的值）。
- O(n)：线性空间。额外空间与 n 成正比（如复制一个数组）。
- O(n²)：平方空间。额外空间与 n² 成正比（如二维矩阵的生成）。

示例：

# O(1) 空间复杂度：交换两个变量
a, b = b, a

# O(n) 空间复杂度：生成一个长度为 n 的数组
new_array = [0] * n

我们希望算法既高效（时间复杂度低）又节省空间（空间复杂度低），但实际上这两者往往是对立的。当优化其中一个时，往往会导致另一个方面的开销增加。因此，理解和应对这种权衡是设计高效算法的重要技巧。

空间换时间：使用更多的内存来加速计算。

时间换空间：通过减少内存使用来降低计算效率。

典型案例

哈希表是一种典型的通过空间换时间的结构。它可以在常数时间内进行插入、删除和查找操作，即时间复杂度为 O(1)，但它需要额外的空间来存储哈希表中的数据。

递归算法往往需要大量的栈空间来保存每次递归的状态，尤其是递归深度较大时。递归可以显著简化代码，但它可能导致空间消耗的增加。