这可能是一个愚蠢的问题，但为什么复杂性不取决于图中存在的边的权重？
问问题
123 次
1 回答
1
有许多不同的图算法，在某些情况下，复杂性确实取决于边权重。例如，Ford-Fulkerson 最大流算法的运行时间为 O(mF)，其中 F 是最大可能流，它取决于边的最大容量。其他算法（如 Dijkstra 算法）的运行时间与边长无关，因为在计算模型中假设对这些权重的操作总是需要 O(1) 时间。
一般来说，运行时间依赖于图中边的权重/容量/长度的算法通过基于这些边的容量/权重/长度进行多次迭代来获得它们的依赖关系。如果算法仅对权重等进行数值计算，则通常不存在依赖性，因为算术运算通常仅被认为需要时间 O(1)，除非有理由不相信。
希望这可以帮助！
于 2013-11-09T03:13:35.783 回答