空间复杂性与时间复杂度之间的权衡
我一直在研究一些排序算法，并且遇到了时间和空间复杂度之间的一些反向关系。 例如，类似选择排序的算法需要O（n ^ 2），但只需要恒定的空间，因为它可以在适当的位置完成。 像合并排序这样的算法具有O（nlogn）时间复杂度，但需要O（n）空间。
我的问题是
是否有一个将时间和空间复杂度相互关联的定理或法则？ 这种现象仅存在于排序算法还是这种交易还存在其他问题？
为了时间复杂性而对空间复杂性进行交易，现代RAM大小的巨大增加，这是否是一个好主意？ 或者有时候减少时间复杂度会使空间复杂性变得过大。
回答你的第一个问题 - 不，没有。 这来自一个算法的案例分析。 没有数学公式可以计算时空复杂度折衷。 是的，它也坚持其他算法。 例如：考虑在数组中运行求和的问题 - 在两者之间进行更新。 如果存储在O(n)存储器（数组）中，那么复杂度将是O(n)用于检索数组范围内的特定和。 但是如果你保留一个具有O(4*n) O(n)空间复杂度的分段树，它会给O(logn)更新和检索。
不它不是。 拥有巨大的空间复杂性无法弥补我们今天获得的额外记忆。 性能将受到内存访问等限制。
有些情况下，时间复杂度的降低只能在相对较高的空间复杂度下才能实现。 例如，如果存储的数据是未压缩的，则需要更多空间，但访问时间要比数据压缩存储时小（因为压缩数据会减少占用的空间量，但运行解压缩算法需要一些时间） 。 这取决于我们将要面对的情况，并决定我们想要采用哪种解决方案。
据我所知，没有关于时间和空间复杂性权衡的明确定律。 然而，存在各种算法问题具有多种解决方案的趋势，其中一些需要较少的时间以牺牲空间为代价，另一些则需要更多的空间而牺牲时间。
当试图优化算法时，通常情况下，例如以预计算的形式使用更多空间会导致更好的时间性能。 研究时间和空间的复杂性有助于观察这种趋势，但也可能会产生误导。 以合并排序为例，您可能实际上实现了需要恒定内存量的合并排序算法。 它甚至可以是一个就地排序。 虽然空间复杂度降低了，虽然时间复杂度保持不变，但由于大的恒定或线性时间因素（不计入O(n log n) ），性能会受到影响。
速度优化最常见的情况是使用查找表，牺牲一些内存以避免重新计算。 另一个例子是数据压缩：采取众多的图像或音频文件格式，其优点和缺点。
关于你的第二个问题，当然有些情况下，性能的一些潜在增加会导致内存需求的爆炸。 在电子游戏中找到例子并不难，因为它们通常需要大量的计算资源。
解答。
不，没有这样的定理。 即使排序。 例如heapsort具有时间O(n log(n))和O(1)空间复杂度。
有很多技术明确地将时间换成空间。 例如memoization。 他们不是免费的，并不总是更好。 请记住，高效的内存使用不仅仅是为了节省内存。 它具有从更好的内存位置到减少数据传输的好处。 举个例子，看看https://github.com/google/snappy，了解现实世界中的系统，人们选择使用更多的CPU来节省内存，因为它让事情变得更快。
上一篇: Space complexity vs time complexity trade offs
下一篇: Path Planning Algorithm D*(Dstar) Algorithm's Time, Space, Complexity?