275
правок
Изменения
→Минусы алгоритма Укконена
== Минусы алгоритма Укконена ==
Не смотря на то, что данный алгоритм является одном из самых простых алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его не часто используют на практике:
# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно<ref>[https://books.google.ru/books?id=sGDXz53FwM4C&pg=PP11&lpg=PP11&dq=Dany+Breslauer,+Giuseppe+F.+Italiano:+Near+Real-Time+Suffix+Tree+Construction+via+the+Fringe+Marked+Ancestor+Problem.&source=bl&ots=utJ8jnql5h&sig=qjCsObtl4pvkIVOSgwaYc3podxk&hl=ru&sa=X&ei=thcsVaexJ-HXyQP-vIC4BQ&ved=0CEMQ6AEwBQ#v=onepage&q&f=falseDany Breslauer, Giuseppe F. Italiano: Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.]</ref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</tex> времени.
== Реализация ==
