空间，时间复杂度的猜想

Question

看了您讲的递归和迭代实现的比较，我产生了一个猜想，这个事估计有数学家研究过了，我想了解一下目前的结论是什么？
猜想是这样的:对于一个特定的问题，时间复杂度和空间复杂度的乘积有一个最小值。可以选择用一个换另一个，但是别想两个都小。

Answer 1

liuyubobobo 2017-06-15 01:49:55

实际上当我们选择了一个不恰当的算法的时候，很容易时间复杂度和空间复杂度都很高。但是一个高效的算法，时间复杂度和空间复杂度会都很低。

以斐波那契问题为例：我们可以使用O(n)的空间来记录之前计算的所有斐波那契数字，进而使用O(n)的时间解决斐波那契问题。但是仔细观察，我们为了求第n个斐波那契额数列，只需要n-1和n-2个斐波那契额数列。换句话说，我们其实没有必要把n个斐波那契额数字都存储起来。使用这个思路，我们可以使用O(1)的空间和O(n)的时间解决斐波那契额问题。不过，其实计算斐波那契额数列的第n项，可以使用O(1)的空间和O(1)的时间，直接用数学的方式计算出来：）

不过对于一些问题，当我们需要不断去计算一些重复数据的时候，就可以使用“用空间换时间”的方式。本质就是预先把一些计算结果存储起来。在后面介绍“查找表的使用”以及“记忆化搜索”的时候，这个思路更明显。

至于对于“某类特定问题”，是否空间和时间存在一定程度的“守恒”？直觉上是的。但这类问题究竟是哪些“特定问题”？能够达到什么程度的“守恒”？怎么定义这里的“守恒”？非常抱歉，我没有接触过这类研究。如果你以后发现了，不要忘记来和我分享一下：）

非常赞的思考！

• 提问者 马尔克ov #1

  您说的又让我有了点新的想法，我们暂且把问题归为两类，一类叫"数列问题"，一类叫"非数列问题"。
  数列问题，除了斐波那契，比如等差数列，也可以用数学直接求出公式，使得时间复杂度从n变到1。但是非数列问题，比如排序问题，直觉上就不可能到1，n都不可能，无论如何都得比较啊。
  感谢老师为我这个"没什么用"的瞎想回复了这么多~

• liuyubobobo 回复 提问者 马尔克ov #2

  所以复杂度领域一个很重要的问题是寻找问题的下界。比如基于比较的排序，其时间复杂度的下界是O(nlogn)，但是不基于比较的排序，（比如基数排序法，桶排序法），其时间复杂度的下界为O(n)。
  
  但是排序问题是被研究的很透彻的问题，依然存在很多问题，我们并不确定其下界在哪里。比如最小生成树问题。Prim算法的时间复杂度是O(ElogV)，Kruskal算法的时间复杂度是O(ElogE)。但是是否存在O(V+E)级别时间复杂度的最小生成树算法（即线性时间复杂度的最小生成树算法）？我们暂时无法证明没有，但也暂时没有发现一个真正的O(V+E)级别的最小生成树算法。更不用提像TSP这样复杂的问题了。
  
  另一方面，也并非所有的和数相关的问题都是这么简单的，可以化简为O(1)的时间复杂度。（事实上，大多数数论领域的问题都是非常困难的）比如，第n个素数是什么？这便是一个经典的世界级难题：）

• 提问者 马尔克ov 回复 liuyubobobo #3

  好涨姿势！谢谢老师~