知识卡片
图算法复杂度同时依赖顶点边数
邻接表配合堆的某些算法可为 O((V+E) log V),矩阵版本可为 O(V²+E)。当 E=Θ(V) 时前者通常渐近更优;当 E=Θ(V²) 时后者的 O(V²) 优于前者的 O(V² log V)。交界量级约 E=Θ(V²/log V)。
稀疏通常指边数相对 V² 较少,并不必然意味着 E=Θ(V);图可能含孤立点或处在中间密度。大O只给上界,不应单凭两个上界断定实际速度。
165的03306–03308比较不同规模和密度的历史数据;Bellman-Ford支持负边,Dijkstra只适用于非负边。不同实验的次数不同,稀疏与稠密结果只能在各自条件下比较。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 图算法复杂度同时依赖顶点边数
- · 比较
原书出处 · 2 处
- · 查看原书依据
图分析 当使用本章的算法时,决定使用邻接表还是邻接矩阵的最重要因素是图是否为稀疏图。算法的性能是和图的顶点数|V|还有边数|E|相关的。和其他算法书一样,我们简化了性能的公式,无论在最好、最坏还是平均情况下,我们都使用V、E的大O记法来表示性能。O(V)表示需要和图中顶点数成直接比例的计算步数。但是
- · 查看原书依据
基准测试数据 产生一个“随机图”是非常困难的。在表6-2中,我们使用的是有V=k2+2个顶点,以及E=k3-k2+2k条边的图(图的构造细节参见代码库中的实现)。注意边的数目大概是n1.5,n是顶点的数目。使用了优先队列的Dijkstra算法的性能最好,Bellman-Ford的性能紧随其后。我们可
参考来源
- 位置:《算法技术手册》第6章《图分析》(spine1563;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1526.html;u146-ch06-004)。
- 结论依据:146全文及03280复杂度表实读。
- 原始内容:图分析 当使用本章的算法时,决定使用邻接表还是邻接矩阵的最重要因素是图是否为稀疏图。算法的性能是和图的顶点数|V|还有边数|E|相关的。和其他算法书一样,我们简化了性能的公式,无论在最好、最坏还是平均情况下,我们都使用V、E的大O记法来表示性能。O(V)表示需要和图中顶点数成直接比例的计算步数。但是
- 位置:《算法技术手册》第6章《比较》(spine1579;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1542.html;u165-ch06-004)。
- 结论依据:165的03306–03308比较不同规模和密度的历史数据;Bellman-Ford支持负边,Dijkstra只适用于非负边。不同实验的次数不同,稀疏与稠密结果只能在各自条件下比较。
- 原始内容:基准测试数据 产生一个“随机图”是非常困难的。在表6-2中,我们使用的是有V=k2+2个顶点,以及E=k3-k2+2k条边的图(图的构造细节参见代码库中的实现)。注意边的数目大概是n1.5,n是顶点的数目。使用了优先队列的Dijkstra算法的性能最好,Bellman-Ford的性能紧随其后。我们可