我们知道普通的背包问题具有伪多项式时间复杂度，因为其运行时间为O(nW)。我在想网络流的运行时间是否也是伪多项式时间，因为使用Ford-Fulkerson算法的网络流的运行时间为O(Cm)(其中m为边数，C为从起点出发的边容量之和)？
网络流算法的时间复杂度是否为伪多项式？
3
- CSnerd
2
1伪多项式的概念几乎完全取决于时间复杂度由输入的长度确定这一事实。在这种情况下，如果您有一组用二进制表示的容量，则通过增加单个位可以将该容量集合的大小潜在地指数级增加。从这个意义上说，算法对于输入的单个“单位”增加而言运行时间呈指数级增长。我认为它是伪多项式的。 - rliu
1这是一个不错的参考资料：http://courses.csail.mit.edu/6.854/06/scribe/s9-maxflow.pdf - Tom Swifty
1个回答
8
是的，Ford-Fulkerson算法是一种伪多项式时间算法。它的运行时间为O（Cm），其中C是离开起始节点的容量之和。由于写出数字C需要O（log C）位，因此该运行时间确实是伪多项式但不是实际多项式。
然而，对于最大流问题，确实存在强多项式时间算法，比如推送-重贴标签算法，其运行时间为O（n³）。
希望这有所帮助！
然而，对于最大流问题，确实存在强多项式时间算法，比如推送-重贴标签算法，其运行时间为O（n³）。
希望这有所帮助！
- templatetypedef
3
1这些问题属于复杂度类P还是NP完全类？网站http://www.cs.yale.edu/homes/aspnes/pinewiki/MaxFlow.html显示运行时间为O(E^2 U)。您的解决方案与该网站有何不同？ - LearningToCode
2@LearningToCode 我给出的界限比他们列出的要严格一些。他们正确地指出，切割的最大尺寸不超过EU，但是你可以通过注意到仅删除s形成的切割的容量最多为C（按我的符号表示）来给出更紧密的界限。至于这个问题是否在P或NP完全中，因为我们有用时效强的多项式算法（而不是伪多项式算法）求解最大流问题，所以最大流问题肯定在P中。它也可能是NP完全的，但没有人知道，因为我们不知道P = NP。（续...） - templatetypedef
5请记住，只有问题可以属于P或NP类问题，而不是算法。 - templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接