知识卡片
布尔闭包时间三次方
按 k、i、j 三层循环求传递闭包,仍需 Θ(n³) 时间;布尔值可用位表示,某些机器上比存整型距离更省空间。
它的成本与 Floyd 同阶,但只保留可达性信息。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 所有结点对的最短路径 · 查看原书依据
The TRANSITIVE-CLOSURE procedure, like the Floyd-Warshall algorithm, runs in Θ(n3) time. On some computers, though, logical operations on single-bit values execute faster than arithmetic operations on integer words of
参考来源
- 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[25000,30000))。
- 结论依据:原文明确时间界,并比较布尔运算与整数存储。
- 原始内容:The T RANSITIVE -C LOSURE procedure, like the Floyd-Warshall algorithm, runs in Θ( n 3 ) time. On some computers, though, logical operations on single-bit values execute faster than arithmetic operations on integer words of