时间复杂度和 Space 复杂度成反比吗？
Are Time Complexity and Space Complexity inversely proportional?
我研究了很多算法，似乎一个算法要达到操作的最高复杂度，他们必须牺牲其他复杂度。我想了解是什么阻止了它们成反比。
时间和space复杂度当然不是成反比的。您一次只能针对一个指标优化系统，这只是一个简单的数学事实。
如果您针对时间优化算法，那么它在 space 中不太可能是最优的。如果您针对 space 进行优化，那么它不太可能及时达到最佳。如果您针对其他内容进行优化，那么它在任一时间或 space.
都不太可能是最佳的
通常我们会选择实际的权衡。填充 space 需要时间这一事实对我们有所帮助，因此在很多情况下，时间和 space 复杂性实际上是正相关的。
肯定的答案是没有，但是更流畅的答案是不一定。
有时，当你解决一个问题时，你可能会想：“我可以通过蛮力来解决这个问题，这将花费我 O(n²) 的时间和 O(1) space.. . 但也许我可以建立这个数据结构并采用 O(n log(n)) space，但我可以在 O(log(n))".
中回答它
在很多情况下，需要在时间和 space 复杂性之间进行权衡。您负担得起使用更多 space、预处理输入、构建结构并且您可以更快地回答，但有时您可以节省您的记忆，而只是 运行 直接算法。
事实是，并非所有问题都有这种权衡。例如，如果我问你：“你能告诉我一个数组所有元素的总和吗？” - 当然你可以用数组构建一棵树并对其执行遍历 return 总和，浪费 O(n) space 和时间，但你不必这样做，你可以只需在 O(n) 时间内求和 return，不使用额外的 space.
简而言之：在很多问题中，许多可能的解决方案是在时间和复杂性之间进行不同的权衡而得出的，但不是所有的，并且由于它们并非在所有情况下都成反比，所以它们是不成反比。
夸张一点：经济学说它们成反比，数学说不成反比。如果你绘制大量算法的时间和 space 复杂度，所有竞争算法都将位于帕累托曲线交易时间与 space 上，因为一个算法需要更多时间和更多 space比它的竞争没有竞争力。甚至还有少量算法称为时间-记忆权衡。但从长远来看，两者在理论上 linked。使用 N space 至少需要 N 时间，如果有限状态机只有 N 位 space，它只有 2^N 种可能状态，所以它不可能使用更多超过 2^N 次而不进入无限循环。
在 Blum (JACM 1967) 的“递归函数复杂性的机器无关理论”中有一个非常理论化的方法。定理 3 提供了任何两个复杂性度量之间的 link 的证明，但我认为它太松散以至于对于任何实际目的都完全无用。它确实说，“这意味着 Phi(n) 和 Phi'(n) 彼此相差不大”（我将 table 中的符号翻译为 Phi 和 Phi'）——但我认为要同意“不要相差太多”，您必须接受 n 和 2^n 几乎是同一回事。
我研究了很多算法，似乎一个算法要达到操作的最高复杂度，他们必须牺牲其他复杂度。我想了解是什么阻止了它们成反比。
时间和space复杂度当然不是成反比的。您一次只能针对一个指标优化系统，这只是一个简单的数学事实。
如果您针对时间优化算法，那么它在 space 中不太可能是最优的。如果您针对 space 进行优化，那么它不太可能及时达到最佳。如果您针对其他内容进行优化，那么它在任一时间或 space.
都不太可能是最佳的通常我们会选择实际的权衡。填充 space 需要时间这一事实对我们有所帮助，因此在很多情况下，时间和 space 复杂性实际上是正相关的。
肯定的答案是没有，但是更流畅的答案是不一定。
有时，当你解决一个问题时，你可能会想：“我可以通过蛮力来解决这个问题，这将花费我 O(n²) 的时间和 O(1) space.. . 但也许我可以建立这个数据结构并采用 O(n log(n)) space，但我可以在 O(log(n))".
中回答它在很多情况下，需要在时间和 space 复杂性之间进行权衡。您负担得起使用更多 space、预处理输入、构建结构并且您可以更快地回答，但有时您可以节省您的记忆，而只是 运行 直接算法。
事实是，并非所有问题都有这种权衡。例如，如果我问你：“你能告诉我一个数组所有元素的总和吗？” - 当然你可以用数组构建一棵树并对其执行遍历 return 总和，浪费 O(n) space 和时间，但你不必这样做，你可以只需在 O(n) 时间内求和 return，不使用额外的 space.
简而言之：在很多问题中，许多可能的解决方案是在时间和复杂性之间进行不同的权衡而得出的，但不是所有的，并且由于它们并非在所有情况下都成反比，所以它们是不成反比。
夸张一点：经济学说它们成反比，数学说不成反比。如果你绘制大量算法的时间和 space 复杂度，所有竞争算法都将位于帕累托曲线交易时间与 space 上，因为一个算法需要更多时间和更多 space比它的竞争没有竞争力。甚至还有少量算法称为时间-记忆权衡。但从长远来看，两者在理论上 linked。使用 N space 至少需要 N 时间，如果有限状态机只有 N 位 space，它只有 2^N 种可能状态，所以它不可能使用更多超过 2^N 次而不进入无限循环。
在 Blum (JACM 1967) 的“递归函数复杂性的机器无关理论”中有一个非常理论化的方法。定理 3 提供了任何两个复杂性度量之间的 link 的证明，但我认为它太松散以至于对于任何实际目的都完全无用。它确实说，“这意味着 Phi(n) 和 Phi'(n) 彼此相差不大”（我将 table 中的符号翻译为 Phi 和 Phi'）——但我认为要同意“不要相差太多”，您必须接受 n 和 2^n 几乎是同一回事。