为什么时间和空间可以互换

引言

在大量的算法教材和课程中，基本都会提到程序的时间和空间是可以互换的，但很少有教材来解释这个问题，下面我们就以一个例子来理解一下什么叫时间和空间是可以互换的。

在一个程序中，数据实际上可以和函数一一对应。

例子

最简单的比方，就用下面一个例子：

// 假设我们有一个数组
int arr[100];

// 还有一个函数:
int func(int index) {
    return arr[idx];
}

这样，就是一个最简单的映射关系，相当于：(arr[index] -> arr(index))

数组 -> 下标 -> 值

函数 -> 参数 -> 值

观察上述两个不同的资源，我们可以将其归为两类：

存储资源（如变量以及数组等数据结构），代表着程序的需要的内存空间大小
计算资源（函数、方法等），代表着程序需要的运行时间的大小

这就是时间和空间可以互换的原理。

假设从数组中取值需要 1 个单位的时间，将参数传入函数中并进行计算，获得返回值的时间需要 100 个单位的时间（并且计算过程中包含这大量的重复子问题），我们需要进行 100 次函数计算，那么我们需要 10000 个单位的时间。

此时，如果我们有一个理论上无限大的内存空间，那么我们可以将函数的参数对pair以及返回值return都记录下来。

这样，我们只需要将最大的参数传入函数中，并在计算过程中记录子问题的结果，这样我们就只需要 100 个单位的计算时间，然后访问 100 次映射表，也只需要 100 个单位的时间，这样最终我们从需要 10000 个单位的时间优化到了只需要 200 个单位的时间即可，但同时，我们付出了 100 个单位的存储空间。

这就是空间换时间的原理，时间换空间的话将上述这个例子倒过来即可。