Изменения

Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|\mathtt{Inverse}|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки.

*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>;*<tex>\mathtt{Part}[i]</tex> {{---}} указатель на голову [[Список#Двусвязный список|двусвязного списка]], содержащего состояния, принадлежащие классу <tex> i </tex>;*<tex>\mathtt{Card}[i]</tex> {{---}} количество состояний в классе <tex>i</tex>;*<tex>\mathtt{Place}[r]</tex> {{---}} указатель на состояние <tex>r</tex> в списке <tex>\mathtt{Part[Class}[r]]</tex>.

Чтобы эффективно находить множество <tex>\mathtt{Inverse}</tex>, построим массив <tex>\mathtt{Inv}</tex>, который для состояния <tex>r</tex> и символа <tex>a</tex> в <tex>\mathtt{Inv}[r][a]</tex> хранит множество состояний, из которых существует переход в <tex>r</tex> по символу <tex>a</tex>. Так как наш алгоритм не меняет изначальный автомат, то массив <tex>\mathtt{Inv}</tex> можно построить перед началом основной части алгоритма, что займет <tex>O(|\Sigma| |Q|)</tex> времени.

Теперь научимся за <tex>O(|\mathtt{Inverse}|)</tex> обрабатывать множество <tex>T'</tex> и разбивать классы. Для этого нам понадобится следующая структура:*<tex>\mathtt{Counter}</tex> {{---}} количество классов;*<tex>\mathtt{Involved}</tex> {{---}} список из номеров классов, содержащихся во множестве <tex>T'</tex>;*<tex>\mathtt{Size}</tex> {{---}} целочисленный массив, где <tex>\mathtt{Size}[i]</tex> хранит количество состояний из класса <tex>i</tex>, которые содержатся в <tex>\mathtt{Inverse}</tex>;*<tex>\mathtt{Twin}</tex> {{---}} массив, хранящий в <tex>\mathtt{Twin}[i]</tex> номер нового класса, образовавшегося при разбиении класса <tex>i</tex>.

Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>\mathtt{InQueue}</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>\mathtt{InQueue}[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди. Так как при разбиении очередного класса <tex>R</tex> на подклассы <tex>R_1</tex> и <tex>R_2</tex> мы в действительности создаем лишь один новый класс, то замена класса <tex>R</tex> в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом <tex>\mathtt{InQueue}</tex>. В результате каждая операция с очередью требует <tex>O(1)</tex> времени.