Изменения

Время работы алгоритма оценивается как <tex>O(|\Sigma| * \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * \cdot n)</tex>, получаем указанную оценку.