1

假设单纯形算法的最坏情况时间复杂度为 O(2^n)。单纯形算法中最坏的情况是什么？为了计算时间复杂度，我想知道最坏的情况。

4

1 回答 1

1

在最坏的情况下，单纯形需要访问2^n顶点（Klee & Minty 1972），如果考虑退化，这也可能是重复访问的同一点。

尽管如此，单纯形算法在各种概率分布下具有多项式平均情况复杂度。通过这样的原理，证明了对单纯形输入的轻微随机扰动（几乎改变了原始数据）会导致预期运行时间变为多项式（Spielman and Teng - 2001）。

参考：

于 2020-04-15T01:41:18.260 回答