计算机中 为何可以时间换空间或空间换时间？

[22yune]

如图，突然想到了这个问题。现实世界也有这种列子吗？（我不知道我在问什么）

我比较认同 ‘选择’不同‘solution’ 的观点。#17 #49 #64 #65

我错误的把这些场景下的时间与空间联系起来。

时间空间是在解决方案中都要涉及到的点。它们之前没有必然联系。



yy 一下：引用#37“时间坐标和空间坐标是平等的”，还有“a 和 b 两种可能”。反推不符合 ‘ab 可能’ 的情况都可以做时空交换（？）。基于这个能分析下‘小卡车搬家运 3 次，用大卡车运一次’ 吗？

[laojiaqing]

?

[woodensail]

你听说过仓库吗？

[lcy630409]

汽车厂流水线不能停，不停的生产汽车
如果每辆汽车能短时间卖出去，就可以回本，得到的钱继续生产出两辆汽车
如果没能短时间卖出去 就只能堆积在仓库，仓库会越来越大，直至仓库放不下破产重组

[cxh116]

这个不能无限换. 跟现在中金钱换时间一样,但换不来长生不老.

[seanseek]

？？？

[22yune]

@woodensail 这个是类比 hashMap 过来的吗？我期待更深入的见解。dog：（
@laojiaqing 我也不知道我在问什么？？？？？？？？

[Torpedo]

当然可以了。
堵车怎么办，多修路。空间换时间。反之就是时间换空间

只不过现实世界复杂的多，不想计算机，条件少，原子性。

[22yune]

知道能换，知道怎么换的，就突然想问 为什么能换？

[ayase252]

图书馆的分类书架，为了查找效率牺牲了空间

[22yune]

@ayase252 放上书架并不能把空间换时间。需要分类了才能换时间？我可能是想问这个。为什么能换？

[ElmerZhang]

以存储一个超大文本文件来举例：
存储时不做任何压缩，虽然耗费的存储空间会比较大，但会达到比较快的读写速度，这就是空间换时间。
把文件压缩存储，这样读写时需要额外做一步解压或者压缩，读写速度肯定不如直接读写，但是会省很多磁盘空间，这就是时间换空间。

[finab]

随便想的例子，衣柜里找一件衣服

假如你就一个小箱子做衣柜，你就得把衣服折好，一件一件塞进箱子里。想找一件衣服时，需要耗费更多时间一件件拿出来
这叫时间换空间

假如你有个 100 平的房间做衣帽间， 你可以把衣服挂着放，买几个模特穿着放，一眼看过去很方便的就找到想找的衣服，走过去就穿上了
这叫空间换时间

[340244120w]

简单说就是时间成本的重要程度。。别想太复杂了

[coderluan]

这个看你说的是什么空间了，如果是占用体积，那样这个类比非常简单，2 吨货物，1 辆车送 2 趟用 2 小时=2 辆车送 1 趟 1 小时。如果你说的空间是距离，那就得引入观察者属性变成谈论相对论了。

[pinews]

你说的时间和空间都不是事务的本质属性，而是人的需求，属于统筹，具有相同属性的事务的数量和长度成正比。
你说的空间越大越好，你说的时间越短越好，所以你说的“换”实际是成“反比”。

[wysnylc]

因为现实世界也是如此

[misdake]

对于“空间换时间”或者“时间换空间”的说法，我觉得并不是真的在做“换”的动作。而是经过考量，从多种不同的<时间,空间>组合的方案中选取了一组合适的。于是，做出的选择相比于其他选择，有一种“时间换空间”(或反过来)的感觉。

[alphatoad]

Caching，就像你家门口的银行可以办最基本的业务，更复杂的得去市分行办

[rrfeng]

单位时间成本和单位空间成本的不同导致了不同的方式有不同的总成本

[l30n]

y = f(x)，把从 x 计算得到 y 的过程转化成查表

[SlipStupig]

这么时候有 100 个人排队去买炸鸡，但是目前只有一个窗口和一个卖炸鸡的店员，假设炸鸡是一分钟一份，那么 100 个人就需要 100 分钟才能全部领到炸鸡，老板只需要给那个店员 3000 块钱工资。
如果现在改 5 个窗口，那么变成了同时可以出货 5 份炸鸡，就需要 5 个炸鸡佬去工作，100 个人只需要 20 分钟就可以全部领到炸鸡了，这个时候老板需要每个月给员工支付 15k 的工资

---

