Изменения

Перейти к: навигация, поиск
Время работы алгоритма
<tex>W</tex>.push(<tex>R_2, a</tex>)
==Время работы простого и модифицированного алгоритма==Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовася в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку.В случаем с простым алгоритмом при разбиении можно гарантировать лишь <tex>|S| \ge |S_1| + 1</tex>, поэтому его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.
== Литература ==
172
правки

Навигация