Изменения

Перейти к: навигация, поиск
Псевдокод
for all <tex>a \in \Sigma</tex>
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 \leftarrow = R \cap \delta^{-1} (S, a) </tex> <tex>R_2 \leftarrow = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> & <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if <tex> |R_1| \le |R_2|</tex> then
<tex>W</tex>.push(<tex>R_1</tex>)
else
<tex>W</tex>.push(<tex>R_2</tex>)
==Время работы алгоритма==
Благодаря системе добавления классов состояний в очередь, каждое ребро будет рассмотрено не более чем <tex>\log{n}</tex> раз. А так как ребер у нас порядка <tex> |\Sigma| * n </tex> то получаем <tex> O(n\log{n})</tex>
Анонимный участник

Навигация