时间与空间的权衡Time-Space Tradeoff

把反复需要的结果或中间步骤存下来，用额外空间换取更少计算。

1614 年，约翰·纳皮尔在爱丁堡出版对数表，把繁琐的计算变成可反复查阅的印刷页面。当时，天文学家处理三角计算，要反复做费时的乘除。有了表，他们可以查出数值，借助加减和再次查表完成计算。纳皮尔承担了制表的工作，使用者则保留一本书，省下此后一次次从头演算的功夫。纸张占了地方，却让同一份计算成果服务于许多人的许多次计算。

为什么成立

存下中间结果，就能跳过重复步骤

假设一份账本有 1,000 笔流水，你经常要查不同区间的总额。逐笔相加，一次最多要加 1,000 项。如果额外存下截至每一笔的累计金额，查询时只需用区间末尾的累计额，减去区间开始前的累计额。增加一份累计表，就把反复求和变成一次减法。这就是时间与空间的权衡：多占一些存储，少做一些计算。

复用省下的时间，要覆盖制表和更新的时间

在同一段使用期内，设每次现算耗时 $c$ ，查表耗时 $r$ ，制表与更新共耗时 $p$ ，有效复用 $q$ 次。查表方案更省时的条件是：

$q (c - r) > p$

白话说，每次少花的时间，乘以真正用上的次数，要超过提前准备和维护花掉的时间。假设结果不变，现算一次用 10 秒，查表用 1 秒，制表用 90 秒。每次省 9 秒，复用 10 次刚好抵平，超过 10 次才省时。

存下可组合的信息，能少占空间又少算

累计表只存每笔的累计额，却能回答任意区间的求和问题，无需为每个区间都留一个答案。选择保存什么，决定了这笔交换有多划算。计算机里的空间是内存或磁盘；跨到日常工作中，它可以是一页换算表或一组已算好的方案。共同机制是把能复用的计算留住，让后来的任务跳过同一段劳动。

出处

它来自计算机科学中的算法与数据结构设计，没有公认的单一提出者。1980 年，马丁·赫尔曼发表《密码分析中的时间—存储权衡》，给出经典构造：预先计算并保存部分信息，缩短后续密钥搜索。这项理论结果清楚展示了预计算、存储量与后续计算时间之间的交换。

换个领域看

技术

写入时就算好

2019 年发布的 PostgreSQL 12 引入存储型生成列。数据库写入或更新数据时，按公式算出结果，将它作为一列存下；以后查询直接读取，省去逐次求值。额外空间和写入计算，换来了读取时更少的计算，适合频繁读取、较少修改且求值费时的数据。

投资

估值先做成表

假设你持续跟踪一家企业，每次股价变化都要查看不同假设下的估值。你先把几档利润与几档估值倍数组合算好，存成一张表。之后股价变动时，直接查表比较价格与估值，省掉重复乘算。在利润假设不变的期间，同一张表可以供你反复比较不同买入价格。

个人生活

份量提前换算

假设你每周都做同一道菜，经常在两人、四人和六人用餐之间切换。你把配方中可按人数同比例调整的用料，各换算一遍，写在厨房卡片上。做饭时选好人数，直接照着称量。多存几行数字，省下每次拿着原配方乘除的功夫，也减少临时算错的机会。

遇事时问自己

我反复做的哪一段计算，可以变成可保存的结果或中间步骤？
这些结果在失效前，会被有效复用多少次？
每次取用省下的时间，累计能否覆盖准备、查找和更新的时间？
我能保存少量可组合的中间结果，替代一大堆完整答案吗？
额外存储会挤占什么资源，输入变化时由谁更新结果？

边界与误用

当任务只做一次、计算本来很便宜，或输入频繁变化时，制表和维护会吃掉省下的时间。结果散落在许多文件中，找表也会比重算更慢；数据超过内存容量，额外读写还会拖慢程序。最常见的误用是把“多存”当成“必然更快”，既保存大量用不到的答案，又沿用过期结果。保存旧估值只能省掉重复运算，企业盈利假设变了，就要重算。空间换来的加速，也不会让原先的判断自动变正确。

练一练

一名剪辑师要制作12个语言版本的宣传片。各版背景动画相同，只有字幕不同。每版重新生成背景要30秒；制作并整理一份可复用的背景文件共需240秒，之后每版读取要5秒。字幕合成在两种方案中耗时相同，磁盘也足够。

关于是否保存背景文件，哪种判断最站得住？

一名投资经理反复调整30只债券的持仓数量，用同一组20个压力情景比较组合盈亏。每只债券在各情景下的单位盈亏计算很慢，但算出后，组合盈亏只需按持仓数量相乘再相加。分析期间定价假设不变，新持仓组合几乎从不重复，而且需要保留每个情景的准确结果。

怎样保存计算结果，最能减少后续工作？

一名护士每次早上七点下夜班，都从医院叫车回家，要比较三个平台此刻谁最便宜。她把过去一个月这条路线的报价存成表，打算以后直接查表，省掉逐个打开平台的时间。三个平台的报价都会随当时司机供给、需求和优惠变化，旧报价不会锁定今天的价格。

关于这张报价表，哪种判断最站得住？