1. 概述
对于同一个问题，通常会有多种不同的解决方案。但算法研究人员的目标是找到一个执行时间更短、占用内存更少的解决方案。
在计算机科学中，解决方案最终会转化为程序代码。因此，衡量一个算法优劣的重要指标，就是它对资源的消耗。这里的资源主要指的是：
- CPU执行时间（时间复杂度）
- 内存使用空间（空间复杂度）
这两个指标共同决定了一个算法的效率和实用性。
在本教程中，我们将分别定义时间复杂度与空间复杂度，介绍它们的计算方法，并通过示例进行说明。最后，我们还将对比两者之间的核心区别。
2. 什么是时间复杂度？
时间复杂度是衡量算法执行所需时间的度量标准。 它描述了算法中每条语句执行时间的总和，主要受输入数据规模的影响。
时间复杂度是一个渐近函数，通常使用Landau记号表示，包括：
O（大O符号）：表示最坏情况下的时间复杂度Ω（欧米伽符号）：表示最好情况下的时间复杂度Θ（西塔符号）：表示平均情况下的时间复杂度
例如：
- 常数时间复杂度：
O(1) - 线性时间复杂度：
O(n) - 对数时间复杂度：
O(log n) - 线性对数时间复杂度：
O(n log n)
这些不同复杂度反映了算法在处理不同规模数据时的性能表现。
3. 时间复杂度的计算方法
我们以一个简单的阶乘计算函数为例，来看如何计算时间复杂度：
1. fact ← 1
2. i ← 2
3. while i ≤ n do
4. fact ← fact * i
5. i ← i + 1
6. end while
我们逐行分析其执行时间：
- 第1、2行：执行一次，复杂度为
O(1) - 第3行是循环控制语句，循环体（第4、5行）执行
n-1次 - 因此，第4、5行的复杂度为
O(n)
将所有语句的复杂度相加，最终整个算法的时间复杂度为：
✅ T(n) = O(n)
这种逐行分析的方法称为迭代法。除此之外，还有：
- 递归法：适用于递归算法，常通过递归树或代入法分析
- 主定理（Master Theorem）：用于快速分析分治算法的时间复杂度
4. 什么是空间复杂度？
空间复杂度是衡量算法运行过程中所需内存空间的度量标准。 它包括：
- 输入数据所占空间
- 辅助变量所占空间（临时变量、函数调用栈等）
例如：
- 选择排序：空间复杂度为
O(1)，因为它在原数组上操作，不需要额外空间 - 归并排序：空间复杂度为
O(n)，因为它需要创建多个临时数组来存储分割后的数据
空间复杂度同样使用 O 表示法进行评估。
5. 空间复杂度的计算方法
我们以一个数组求和函数为例：
1. int sum, i
2. while i ≤ n do
3. sum ← sum + a[i]
4. i ← i + 1
5. end while
6. return sum
逐行分析其空间占用：
- 第1行：定义两个整型变量，占用
2 × 4 = 8字节 - 第6行：返回值需要额外分配
4字节 - 数组
a占用n × 4字节（假设int占4字节）
因此，总的空间复杂度为：
✅ S(n) = 4n + 12，简化后为：
✅ S(n) = O(n)
6. 时间复杂度 vs. 空间复杂度
| 对比维度 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 衡量对象 | 算法执行所需时间 | 算法执行所需内存空间 |
| 影响因素 | 输入数据规模 | 辅助变量数量 |
| 计算重点 | 所有语句的执行时间 | 所有变量的内存占用 |
| 实际重要性 | ✅ 更重要（现代硬件内存充足） | ❌ 相对次要 |
| 示例（归并排序） | 时间复杂度：O(n log n) |
空间复杂度：O(n) |
7. 总结
时间复杂度与空间复杂度是评估算法性能的两个核心指标：
- 时间复杂度关注算法执行速度，是优化算法时的首要考虑
- 空间复杂度关注内存占用，随着硬件发展，其重要性已有所下降
我们通过阶乘和数组求和两个例子，分别演示了时间与空间复杂度的计算方法，并总结了它们之间的关键区别。
在实际开发中，我们更关注时间效率。但在资源受限的环境中（如嵌入式系统、移动设备），空间复杂度仍不可忽视。因此，在设计算法时，应根据实际需求在两者之间做出权衡。