Сравнение списков - часть 4

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

и

.

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

.

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

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

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