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