322
правки
Изменения
Нет описания правки
Действительно, данный метод может работать даже не за <tex> O(n^4) </tex>, а медленнее, более того, мне вообще непонятно, как оценить время его работы точнее, чем это сделано сейчас. Думаю, можно оставить текущую оценку, так как дальше в статье все равно разбирается алгоритм за <tex> O(n^3) </tex>, а этот вариант полезен скорее для понимания алгоритма, чем для практики. --[[Участник:Sementry|Мейнстер Д.]] 13:49, 10 марта 2012 (GST)
После применения операции могут исчезать нули на ребрах между <tex>X_c</tex> и <tex>Y_c</tex>. Из-за этого оценка <tex>O(n^5)</tex> перестает быть очевидной. Я не знаю, верна ли она на самом деле, но можно просто показать, что алгоритм завершается (в той же статье есть доказательство). --[[Участник:Igor buzhinsky|Игорь Бужинский]] 23:58, 11 марта 2012 (GST)
