知识卡片

普通读书笔记卡 · 3663.a.1

布尔闭包时间三次方

理解等级:中级

按 k、i、j 三层循环求传递闭包,仍需 Θ(n³) 时间;布尔值可用位表示,某些机器上比存整型距离更省空间。

它的成本与 Floyd 同阶,但只保留可达性信息。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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