Редактирование: СНМ(списки с весовой эвристикой)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[СНМ (списки с весовой эвристикой)]]
+
== Весовая эвристика ==
 +
{{Определение|
 +
definition =
 +
'''Весовая эвристика''' - улучшение наивной реализации СНМ, при котором список включает поле длины списка, и добавление идет всегда меньшего списка к большему.
 +
}}
 +
 
 +
== Оценка для весовой эвристики ==
 +
 
 +
{{Утверждение
 +
|statement=При использовании связанных списков для представления СНМ и применении весовой эвристики, последовательность из <tex>m</tex> операций MAKE_SET, UNION, и FIND_SET, <tex>n</tex> из которых составляют операции MAKE_SET, требует для выполнения <tex>O(m+n </tex> lg <tex> n)</tex> времени.
 +
|proof = Вычислим верхнюю границу количества обновлений указателя на представителя для каждого множества из <tex>n</tex> элементов. Рассмотрим некий фиксированный объект. Когда мы обновляем указатель на представителя в объекте, он должен находиться в меньшем из множестав. Следовательно, при первом обновлении образованное множество хранит не менее 2 элементов, при втором не менее 4 элементов, и т.д. Таким образом, при <tex>k \leqslant\ n</tex>}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)