常见的算法优化套路，用空间换时间

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天我们来聊聊算法当中非常常见的一种优化思路，以空间换时间。

这里的空间指的是空间复杂度，时间指的是时间复杂度。空间换时间即是指牺牲一定的空间复杂度来换取更低的时间复杂度，来保证程序的运行效率。

其实这句话也道出了算法的本质，算法不是万能的，也不是没有代价的。我们当然想什么也不牺牲就得到更高的性能，但是在很多问题当中这是办不到的。很多时候，更大的存储空间就是更高性能的代价。不过好在现在内存的价格越来越便宜，而程序效率越来越重要，空间换时间的这个操作也就越来越有价值。

空间换时间是很多算法和数据结构的出发点，我们当然不可能在一篇文章当中穷尽所有的应用场景。但至少我们可以理解它的运作原理，对于这样的技巧或者策略有一定的认知。

举个栗子

如果我问你，最优的排序算法的复杂度是多少？

我相信很多同学的答案是

，这当然不能说是错的，但如果我们加上更多的条件，比如这些数的取值范围很小，答案还是

吗？

其实不是，因为我们有更快的方法。举个例子，假设要排序数组a中的每个数都在0到1000之间，那么我们是不是可以用一个长度为1000的数组b记录哪些数字出现在了a数组当中，哪些没有？这样我们只需要遍历一遍数组a，执行b[a[i]]++。之后再遍历一次数组b，就可以得到数组a排序之后的结果了。

这种排序的算法叫做桶排序，它的复杂度完全取决于要排序的元素的数据范围。我们利用了数组下标的有序性来进行排序，这本质上就是一种空间换时间的思路。

记忆化和缓存

我们再来看一个经典的例子，在一些递归问题当中，可能会出现一些子问题被反复求解导致冗余的问题。

比如斐波那契数列问题，我们要求数列当中的第n个数。很容易想到，从第三个数开始数列中的元素等于前两个元素之和，我们可以利用这一点写出递归代码。

int fib(int n) {
    if (n < 3) return 1;
    return fib(n-1) + fib(n-2);
}

但是这段代码有很大的问题，最大的问题就是复杂度。如果我们画出它的递归树会发现当中有太多的重复。

从上图当中可以看出，我们要求fib(10)，需要先求fib(9)和fib(8)。但求fib(9)也需要求fib(8)，相当于fib(8)被重复计算了两次。如果我们继续展开下去，会发现更多的重复，离树根越远，重复的次数也就越多。

大家感兴趣的话可以用一个全局变量统计一下递归次数，看看随着n的增大，递归次数会发生怎样的变化。

在这个问题当中，我们很容易想到，我们能不能这些递归出现的结果都存起来呢？比如当我们执行过一次fib(5)以后，我们就把对应的结果存起来。下次再要递归的时候，先检查以及保存的结果，看看是不是已经存在了，如果已经存在了就直接返回结果。

代码改动起来也非常简单，我们只需要使用一个map来存储递归的结果即可。

map<int, int> buf;

int fib(int n) {
    if (n < 3) return 1;
    if (buf.count(n)) return buf[n];
    int ret = fib(n-1) + fib(n-2);
    // 更新缓存
    buf[n] = ret;
    return ret;
}

如果把求斐波那契数列看成是一个搜索问题的话，那么这就是记忆化搜索的最简单的应用。看起来好像很高大上，其实就是在搜索当中加入缓存，确保已经搜索过的问题不再重复搜索，从而加快程序运行的效率。

我们使用缓存来存储中间结果当然需要使用额外的存储，但这样做的好处是非常明显的，我们大大提升了程序运行的速度，说白了底层逻辑依然是空间换时间。

另外多说一句，类似的思路现在广泛使用了各大互联网公司当中。几乎所有面向用户的服务器都会使用缓存，当用户登录时缓存用户的信息，这样可以缩短数据查询的时间。只不过实际应用层面的缓存要高级和复杂一些，比如会支持定时时效，另外由于访问量庞大，使用的往往是分布式缓存。

从单机缓存到分布式缓存虽然看起来只是服务器数量的变化，但其实是问题场景的巨大变化，整个复杂度上升了远不止一个层级。当中会涉及到各种各样的问题，在后端领域当中，缓存更新是一件非常硬核的事情，远不像大家想的那么简单。

大家感兴趣的话可以花点时间了解一下分布式系统的一些知识，相信会有更深刻的感悟。

还有，给算法加缓存这事并不只发生在搜索算法当中，像是动态规划或者是一些其他查询的算法都可以使用。算法和数据结构之间的互相结合、发散是非常灵活的，大家千万不要拘泥于一种用法。

关于空间换时间的具体用法我们还会在之后的文章当中遇到，这里就不过多发散了。如果有什么想说的，欢迎在下方评论。