如何确定单工时间复杂度（即最大流量）

单纯形算法据说具有指数最差情况时间复杂度。但它仍然经常用于实践。如何确定某个问题的平均时间复杂度（用单纯形法解决）。如何确定单工时间复杂度（即最大流量）

例如，什么是最大流问题的平均时间复杂度被解决了单纯形法。（Wiki有时间复杂度为所有其它算法）

谢谢您的时间。

2011-12-27 Ben

听起来像作业/测试问题。 – 2011-12-27 23:46:57

+1这实际上是一个非常深刻的问题，我不确定以前是否有人解决过这个问题。我很好奇听到答案。 – templatetypedef 2011-12-27 23:58:28

平均情况下的复杂性是相当困难的分析，它取决于你的线性程序的分发。我相信在一些普通的分布下，它被证明是多项式时间。我目前无法找到该论文。

编辑：是的，这里有来源：

Nocedal，J.和赖特，S. J.数值优化。纽约：施普林格出版社，1999年。

Forsgren，A .;吉尔，体育。和Wright，M. H.“用于非线性优化的内部方法”。 SIAM牧师44，525-597，2002。

我在第一本书读它，显然它是在一个单独的文件（Forsgren）证明。你可以在大学图书馆找到。

2011-12-28 00:05:32 tskuzzy

如果它仍然有趣。单纯形的时间复杂度为O（（n + m）* n）。

n - 变量的数量。

m - 不等式约束。

为什么？因为对于顶点数的上界，n 的迭代次数可能不超过n + m。

但这上限是n的指数。

2015-12-05 14:40:50

回答