上面的这个例子就是，典型的时间换空间，长流水线和多流水线（具体可以看 CICS 指令集和 RSIC 指令集）如何得到最优性价比，就是经典的 LP 问题, 如果人流量每个月不确定，成本不确定，这个就变成动态规划问题

[STRRL]

程序 = 算法 + 数据结构

空间 /时间的交换 正是解决问题使用了不用的算法和数据结构的组合.


再举个例子,有 A B C 三个人, A 知道 B 的家在哪, B 知道 C 的家在哪.

A 每次想去找 C 玩, 他都需要跑到 B 的家里询问 B.
或者 A 自己记住 C 的家在哪.

空间换时间....

[yellowmarlboro]

我认为时间不存在交换一说

[lithbitren]

提前生产好，放进库存，发货快。
没库存，得去订材料，再生产，再发货。

前者库存成本高，发货快。
后者库存成本低，发货慢。

[22yune]

@misdake 角度有点特别！选择 ？如#11 #12 的例子也都是选择吗？如果不知道那种方式就没有那个选择。就不能换？
下面回答的例子好像都是回答的怎么换，举例的。我想问为什么能换？不是怎么换。‘为什么能’和‘怎么做’ 好像是一样的。但在这里是不一样的。就像是可以

[22yune]

@misdake 角度有点特别！选择 ？如#11 #12 的例子也都是选择吗？如果不知道那种方式就没有那个选择。就不能换？

下面回答的例子好像都是回答的怎么换，举例的。

我想问为什么能换？不是怎么换。

‘为什么能’和‘怎么做’ 好像是一样的。但在这里是不一样的。

就好像是可以做和为什么可以做。‘怎么做’对应‘可以做’，‘为什么能’对应‘为什么可以做’。

所以我是想问为什么可以换？不是怎么换可不可以换。

[yufpga]

计算机中的空间，时间和物理中的空间，时间不是一个概念。计算机中的空间指的是内存(物理存储介质)的空间，时间指的是 cpu 的时间, 是一个非常具体且可以衡量的东西。物理上的空间和时间,我不是搞物理的,解释不了。

[helloZwq]

一个敢问 一个敢答!

[litmxs]

把一些运算结果存在内存里面, 下次遇到的时候直接读取而不需要再次运算达到节约时间的效果.

[daozhihun]

你的书桌其实也是用空间换时间呀。
你的书库有一堆书，把最近常用的书放在书桌上，以免每一本书都要去书库里找，从而节省时间。
时间换空间反之，如果你的书桌坏了要修理，没有这一部分空间，那么你就只能每次花时间去书库找了，读完再放回去。

[Kagari]

心算

[keith1126]

基础不牢，地动山摇。 —— 高中某老师

[www5070504]

有点民科的味道

[lengyihan]

单纯的概念上的转换以人类目前对宇宙的认知还做不到。目前所说的这个主要是针对具体情况进行的。

[Yourshell]

你下黄片时大带宽不省时间吗？

[xiaobai332]

问：磁为何能生电
答：因为电磁感应现象
问：我知道电磁感应，但为什么磁能生电
答：用切割磁感线，导体就会产生感应电流
问：我问的不是怎么样磁生电，是磁为什么能生电？？？

[favourstreet]

楼主的这个问题真有意思，我先提供一个物理学上的推论供楼主参考：数据也占用物理上的空间，因为所谓数据就是熵，而熵是一个广延量，熵越大体积也一定越大（如果全息原理是正确的，熵越大表面积越大）；至于计算机中的时间，物理上的时间区别不大。

如果楼主能适应相对论的思维习惯：两个门电路可以在空间的两个不同坐标各自接受输入并输出结果，也可以在不同的两个时间坐标各自接受输入并输出结果。而时间坐标和空间坐标是平等的，把门电路摆放在空间的不同位置，以及把门电路摆放在时间的不同位置，在相对论角度下是没有区别的。如果相对论不正确，不存在这样的时空对称性，那么就有两种可能：a.算法和物质的运动可以具有无限大的速度，开始即是结束，根本不需要时间这一维度； b.数据在空间中传播时本身会发生变化，即使有空间也无法利用

[zhujinliang]

为什么空间能换时间，因为内存便宜了呗😄
空间换时间最常用的办法：查表法，提前把输入值的结果算好，需要时直接按地址读出来就可以了。缺点就是表需要占一定的存储空间，输入输出为 int16 的话可能需要 128KB，int32 的话可能需要 16GB 。

[cmdOptionKana]

@22yune "我想问为什么能换？不是怎么换。"

