知识卡片

普通读书笔记卡 · 5654.c.3.d

时间与空间可以互相换取

理解等级:中级

保存可复用结果、索引或额外结构,可能减少后续计算与搜索;减少这些保存,又可能需要重复计算。这是用空间换时间及反方向取舍的基本思路。

两类资源不必总是一增一减,有时算法改进能同时减少两者。实际选择要看内存预算、输入规模和延迟需求,不能把“时间总比空间宝贵”当所有系统的通用规则。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      降低时间复杂度通常需要以提升空间复杂度为代价,反之亦然 。我们将牺牲内存空间来提升算法运行速度的 思路称为“以空间换时间”;反之,则称为“以时间换空间” 。 选择哪种思路取决于我们更看重哪个方面。在大多数情况下,时间比空

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[2254,2364)) - 结论依据:原文权衡段实质提出双向交换,限定为可能取舍。 - 原始内容:降低时间复杂度通常需要以提升空间复杂度为代价,反之亦然 。我们将牺牲内存空间来提升算法运行速度的 思路称为“以空间换时间”;反之,则称为“以时间换空间” 。 选择哪种思路取决于我们更看重哪个方面。在大多数情况下,时间比空