Изменения

Перейти к: навигация, поиск
Время работы алгоритмов
==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <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>, получаем указанную оценку.<br>
В случаем с простым алгоритмом при последующем разбиении в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Поэтому, его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.
172
правки

Навигация