楼主这里想错了，这种情况下，怎么换等同于为什么能换。

比如上面有人举衣柜的例子：为什么更大的衣柜可以加快找衣服的时间？

因为衣服不用折叠。

为什么不折叠更快？因为拆叠需要时间，拆叠起来后无法直接看见。

就是这么简单，这里面还有什么疑问吗？

[cmdOptionKana]

还是说，你误解了这里“换”的意思？

这不是物理上的时间与空间（维度）的转换，只是 “有更大的地方办事可以更快” 的意思。

[murmur]

京东啊，满地都是仓库，所以发货快

[yangzhezjgs]

为什么空间换时间？
把计算结果存储起来，就节省了下次计算的时间
为什么时间换空间？
典型例子虚拟存储，程序具有局部性，所以可以只装载部分程序到内存中。

[yangzhezjgs]

详细来说，空间换时间，时间换空间相通的点在于 程序中存在某种重复。

空间换时间 是计算过程存在重复， 如果预测到了计算结果会重复使用，就可以提前计算好，把结果存下来，节省了每次计算的时间。

时间换空间 是程序中普遍存在顺序存储和循环结构而导致时间和空间上存在局部性，换句话说 cpu 花在一部分代码上的时间比其他部分多，用 28 法则来说，百分之二十的代码占用百分之八十的 CPU 时间，但是这部分代码存储空间只占百分之二十，所以只用保存百分之二十的重要程序就可以保证百分之八十的时间 CPU 都能正常运行。

[yangzhezjgs]

补充一下，空间换时间的重复应该是 程序在逻辑和功能上存在重复，时间换空间的重复应该是 程序在物理分布上存在重复。

[hoyixi]

这还用找例子，你用小卡车搬家运 3 次，用大卡车运一次

[Blacate]

比方说有一副扑克你要其中的某一张 一种是你吧所有的抓在手里一张张过 一种是所有的全都铺在桌面上 你一下子就能找到

[Cielsky]

@22yune 分类摆放不是需要更大的空间吗，不分类全堆一块
这不就是空间换时间吗

[ruxuan1306]

网上常见的行李箱收纳技巧，本质上是加大存取的时间复杂度，换取更小的空间复杂度。

[wshwwl]

如果你一定要这么问，那就是不能换或者没有换。
1. 空间换时间只是人们对于选择不同解决方案习惯性的表达而已，并不是真的产生了概念上的转换。实际上是，解决方案有多种，有的方案花的时间长，但是需要更少空间，而有的方案则相反，人们在不同的方案之间做选择，有取舍，类似于做出了交换。
2.如果你还要继续钻牛角尖，那其实所谓空间换时间也并没有换，只是时间成本转移了。生产更多的内存也需要时间，你在 cpu 上省的时间或者说成本全转换到内存生产上去了。你的空间也是你用生产内存的时间或成本换来的。只不过你(cpu)花费的时间少了，别人花费的时间更多了。但这种转移也是有限制的，即使你有无限的内存空间，你也不可能把时间压缩到零。

[oneisall8955]

钻牛角尖

[cwek]

更适合的比喻是桌面（内存）和柜子（外存）。
桌面是触手可及的（小空间但用时短），柜子够大胆查找需要翻箱倒柜的（大空间胆用时长），如果桌面够大，将工作所有需要用的东西都放在桌面上，就能随手拿来用，不用翻柜子。（空间换时间）
如果桌面不够大，部分工作东西只能放到柜子里来节省出必要的桌面空间，但需要时需要花时间找（时间换空间）

[22yune]

@www5070504 #33 我也觉得，就是突然有个念头，随便问问。

@xiaobai332 #36 就是这个 style

@favourstreet #37 没怎么看懂。门电路在时空不同位置没有区别，并没有回答问题吧？是 a 和 b 两种可能吗？（我没理解）

@cmdOptionKana #39 这个例子和#9 图书馆的列子类似。书不像衣服需要折叠。但也达到同样效果了。折叠不是问题点。

@yangzhezjgs #43 这个针对计算机好理解。你的意思是因为‘重复’。

@hoyixi @Blacate 这些列子直观的我没有一点疑问。但我对应不起来。我要对这些例子问‘为什么’。会不会有人想打我？_(:з」∠)_

[aneureka]

你肯定没学过动态规划..

[22yune]

@wshwwl
1 、观点是 选择。
2 、观点是 转移。这个部分认同。前面图书馆的例子，是因为分类整理的时间转移了后面查找的时间还是制作书架的时间？

是我钻牛角尖了。

[jackchao7432]

您就是带哲学家？

[22yune]

@jackchao7432 我感觉到被你嘲讽了。这个问题不能问吗？我是随便问问，有兴趣参与讨论下，没兴趣可以不用回复。

[cmdOptionKana]

@22yune 我明白了！

你以为计算机中、书柜、衣柜等等，空间时间互换的背后有一个共通的原因，所以你一直问“为什么”。

我觉得你就是这里想错了，没有共通原因，每一个能换的案例都是特殊的。

比如一个比较深的书柜，放在深处的书会被放在外层的书遮挡。但如果把书柜做成只有一本书的深度，然后相应的扩大书柜的宽度，注意，书柜的总空间大小并没有变，但找书就方便多了，这样不需要空间就能换时间（加快速度）。

也就是说，用空间换时间或时间换空间，其实只是做事方法之一，注意，它本质上是做事方法，即，本质上就是“怎么做”，因此在这种情况下“怎么做等同于为什么”。

[oshio]

这里时间指的是执行效率，空间指的是存储效率，结果你理解成了相对论。

[janus77]

我来回答吧
因为所有一切的计算任务都是可拆分的，大的拆成小的，小的拆成更小的。而他们又是互相独立，组合起来才成为最后结果。
于是，可以换=可以拆分。只要你能拆出一个小任务，我们就可以用另外的成本来实现这个任务。比如时间成本换成空间成本。你还要问为什么可以换？因为他是互相独立的啊，我把他当做两种东西分别用不同成本去做这不行吗

[takato]

说到修路- -以前看到过这个

Traffic flow measured on 30 different 4-way junctions

[qwertqwert12345]

https://zhuanlan.zhihu.com/p/90172780

[wingzhingling]

民科不请自来。
如果一个结构的发展依赖于某种行为，而这种行为依赖于某种属性，那么提高这种属性就能加速结构发展。
如水池泄水，在不改变水量的条件下，泄水这一行为取决于泄水孔大小，增大泄水孔面积就能加速泄水速度。
至于为什么算法中空间成本和时间成本可以互换，粗略的来讲，是因为完成一个功能时，基本操作依赖于空间。如果算法能利用更多的空间，效率就会更高。

[liuzhedash]

想一下实体书形式的字典，字典前几十页纸的内容是对所有字的索引（占用了额外的空间），这部分空间可以提高你找到特定字的速度（换取了时间）。

[charlie21]

本来就是一个个 solution 而已，每个 solution 需要不同的资源，你手上有一些时间资源、一些空间资源，然后 你选择了某个 solution 就献祭了一份它所需的资源。你只是在一次一次做 “拿 solution 并献祭资源” 这件事。最后，有一个人为你设定了一个衡量标准 ( 时间复杂度 / 空间复杂度 )，然后他拿着这个标准说，这是 时间复杂度换空间复杂度，即时间换空间。

时间复杂度 看 语句的执行次数

空间复杂度 看 临时变量的数量

http://www.ehcoo.com/complexity.html

你完全可以对这个标准不买账，设立你自己的标准，并且为此标准建立硬件设备，比如 算盘

[Trim21]

不是物理意义上的两种不同东西的转换（重力势能转换为动能）
只是在处理问题时通过占用更多的空间来换取时间的节约。花费的时间和空间本身在不处理问题的时候都是不存在的，而不像物理上某个能量在没有物理过程中依旧存在。

这个所谓的“换”是相对于相对于另一个算法的时间 /空间复杂度有所不同，而不是真的拿出某样东西来进行转换。

举个例子，你把垃圾算法同时优化了时间和空间，这个新算法是什么换什么？

[Yain]

退役竞赛生答一波

时空转换是众多前人通过解决问题总结出的规律和手段。在算法竞赛中，它特指“降低时间复杂度或常数因子，但增大空间开销”和“降低空间复杂度或常数因子，但增大时间开销”。

由于储存空间有限和人为对时间的要求，我们常常需要调整算法，折衷两种资源的开销。

现实中的例子其实有很多，不必局限于“时间”和“空间”，大可以是“时间”和“钱”的相互转换等等，只要是资源开销，都可能相互转换。但是要注意，“开销”的转换，和直接用钱买时间还是有区别的。

[yukiloh]

曹德旺卖玻璃，别人玻璃只能存半年，我可以存存到你倒闭

[GeruzoniAnsasu]

#19 @l30n 的回答简短准确，咋都没人看到


