知识卡片
时间与空间可以互相换取
保存可复用结果、索引或额外结构,可能减少后续计算与搜索;减少这些保存,又可能需要重复计算。这是用空间换时间及反方向取舍的基本思路。
两类资源不必总是一增一减,有时算法改进能同时减少两者。实际选择要看内存预算、输入规模和延迟需求,不能把“时间总比空间宝贵”当所有系统的通用规则。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
降低时间复杂度通常需要以提升空间复杂度为代价,反之亦然 。我们将牺牲内存空间来提升算法运行速度的 思路称为“以空间换时间”;反之,则称为“以时间换空间” 。 选择哪种思路取决于我们更看重哪个方面。在大多数情况下,时间比空
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[2254,2364))
- 结论依据:原文权衡段实质提出双向交换,限定为可能取舍。
- 原始内容:降低时间复杂度通常需要以提升空间复杂度为代价,反之亦然 。我们将牺牲内存空间来提升算法运行速度的 思路称为“以空间换时间”;反之,则称为“以时间换空间” 。 选择哪种思路取决于我们更看重哪个方面。在大多数情况下,时间比空