@[toc] --- ## 时间复杂度和空间复杂度的定义 - 时间复杂度是指算法执行所需的时间，通常以运行次数来衡量，表示为 T(n)。通常使用“大 O 表示法”来表示算法的时间复杂度，即 $T(n) = O(f(n))$，其中 f(n) 是某个函数。常见的时间复杂度有常数级别 $O(1)$、线性级别 $O(n)$、对数级别 $O(log n)$、平方级别 $O(n^2)$、立方级别 $O(n^3)$、指数级别 $O(2^n)$ 等。 - 空间复杂度是指算法执行所需的空间，通常以空间使用量来衡量，表示为 S(n)。与时间复杂度一样，也使用“大 O 表示法”来表示算法的空间复杂度，即 $S(n) = O(g(n))$，其中 g(n) 是某个函数。常见的空间复杂度有常数级别 $O(1)$、线性级别 $O(n)$、对数级别 $O(log n)$、平方级别 $O(n^2)$、立方级别 $O(n^3)$、指数级别 $O(2^n)$ 等。 ## 空间换时间的例子 - **哈希表**：在使用哈希表时，需要额外的空间来存储哈希表的桶（数组），增加了空间复杂度，但可以通过哈希函数快速地查找数据，时间复杂度为 O(1)。 - **跳表**：在查找数据时，跳表通过增加多级索引来加速查找，虽然增加了索引的维护成本，但可以在 $O(log n)$ 的时间复杂度内完成查找，比普通链表的 O(n) 查找效率更高。 - **数据库建立索引** ## 时间换空间的例子 - **压缩算法**：压缩算法可以将大量的数据压缩成较小的数据集合，从而减少数据的存储空间。例如，Gzip、Zip、LZ77等压缩算法可以将文本、图像、音频等文件压缩成更小的文件。这种方式可以节省存储空间，但需要占用更多的计算时间。 - **Gradient Checkpointing**：搞过深度学习的小伙伴应该能够理解这个意思。通常情况下，反向传播算法需要在前向传播过程中存储所有的中间结果，以便计算梯度。但是，这种方法会导致内存使用量急剧增加，并可能导致计算机内存不足而无法进行大规模训练。Gradient Checkpointing 解决了这个问题，它允许在前向传播的过程中把部分结果存储到磁盘上，并在反向传播过程中恢复这些结果。这样，虽然会增加计算时间，但是可以减少内存使用量，从而支持更大规模的训练数据。因此，Gradient Checkpointing 是一种时间换空间的技术。