Изменения
→Время работы: n1 и n2 оптимизация
==Время работы==
:Итак, алгоритм Куна можно представить как серию из <tex>n</tex> запусков обхода в глубину на всём графе.
:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество ребер, что в худшем случае есть <tex>O(n^3)</tex>:Если явно задано разбиение графа на две доли размером <tex>n_1</tex> и <tex>n_2</tex>, то можно запускать <tex>\mathtt{dfs}</tex> только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex>, где <tex>m</tex> - число ребер. В худшем случае это составляет <tex>O(n_1^2n_2)</tex></tex>.
==Ссылки==
