и модифицированные версии некоторого списка

Пусть

— основная и модифицированные версии некоторого списка символов:

. Тогда дельты, вычисленные в результате сравнения соответствующих модифицированных версий с базовой, представляются как

. В данном случае изменения не содержат конфликтов и могут быть консолидированы, приводя к результирующему представлению списка

. Оценка вычислительной сложности классического алгоритма минимального редакторского расстояния с использованием метода динамического программирования составляет

. Этой же оценкой определяется общая сложность формирования дельты для списков. При неоптимальном формировании дельты, например, путем нахождения наибольшей общей последовательности и определения дополняющих операций, оценка вычислительной сложности может быть улучшена до

, однако количество элементарных операций в полученном представлении дельты может оказаться высоким. Более детальная систематизация алгоритмов и сравнительный анализ их вычислительной сложности приводятся в [20, 21].

Содержание Назад

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий