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

Question

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

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

任何帮助都将不胜感激。

Answer 1

如果您的分析集中在算法的时间复杂性上，那么您应该只关注time (每个操作成本)。

如果您的分析集中在算法的时间和空间复杂性上，那么您应该将重点放在time (每个操作成本)和数据结构的空间成本上。

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

也就是说，时空权衡.的关键概念是，我们可以用空间修改给定的算法时间，反之亦然。

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

Answer 2

如果在理论算法理论中对运行时间进行分析，空间复杂度对运行时间复杂度没有影响。因为当我们谈到时间复杂性时，我们谈论的是图灵机 上程序的时间复杂性，它具有无限的内存。

空间和时间的权衡只适用于应用。参见@Haile的帖子以供参考。