我对算法很陌生，我有一些问题。假设我有一个排序算法，它以 O(n^2) 对数据进行排序，运行时间复杂度很高。例如，这可能是选择排序。现在，假设我没有使用选择排序，而是使用 HashTable，它将运行时间减少到 O(n)。
- 额外的空间复杂度对运行时间分析有影响吗？
- 在陈述答案时，我如何定义这两者之间的关系？
- 还是它们完全不同？
任何帮助，将不胜感激。
问问题
2440 次
2 回答
0
如果您的分析重点是算法的时间复杂度，您应该只关注每个操作的时间成本。
如果您的分析侧重于算法的时间和空间复杂性，那么您应该关注每个操作的时间成本以及数据结构的空间成本。
由于时间和空间是不同的资源，时间和空间分析应该分开进行。
也就是说，存在时空权衡的关键概念。 简而言之，可以用空间修改给定的算法交易时间，反之亦然。
例如，您可以通过引入一些复杂且占用空间但速度快的数据结构来降低时间复杂度。这将是时间 -> 空间权衡的一个示例，因为我们以增加内存使用为代价来加速我们的算法。
于 2012-08-04T18:02:59.497 回答
0
如果是理论算法理论中的运行时间分析，空间复杂度对运行时间复杂度没有影响。因为当我们谈论时间复杂度时，我们谈论的是 图灵机上程序的时间复杂度，它具有无限的内存。
空间和时间的权衡仅适用于应用程序。请参阅@Haile 的帖子以供参考。
于 2012-08-04T18:14:06.273 回答