空间复杂性与时间复杂性权衡

Question

我一直在研究一些排序算法，并在时间和空间复杂度之间遇到了一些逆关系。例如，像selection这样的算法采用O(n^2)，但由于可以在适当的地方执行，所以只需要常量空间。然而，像合并排序这样的算法具有O(nlogn)时间复杂度，但需要O(n)空间。

我的问题是

1. 是否有一个定理或定律将时间和空间的复杂性相互权衡？这种现象是只存在于排序算法中，还是在其他问题上也存在这种折衷？
2. 将空间复杂性与时间复杂性进行交换，以大幅度增加现代RAM大小，这总是一个好主意吗？或者，当时间复杂度降低时，是否会使空间复杂度过大。

Answer 1

在回答你的第一个问题时--不，没有。这来自于一种算法的逐个案例分析。没有计算时空复杂性权衡的数学公式。是的，它也存在于其他算法中。例如:考虑在数组中运行sum的问题--在两者之间进行更新。如果您存储在O(n)内存(数组)中，那么用于在数组中的某个范围内检索特定和的复杂性将是O(n)。但是，如果保留一个具有O(4*n)~O(n)空间复杂性的段树，则会提供O(logn)更新和检索。

不不是的。拥有巨大的空间复杂性并不能弥补我们今天所获得的额外记忆。性能将受到内存访问等的限制。

在某些情况下，时间复杂度的降低只能在空间复杂度较高的情况下实现。例如，如果存储的数据是未压缩的，则需要更多的空间，但访问时间比存储的数据要小(因为压缩数据会减少所需的空间，但运行解压缩算法需要一些时间)。这取决于我们将要面对的情况，也决定了我们想要采取的解决方案。

Answer 2

据我所知，没有关于时间和空间复杂性权衡的明确规律。然而，有一种趋势是，各种算法问题都有多重解的倾向，有些以牺牲空间为代价而需要更少的时间，而另一些则以牺牲时间为代价而需要更多的空间。

当试图优化算法时，通常情况是，使用更多的空间，例如，以预计算的形式，会带来更好的时间分辨性能。研究时间和空间的复杂性有助于观察这一趋势，但也可能造成误导。以合并排序为例:您可能实际上实现了一个需要常量内存的合并排序算法。它甚至可以成为一种就地的类型。虽然空间复杂度降低了，虽然时间复杂度保持不变，但由于大的常数或线性时间因素(在O(n log n)中不算在内)，会对性能造成影响。

对速度进行优化的最常见情况是使用查找表，为了避免重新计算，需要牺牲一定数量的内存。另一个例子是数据压缩:以众多的图像或音频文件格式为例，它们各有优缺点。

关于第二个问题，当然，在某些情况下，性能的可能提高会导致内存需求的激增。在电子游戏中找到例子并不难，因为它们通常需要大量的计算资源。

Answer 3

答案。

1. 不，没有这样的定理。即使是分类也不行。例如，堆排序具有时间、O(n log(n))和O(1)空间复杂性。
2. 有各种各样的技术可以显式地交换空间来换取时间。比如回忆录。它们不是自由的，也不是总是更好的。记住，有效的内存使用不仅仅是为了节省内存。它从具有更好的内存局部性到减少有线数据传输都有好处。举个例子，看看https://github.com/google/snappy，看看在现实系统中人们是如何选择使用更多的CPU来节省内存的，因为它使事情变得更快。