Симплексный алгоритм, как говорят, имеет экспоненциальную временную сложность наихудшего случая. Тем не менее, он все еще часто используется на практике. Как вы можете определить среднюю временную сложность для определенной задачи (решаемой с помощью симплексного метода).
Например, какова средняя временная сложность задачи о максимальном потоке, решаемой с помощью симплексного алгоритма. (В Wiki есть временная сложность для всех других алгоритмов)
Спасибо за ваше время.