代码之家 › 专栏 › 技术社区 › nes1983

计算图的传递闭包所需的非对称运行时间?

graph-theory theory runtime language-agnostic

nes1983 · 技术社区 · 15 年前

在O(n^3)中很容易实现,其中n是顶点数。我想知道它是否能在O(n^2)时间内完成。

3 回复 | 直到 10 年前

Mehrdad Afshari 15 年前

^2. )它的算法。我希望如果存在这样一个算法,您可以在O(n)中解决所有对最短路径问题 ^2. )但事实并非如此。我能想到的渐近最快的算法是Dijkstra最短路径算法的一个实现,它是一个Fibonacci堆(O( N 日志 N )在不太密集的图中)。

nes1983 15 年前

MarkusQ 15 年前

你能想出一个O(kn^2+m)传递闭包/归约吗算法,其中k是传递函数中缺失/额外边的数目关闭/减少?

对于那些比我们想得更多的人来说,这仍然是一个悬而未决的问题,我会说“我不知道”。

那个

推荐文章

goofy126 · 计算理论-DFA[闭合]

7 年前

Marcos · 是否有一个术语来描述只应使用最后一个值的表格?

7 年前

ZhaiNan · 这能在O(N log(N))时间内解决3SUM吗?

7 年前

Kishore · 如何证明(g(n))=O(g(n))(g(n))

7 年前

Artemis · 为什么在二进制搜索中我们要除以2而不是其他更高的常数

7 年前

user8175891 · 单元测试的价值是否随着单元测试的复杂性而降低?

7 年前

NaSh · 求图中局部最小值/最大值的爬山算法的时间复杂度

9 年前

magic-sudo · 排序arrya的最有效方法[已关闭]

10 年前

user1501127 · 如果L={0^n1^n|n>0}是L^c(L的补码)正则的吗?

10 年前

Dan Drews · 为什么替身能像他们那样工作

11 年前