y = f(x)，把从 x 计算得到 y 的过程转化成查表

[loading]

现实中也可以空间换时间。
离公司更近的房子，类似于 cpu 缓存和内存的区别。
两台一直同步的电脑分别放工位和家里，类似于数据库冗余数据。

[cmdOptionKana]

@GeruzoniAnsasu 楼主看到了，但楼主认为这是 “怎么做”，不是“为什么”。

[GeruzoniAnsasu]

@cmdOptionKana 并没有看到

前面的例子，书放书架上根本不是恰当的比喻，书不管放哪空间都没变，衣柜不管怎么整理，空间也没变

唯独#19 说的打表是“空间换时间”的正确场景，换个更快的算法 On 变 Ologn 并没有用空间来换时间

[epicnoob]

辩证思维

[cmdOptionKana]

@GeruzoniAnsasu 衣柜的例子是我提出的，所以我有必要说明，一个小衣柜，如果只能容纳一百件折叠后的衣服（无法容纳更多，也无法容纳一百件摊开的衣服），那么，使用一个更大的衣柜（足以容纳一百件摊开的衣服），这就是用更大的空间来换取了更快的速度。

这里把折叠衣服摊开的过程非常像一个函数的计算过程（都需要经过一些花费时间的操作步骤）。

[22yune]

@GeruzoniAnsasu #68 查表也是一个更简单的 y=f(x).

[Jabin]

问的是 为什么能这样
答的是 可以这样

通常别人问用这种方法怎么解决问题
我们给的答案往往是使用另一种方法解决

[kamilic]

我的理解是这样的。
计算机完成一个纯计算任务，用到的资源无非只有存储空间和 CPU 资源使用时间。
你也只能在这两者中倒腾了。。。

给出一个纯计算任务，如果直接使用 CPU 计算，则要用到 CPU 时间去处理任务，但它没有用到存储空间。
如果你事先计算好了，直接在内存去找就行了，这样没有利用到 CPU 时间就能完成任务。

前提：
不要考虑说你的时间也是时间。
也不要考虑说 CPU 运行过程中会载入内存的代码段，以及读内存需要 CPU 参与这些事。

我们只讨论这个任务结果在计算机部件中的存在。

[johnkiller]

若一个文件内容是：aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

若只保存对这个文件内容的描述，

如：a*20+b*20，

这样子，空间少了，

但是需要 CPU 进行计算得出结果，时间增加了。

[GeruzoniAnsasu]

@22yune

难到你认为计算的时间量是 0 ？
或者你没意识到所有方案的总“功耗”其实是一样的？


预计算替换掉耗时只是把时间消耗提到关注的时间窗口外而已

[diubo]

看来老板给你安排的活有点不够，都开始思考这些终极问题了

[p1gd0g]

因为空间和时间都不是无节制的。

[aut0man]

这里举到的所有例子 包括楼主自己认识到的'换'，都是成本的转换。空间成本换时间成本，而不是真的能换到失去的时间…所以 未发生的东西，有什么不能换？

[MoYi123]

乘法口诀表会背吗?

[HelloAmadeus]

因为寄存器，CPU 缓存， 内存， 硬盘的速度不一样， 价格也不一样

[vagarlee]

我觉得那个“选择”的说法是正确
从另一个角度说来，楼主的问题其实有误导的地方
因为此换非彼换，楼主举的例子里面并没有真的换这个概念，因为时间并没有变成空间，空间也并不会变成时间，
如果从结果来说，对于一个楼主举例的计算机问题来说，其实有四个可能（ 1.使用的时间长并且空间多，2.使用的时间长而空间少的，3.使用的时间短而空间多的，4.使用的时间短且空间少的），而楼主只拿了其中的两个来提问，如果把四种可能放到一起来讨论，就不会有换的感觉了…
至于楼主提到的为什么可以换的问题，按照上述的四种可能，大概可以转变为“同一个问题为什么会不一样的解决办法”？

[zacone]

这里的“换”是对`结果`的形容，为什么能换，应该从“换”的`过程`来理解。
为什么能换：因为我们针对业务特点选择不同的策略，而不同策略的执行过程，会有不同的消耗，这里可以把“换”理解为“节约”，选择对业务有利的消耗，就达到了“换”的效果。
为什么不能无限换：“节约”的前提是有“浪费”，如果不存了浪费了，就不能“换”了。
综上所述，“换”只是对过程的调整，程序在我们手中，过程当然能被调整，所以能“换”。