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

Ивтекстил𚷕 читать далее. |

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


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

Ниже приведен пример сравнения двух версий множества натуральных чисел

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


Начало  Назад  Вперед



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