editor
177
правок
Изменения
м
Поправлено оформление псевдокода
<tex>Q</tex> {{---}} очередь состояний, соответствующих множествам, состоящих из состояний НКА.
<tex>s</tex> {{---}} стартовое состояние НКА.
<tex>Q</tex>.push(\{<tex>s\})</tex>}) <tex>whilenot isEmpty(</tex> <tex>notQ</tex> ) <tex>(isEmpty(Q))</tex> .pop(<tex>Q.pop(q_d)</tex>)
<tex>for</tex> <tex>c \in \Sigma</tex>
<tex>p_d = \varnothing</tex> = <tex>for\varnothing</tex> for <tex>q \in q_d</tex> <tex>p_d </tex> = <tex>p_d \cup \delta(q, c)</tex> <tex>if(</tex> <tex>(p_d</tex> <tex>haven't</tex> <tex>been</tex> <tex>in</tex> <tex>Q</tex>) <tex>Q</tex>.push(<tex>p_d)</tex>)
===Асимптотика===
Так как количество подмножеств множества состояний НКА не более, чем <tex>2^n</tex>, а каждое подмножество мы обрабатываем ровно один раз за время <tex>O(n)</tex>, получаем верхнюю оценку времени работы алгоритма {{---}} <tex>O(n \cdot 2^n)</tex>.
