Изменения

Перейти к: навигация, поиск
м
Асимптотика
В применении к задаче [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин — <tex>O(N)</tex>, рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(N^2 log N + 2N^3)</tex>.
== Литература ==
42
правки

Навигация