403
правки
Изменения
→Модификация
Каждая итерация цикла <tex> while </tex> не может быть выполнена быстрее, чем за <tex> O(|Inverse|) </tex> для текущей пары <tex> (C,a)</tex>. Покажем, как достичь этой оценки.
===qqqМодификация===Разбиение <tex> P </tex> можно поддерживать четырьмя массивами:*<tex>Class[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>;*<tex>Part[i]</tex> {{---}} указатель на голову двусвязного списка, содержащего состояния, принадлежащие классу <tex> i </tex>;*<tex>Card[i]</tex> {{---}} количество состояний в классе <tex>i</tex>;*<tex>Place[r]</tex> {{---}} указатель на состояние <tex>r</tex> в списке <tex>Part[Class[r]]</tex>. Так как мы храним указатель, где находится состояние в двусвязном списке, то операцию перемещения состояния из одного класса в другой можно выполнить за <tex>O(1)</tex>. Для быстрой проверки, находится ли пара <tex>(C,a)</tex> в очереди <tex>S</tex>, будем использовать массив <tex>InList</tex> размера <tex>|Q| \times |\Sigma|</tex>, где <tex>InList[C][a] = true</tex>, если пара <tex>(C,a)</tex> содержится в очереди. Так как при разбиении очередного класса <tex>R</tex> на подклассы <tex>R_1</tex> и <tex>R_2</tex> мы в действительности создаем лишь один новый класс, то замена класса <tex>R</tex> в очереди на подклассы, образовавшиеся при разбиении, сводится лишь к взаимодействию с массивом <tex>InList</tex>. В итоге работа с очередью на каждой итерации требует <tex>O(1)</tex> времени.
===Время работы===
