В последних двух абзацах статьи об алгоритме Хопкрофта-Карпа для нахождения соответствия максимальной мощности в двудольном графе:
https://dl.dropboxusercontent.com/u/64823035/04569670.pdf
Время выполнения фазы равно O(m+n), где m — количество ребер в G, а n — количество вершин. Следовательно, время выполнения всего алгоритма равно O((m+n)s), где s — мощность максимального паросочетания.
Если G имеет n вершин, то m ‹= n^2/4 и s ‹ n/2, так что время выполнения ограничено величиной O(n^(5/2)).
Я не понимаю, учитывая:
m <= n^2 / 4
s <= n / 2
почему они пришли к выводу:
O((m+n)s) = O(n^(5/2))
Разве не должно быть:
O((m+n)s) = O(n^3)
Есть идеи?
Отредактировано: ссылка исправлена. Виноват.
