如何确定单纯形时间复杂度（即最大流）
据说单纯形算法具有指数最坏情况时间复杂度。但它在实践中仍然经常被使用。如何确定某个问题（用单纯形法解决）的平均时间复杂度。
例如，用单纯形算法解决最大流问题的平均时间复杂度是多少。 （Wiki 对于所有其他算法都有时间复杂度）
感谢您的宝贵时间。
Simplex algorithm is said to have exponential worst case time complexity. Yet it is still often used in practice. How can you determine the average time complexity for a certain problem (being solved with simplex).
For example, what is the average time complexity of the maximum flow problem being solved with simplex algorithm. (Wiki has time complexity for all other algorithms)
Thank you for your time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
平均情况复杂度相当难以分析，它取决于线性程序的分布。我相信在一些常见的分布下它被计算为多项式时间。但我目前找不到该论文。
编辑：是的，以下是来源：
Nocedal, J. 和 Wright, SJ Numerical Optimization。纽约：Springer-Verlag，1999。Forsgren
，A.；吉尔，PE；和 Wright，MH“非线性优化的内部方法”。 SIAM Rev. 44, 525-597, 2002。
我在第一本书中读到了它，显然它在另一篇论文（Forsgren）中得到了证明。您可以在大学图书馆找到其中之一。
The average case complexity is rather difficult to analyze and it depends on the distribution of your linear program. I believe that it was worked out to be polynomial time under some common distributions. I currently cannot find the paper though.
EDIT: Yes, here are the sources:
Nocedal, J. and Wright, S. J. Numerical Optimization. New York: Springer-Verlag, 1999.
Forsgren, A.; Gill, P. E.; and Wright, M. H. "Interior Methods for Nonlinear Optimization." SIAM Rev. 44, 525-597, 2002.
I read it in the first book and apparently it was proven in a separate paper (Forsgren). You could find either in a university library.
如果还觉得有趣的话。单纯形的时间复杂度为 O((n+m)*n)。
n - 变量数量。
m - 不平等约束。
为什么？因为在 n 的情况下迭代次数不能超过 n + m
这是顶点数量的上限。
但这个上限是 n 的指数。
If it is still interesting. Time complexity of simplex is O((n+m)*n).
n - number of variables.
m - inequality constraints.
Why? Because the number of iterations could be no more than n + m in case of n
which is an upper bound on the numbers of vertices .
But this upper bound is exponential in n.