Вычислительная сложность наивной реализации, основанной

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

. Сложность оптимальной реализации, основанной на предварительной сортировке исходных множеств, например, методом пирамидальной сортировки или методом слияния списков, можно оценить как

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

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

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

. Пусть

— основная и модифицированная версии коллекции, содержащие следующие элементы:

. Тогда дельта, вычисленная путем сравнения двух версий множества, представляется как

.

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

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