Space 复杂度与时间复杂度的权衡
Space complexity vs time complexity trade offs
我一直在研究一些排序算法，发现时间和 space 复杂度之间存在一些反比关系。例如，像选择排序这样的算法需要 O(n^2)，但只需要常数 space，因为它可以就地完成。然而，像合并排序这样的算法具有 O(nlogn) 时间复杂度，但需要 O(n) space。
我的问题是
是否存在将时间和 space 复杂性相互权衡相关的定理或法则？这种现象是否只存在于排序算法中，或者这种权衡是否也存在于其他问题中？
用现代 RAM 大小的巨大增加来交换 space 复杂度来换取时间复杂度总是一个好主意吗？或者有时降低时间复杂度会使 space 复杂度过大。
关于第一个问题的回答 - 不，没有。这来自对算法的个案分析。没有数学公式可以计算 space - 时间复杂度 trade-off。是的，它也存在于其他算法中。例如：考虑在数组中获取 运行ning 总和的问题——中间有更新。如果您存储在 O(n) 内存（数组）中，那么复杂性将是 O(n) 以检索数组范围内的特定总和。但是，如果您保留具有 O(4*n)~O(n) space 复杂度的线段树，它将提供 O(logn) 更新和检索。
不，不是。具有巨大的 space 复杂性并不能补偿我们今天获得的额外内存。性能将受到内存访问等的限制。
在某些情况下，时间复杂度的降低只能通过相对较高的 space 复杂度来实现。例如，如果数据未压缩存储，则需要更多 space，但访问时间比压缩数据存储更短（因为压缩数据减少了所需的 space 量，但它需要有时间运行解压算法）。这取决于我们将面临的情况，这决定了我们想要采用哪种解决方案。
据我所知，关于时间和 space 复杂性权衡没有明确的规律。然而，各种算法问题都有多种解决方案的趋势，有些需要更少的时间，但需要 space，而另一些则需要更多的 space，但需要更多的时间。
]
在尝试优化算法时，通常情况下使用更多 space，例如以 pre-calculations 的形式，会导致更好的 time-wise 性能。研究时间和 space 复杂性有助于观察这种趋势，但也可能产生误导。以你关于归并排序的例子为例：你实际上可以实现一个merge sort algorithm that requires a constant amount of memory. It can even be an in-place sort。虽然 space 复杂度降低了，虽然时间复杂度保持不变，但由于常数或线性时间因素较大（不计入 O(n log n)），性能受到影响。
最常见的速度优化案例是使用查找表，牺牲一些内存量以避免重新计算。另一个例子是数据压缩：各种图像或音频文件格式各有优缺点。
关于您的第二个问题，在某些情况下，性能的潜在提升当然会导致内存需求激增。在视频游戏中不难找到示例，因为它们通常需要大量计算资源。
答案。
不，没有这样的定理。甚至不用于排序。例如heapsort有时间O(n log(n))和O(1)space复杂度。
有多种技术可以明确地权衡 space 时间。例如记忆。它们不是免费的，而且并不总是更好。请记住，有效的内存使用不仅仅是节省内存。从拥有更好的内存位置到减少线上的数据传输，它都有很多好处。以 https://github.com/google/snappy 为例，了解在现实世界中人们如何选择使用更多 CPU 来节省内存，因为这样可以加快速度。
没有定理，没有规律，但是有处理时间-space复杂度权衡的算法设计方法。我建议你寻找动态编程方法。
重点是对于某些问题可能存在一些有趣的时间-space 复杂性权衡，但对于某些问题不...
对于您自己的示例，只有当您查看这两个孤立的示例时，时间 -space 复杂性权衡才会有趣。即，有一种用于对具有 O(n lg n) 时间复杂度和 O(1) space 复杂度的数组进行排序的算法 - heapsort 算法。
我一直在研究一些排序算法，发现时间和 space 复杂度之间存在一些反比关系。例如，像选择排序这样的算法需要 O(n^2)，但只需要常数 space，因为它可以就地完成。然而，像合并排序这样的算法具有 O(nlogn) 时间复杂度，但需要 O(n) space。
我的问题是
是否存在将时间和 space 复杂性相互权衡相关的定理或法则？这种现象是否只存在于排序算法中，或者这种权衡是否也存在于其他问题中？
用现代 RAM 大小的巨大增加来交换 space 复杂度来换取时间复杂度总是一个好主意吗？或者有时降低时间复杂度会使 space 复杂度过大。
关于第一个问题的回答 - 不，没有。这来自对算法的个案分析。没有数学公式可以计算 space - 时间复杂度 trade-off。是的，它也存在于其他算法中。例如：考虑在数组中获取 运行ning 总和的问题——中间有更新。如果您存储在 O(n) 内存（数组）中，那么复杂性将是 O(n) 以检索数组范围内的特定总和。但是，如果您保留具有 O(4*n)~O(n) space 复杂度的线段树，它将提供 O(logn) 更新和检索。
不，不是。具有巨大的 space 复杂性并不能补偿我们今天获得的额外内存。性能将受到内存访问等的限制。
在某些情况下，时间复杂度的降低只能通过相对较高的 space 复杂度来实现。例如，如果数据未压缩存储，则需要更多 space，但访问时间比压缩数据存储更短（因为压缩数据减少了所需的 space 量，但它需要有时间运行解压算法）。这取决于我们将面临的情况，这决定了我们想要采用哪种解决方案。
据我所知，关于时间和 space 复杂性权衡没有明确的规律。然而，各种算法问题都有多种解决方案的趋势，有些需要更少的时间，但需要 space，而另一些则需要更多的 space，但需要更多的时间。
]在尝试优化算法时，通常情况下使用更多 space，例如以 pre-calculations 的形式，会导致更好的 time-wise 性能。研究时间和 space 复杂性有助于观察这种趋势，但也可能产生误导。以你关于归并排序的例子为例：你实际上可以实现一个merge sort algorithm that requires a constant amount of memory. It can even be an in-place sort。虽然 space 复杂度降低了，虽然时间复杂度保持不变，但由于常数或线性时间因素较大（不计入 O(n log n)），性能受到影响。
最常见的速度优化案例是使用查找表，牺牲一些内存量以避免重新计算。另一个例子是数据压缩：各种图像或音频文件格式各有优缺点。
关于您的第二个问题，在某些情况下，性能的潜在提升当然会导致内存需求激增。在视频游戏中不难找到示例，因为它们通常需要大量计算资源。
答案。
不，没有这样的定理。甚至不用于排序。例如heapsort有时间
O(n log(n))和O(1)space复杂度。有多种技术可以明确地权衡 space 时间。例如记忆。它们不是免费的，而且并不总是更好。请记住，有效的内存使用不仅仅是节省内存。从拥有更好的内存位置到减少线上的数据传输，它都有很多好处。以 https://github.com/google/snappy 为例，了解在现实世界中人们如何选择使用更多 CPU 来节省内存，因为这样可以加快速度。
没有定理，没有规律，但是有处理时间-space复杂度权衡的算法设计方法。我建议你寻找动态编程方法。
重点是对于某些问题可能存在一些有趣的时间-space 复杂性权衡，但对于某些问题不...
对于您自己的示例，只有当您查看这两个孤立的示例时，时间 -space 复杂性权衡才会有趣。即，有一种用于对具有 O(n lg n) 时间复杂度和 O(1) space 复杂度的数组进行排序的算法 - heapsort 算法。