定义
- 时间复杂度: 衡量一个算法执行时间随输入数据规模增长而变化的趋势。它描述的是算法执行基本操作的次数，通常用大 O 表示法来表示，关注算法的渐进性能。
- 空间复杂度: 衡量一个算法在执行过程中所需存储空间随输入数据规模增长而变化的趋势。它描述的是算法在运行过程中临时占用存储空间的大小，同样常用大 O 表示法表示。
核心特点
- 时间复杂度: - 关注算法的 ” 快慢 “，即计算效率。 - 与 CPU 的计算能力、指令执行次数相关。 - 通常分析最好、最坏、平均三种情况。
- 空间复杂度: - 关注算法的 ” 内存占用 “，即资源消耗。 - 与内存、硬盘等存储资源的使用相关。 - 包括算法本身、输入数据、辅助变量等占用的空间。
分类
两者都使用大 O 表示法进行分类，常见的复杂度类型包括：
- O(1): 常数复杂度（时间或空间）
- O(log n): 对数复杂度
- O(n): 线性复杂度
- O(n log n): 线性对数复杂度
- O(n^2): 平方复杂度
- O(2^n): 指数复杂度
- O(n!): 阶乘复杂度
应用
- 算法设计与选择: 在设计或选择算法时，需要综合考虑时间和空间复杂度，以满足特定场景的性能要求。
- 系统资源优化: 针对时间敏感型应用，优先优化时间复杂度；针对内存受限型应用，优先优化空间复杂度。
- 性能瓶颈分析: 通过分析算法的时间和空间复杂度，可以预判潜在的性能瓶颈，并进行针对性优化。
优缺点
- 优点: - 提供量化标准，便于比较不同算法的效率和资源消耗。 - 帮助预测算法在处理大规模数据时的行为。 - 指导算法设计者进行性能优化和资源规划。
- 缺点: - 大 O 表示法忽略常数因子和低阶项，可能导致在小规模数据下与实际运行情况有偏差。 - 实际运行时间/空间还受硬件、编程语言、编译器等多种因素影响。 - 仅关注渐进趋势，不代表绝对速度或绝对内存占用。
- 对比/区别: - 关注点不同: 时间复杂度关注算法执行所需的时间资源，空间复杂度关注算法执行所需占用的存储空间资源。 - 资源类型不同: 时间对应 CPU 计算周期，空间对应内存/硬盘存储。 - 权衡关系: 很多时候，时间和空间是相互制约的。例如，通过增加存储空间（空间换时间）来减少计算时间，或通过增加计算时间（时间换空间）来减少内存占用。
相关概念
- 时间复杂度分析: 详细解释时间复杂度的定义、计算方法和常见类型。
- 空间复杂度分析: 详细解释空间复杂度的定义、计算方法和常见类型。
- 大O表示法: 描述函数渐进上界的一种数学符号，是表示时间和空间复杂度的标准方法。
- 算法效率: 衡量算法性能的综合指标，包括时间效率和空间效率。
案例
- 时间换空间: - 哈希表: 通过额外的空间存储键值对，实现 的平均查找时间。 - 动态规划: 通过存储子问题的解（DP 表），避免重复计算，从而降低时间复杂度。
- 空间换时间: - 递归转迭代: 某些递归算法（如斐波那契数列）会占用大量栈空间，转换为迭代可以减少空间复杂度，但可能增加代码复杂性或时间常数。 - 原地排序算法: 如冒泡排序、选择排序，它们在排序过程中只使用常数级别的额外空间 ()，但时间复杂度通常较高 ()。
问答卡片
- Q1：时间复杂度和空间复杂度分别衡量什么？
- A：时间复杂度衡量算法执行时间随输入规模增长的趋势（计算效率），空间复杂度衡量算法执行所需存储空间随输入规模增长的趋势（资源消耗）。
- Q2：为什么在算法设计中需要权衡时间和空间复杂度？
- A：因为在许多情况下，优化时间复杂度可能会增加空间复杂度，反之亦然。开发者需要根据具体的应用场景和资源限制，选择最合适的权衡方案。
- Q3：举例说明 ” 空间换时间 ” 和 ” 时间换空间 ” 的场景。
- A：空间换时间：使用哈希表通过额外空间实现快速查找；时间换空间：原地排序算法通过增加计算时间来减少内存占用。
参考资料
- 《算法导论》
- 《数据结构与算法分析》
- 维基百科：时间复杂度
- 维基百科：空间复杂度
- GeeksforGeeks: Space Complexity