知识卡片
空间换时间要计入维护成本
保存已计算结果、访问标记或额外索引,可以减少后续查找与重复运算;同时要计算空间占用、更新和失效成本。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之间的最短距离。作为算法中的关键一环,必须要判断出一个给定节点是否已经访问过。因为二叉堆实现的优先队列无法解决这个问题,通过一个单独的布