algorithm - 排序中的运行时间复杂度与空间复杂度

Question

我对算法还很陌生，我有一些问题。假设我有一个排序算法，它以 O(n^2) 的运行时间复杂度对数据进行排序。例如，这可能是选择排序。现在，假设我不使用选择排序而是使用 HashTable，它将运行时间减少到 O(n)。

• 额外的空间复杂度对运行时间分析有影响吗？
• 在陈述答案时如何定义这两者之间的关系？
• 或者它们完全不同？

如有任何帮助，我们将不胜感激。

Answer 1

如果您的分析侧重于算法的时间复杂度，则您应该只关注每个操作花费的时间。

如果您的分析侧重于算法的时间和空间复杂度，那么您应该侧重于每个操作花费的时间，以及空间 数据结构的成本。

由于时间和空间是不同的资源，所以时间和空间分析应该分开进行。

---

也就是说， Space - time tradeoff 是关键概念. 简而言之，可以用空间来修改给定的算法交易时间，反之亦然。

例如可以通过引入一些复杂、耗空间但速度快的数据结构来降低时间复杂度。这将是时间 -> 空间权衡的一个例子，因为我们以增加内存使用为代价来加速我们的算法。