Нечеткое сравнение коллекций семантический и алгоритмический аспекты


Сравнение мультимножеств - часть 2


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

Сложность построения

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

В качестве примера рассмотрим процедуру сравнения двух версий мультимножества символов. Пусть

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

.




Начало  Назад  



Книжный магазин