Изменения

Самым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В работе<ref>[http://citeseerciteseerx.uarkist.psu.edu:8080/citeseerx/viewdoc/summarydownload;jsessionid=EF3DD7271F6E8907A154A540D93F2B0CA511A421C93DF66BDCC32A0E133D1F99?doi=10.1.1.59.8276 &rep=rep1&type=pdf Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions]</ref>, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.