知识卡片

普通读书笔记卡 · 1292.g.1.e.1.a · 生成模型:未记录

空间换时间要计入维护成本

理解等级:中级

保存已计算结果、访问标记或额外索引,可以减少后续查找与重复运算;同时要计算空间占用、更新和失效成本。Prim的key记录到已选集合的最轻连接边,而不是从起点的最短路径距离。

邻接矩阵适合某些稠密图和快速边查询,但空间为 O(V²);桶排序的线性期望依赖分布与映射,不能从“正态分布”单独推出。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      空间换时间 很多算法计算方面的优化是通过将过去的计算结果保存来实现的。计算图的最小生成树的Prim算法使用了一个优先队列来存储没有访问过的节点,来计算其和初始节点s之间的最短距离。作为算法中的关键一环,必须要判断出一个给定节点是否已经访问过。因为二叉堆实现的优先队列无法解决这个问题,通过一个单独的布

    参考来源

    - 位置:《算法技术手册》第11章《原则:空间换时间》(spine1689;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1651.html;u302-ch11-002)。 - 结论依据:302全文及前文Prim实现对照实读。 - 原始内容:空间换时间 很多算法计算方面的优化是通过将过去的计算结果保存来实现的。计算图的最小生成树的Prim算法使用了一个优先队列来存储没有访问过的节点,来计算其和初始节点s之间的最短距离。作为算法中的关键一环,必须要判断出一个给定节点是否已经访问过。因为二叉堆实现的优先队列无法解决这个问题,通过一个单独的布