如何確定單工時間複雜度（即最大流量）

單純形算法據說具有指數最差情況時間複雜度。但它仍然經常用於實踐。如何確定某個問題的平均時間複雜度（用單純形法解決）。如何確定單工時間複雜度（即最大流量）

例如，什麼是最大流問題的平均時間複雜度被解決了單純形法。（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

回答