空间，时间复杂度的猜想
来源：
马尔克ov
2017-06-14
看了您讲的递归和迭代实现的比较，我产生了一个猜想，这个事估计有数学家研究过了，我想了解一下目前的结论是什么？
猜想是这样的:对于一个特定的问题，时间复杂度和空间复杂度的乘积有一个最小值。可以选择用一个换另一个，但是别想两个都小。
写回答
1回答
-
实际上当我们选择了一个不恰当的算法的时候，很容易时间复杂度和空间复杂度都很高。但是一个高效的算法，时间复杂度和空间复杂度会都很低。
以斐波那契问题为例：我们可以使用O(n)的空间来记录之前计算的所有斐波那契数字，进而使用O(n)的时间解决斐波那契问题。但是仔细观察，我们为了求第n个斐波那契额数列，只需要n-1和n-2个斐波那契额数列。换句话说，我们其实没有必要把n个斐波那契额数字都存储起来。使用这个思路，我们可以使用O(1)的空间和O(n)的时间解决斐波那契额问题。不过，其实计算斐波那契额数列的第n项，可以使用O(1)的空间和O(1)的时间，直接用数学的方式计算出来：）
不过对于一些问题，当我们需要不断去计算一些重复数据的时候，就可以使用“用空间换时间”的方式。本质就是预先把一些计算结果存储起来。在后面介绍“查找表的使用”以及“记忆化搜索”的时候，这个思路更明显。
至于对于“某类特定问题”，是否空间和时间存在一定程度的“守恒”？直觉上是的。但这类问题究竟是哪些“特定问题”？能够达到什么程度的“守恒”？怎么定义这里的“守恒”？非常抱歉，我没有接触过这类研究。如果你以后发现了，不要忘记来和我分享一下：）
非常赞的思考！
032017-06-18
相似问题