Изменения
reformatting a bit
*<tex>\mathtt{Q}</tex> {{---}} множество состояний ДКА,
*<tex>\mathtt{F}</tex> {{---}} множество терминальных состояний,
*<tex>\mathtt{\delta}</tex> {{---}} функция перехода (<tex>\delta (r,\ a)</tex> {{- --}} состояние, в которое можно совершить переход из <tex>r</tex> по символу <tex>a</tex>),
*<tex>\mathtt{S}</tex> {{---}} очередь пар <tex>\langle C,\ a \rangle</tex>,
*<tex>\mathtt{P}</tex> {{---}} разбиение множества состояний ДКА,
Каждая итерация цикла <tex> \mathrm{while} </tex> может быть выполнена за <tex> O(|Q| + |\mathtt{Inverse}|) </tex> для текущей пары <tex>\langle C,\ a \rangle</tex>. Покажем, как можно достичь этой оценки.
Классы разбиения <tex>P</tex> будем поддерживать с помощью множеств на [[Хеш-таблица | хэш-таблицах]] (само же разбиение {{- --}} обычный вектор, индекс {{--- }} номер класса). Это позволит нам эффективно переносить состояния из одного класса в другой (за <tex>O(1)</tex>).
*<tex>\mathtt{Class}[r]</tex> {{---}} номер класса, которому принадлежит состояние <tex>r</tex>,
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2)</tex>:
<tex>\mathrm{cnt1 } \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_1]</tex> <tex>\mathrm{cnt2 } \leftarrow </tex> '''size of''' <tex>\mathtt{P}[R_2]</tex> '''if''' <tex> \mathrm{cnt1 } \leqslant \mathrm{cnt2 } </tex>
<tex>\mathtt{swapClasses}(R_1,\ R_2)</tex>
'''for''' <tex>c \in \Sigma</tex>
<tex>\mathtt{Class}[r] = i</tex>
Стоит пояснить, зачем требуется менять содержимое множеств (<tex>\mathtt{swapClasses}(R_1,\ R_2)</tex>). Почему нельзя просто проверить <tex> \mathrm{cnt1 } \leqslant \mathrm{cnt2 } </tex>, и на основе этого добавить либо первое, либо второе? Ответ кроется в том, что де-факто мы создаем только один новый класс, старый класс (<tex>R_1</tex>) мы только меняем в размерах. Потому если <tex>\langle R_1, c \rangle</tex> уже есть в очереди, у нас не остается иного выбора, кроме как добавить <tex>\langle R_2, c \rangle</tex>. Однако, может случится, что <tex>|R_2| > |R_1| </tex>, что как раз и может потенциально дать квадратичную ассимптотику (логарифмическая достигается как раз за счет того, что добавляемый в очередь подкласс - меньший).
Причем, стоит отметить, что собственно наличие/отсутствие пары в очереди можно не проверять. Если для некоторого <tex>c</tex> пара <tex>\langle R_1, c \rangle</tex> уже была в очереди, то мы добавим её "вторую половинку" <tex>\langle R_2, c \rangle</tex>. Если её в очереди не было, то мы вольны сами выбирать, какой подкласс добавлять в очередь, и таким образом добавляем опять же <tex>\langle R_2, c \rangle</tex>.
<tex>\mathtt{pushSetsToQueue}(\mathtt{Queue},\ R_1,\ R_2)</tex>:
<tex>\mathrm{cnt1 } \leftarrow \mathtt{ClassInv}[R_1][c]</tex> <tex>\mathrm{cnt2 } \leftarrow \mathtt{ClassInv}[R_2][c]</tex> '''if''' <tex> \mathrm{cnt1 } \leqslant \mathrm{cnt2 } </tex>
<tex>\mathtt{swapClasses}(R_1,\ R_2)</tex>
'''for''' <tex>c \in \Sigma</tex>
