СНМ (списки с весовой эвристикой) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:19Z

rollbackEdits.php mass rollback

23.128.248.38 в 03:46, 1 сентября 2022

2022-09-01T03:46:27Z

Adel: /* Реализация с весовой эвристикой */

2014-06-12T12:35:55Z

‎Реализация с весовой эвристикой

Adel в 12:35, 12 июня 2014

2014-06-12T12:35:05Z

Adel: /* Реализация с весовой эвристикой */

2014-06-10T23:46:38Z

‎Реализация с весовой эвристикой

Adel: /* Реализация с весовой эвристикой */

2014-06-10T23:46:08Z

‎Реализация с весовой эвристикой

Adel в 23:44, 10 июня 2014

2014-06-10T23:44:11Z

Adel: /* Источники */

2014-06-10T23:34:35Z

‎Источники

Adel: /* Ссылки */

2014-06-10T23:33:33Z

‎Ссылки

194.85.161.2 в 12:22, 7 июня 2012

2012-06-07T12:22:28Z

← Предыдущая		Версия 16:38, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большему при объединении множеств.		'''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большему при объединении множеств.

← Предыдущая		Версия 03:46, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большему при объединении множеств.		'''Весовая эвристика''' (weighted-union heuristic) {{ --- }} улучшение наивной реализации СНМ на списках с указателями на представителя. Позволяет добиться улучшения асимптотики с <tex>O(n^2)</tex> до <tex>O(n \log n)</tex> благодаря добавлению меньшего списка к большему при объединении множеств.

@@ Строка 23: / Строка 23: @@
       s[i].count  = 1  <font color = "green">// храним только для представителя</font>
-  '''function''' find(x): <font color = "green">// подразумевается, что x {{ --- }} ссылка на один из элементов</font>
+  '''T''' find(x): <font color = "green">// подразумевается, что x {{ --- }} ссылка на один из элементов</font>
     '''return''' x.head.set

@@ Строка 5: / Строка 5: @@
 Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.
-При такой реализации операция <math> \mathrm {init} </math> для создания n множеств состоящих из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции <math> \mathrm {findSet} </math> достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция <math> \mathrm {union} </math>. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
+При такой реализации операция <tex> \mathrm {init} </tex> для создания n множеств состоящих из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции <tex> \mathrm {findSet} </tex> достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция <tex> \mathrm {union} </tex>. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
-Нетрудно придумать последовательность из <tex>n - 1</tex> операций <math> \mathrm {union} </math>, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция <math> \mathrm {union} </math> обновляет <tex>i</tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1</tex> операциями <math> \mathrm {union} </math> равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции <math> \mathrm {union} </math> составляет <tex>O(n)</tex>.
+Нетрудно придумать последовательность из <tex>n - 1</tex> операций <tex> \mathrm {union} </tex>, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция <tex> \mathrm {union} </tex> обновляет <tex>i</tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1</tex> операциями <tex> \mathrm {union} </tex> равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции <tex> \mathrm {union} </tex> составляет <tex>O(n)</tex>.
 == Реализация с весовой эвристикой ==
-Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция <math> \mathrm {union} </math> по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций <math> \mathrm {union} </math> требует <tex>O(n \log n)</tex> действий.
+Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция <tex> \mathrm {union} </tex> по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций <tex> \mathrm {union} </tex> требует <tex>O(n \log n)</tex> действий.
 '''Псевдокод:'''
@@ Строка 45: / Строка 45: @@
 {{Утверждение
-|statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции <math> \mathrm {init} </math> для n элементов и m операций <math> \mathrm {union} </math> и <math> \mathrm {findSet} </math>, требует для выполнения <tex>O(m+n \log n)</tex> действий.
+|statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции <tex> \mathrm {init} </tex> для n элементов и m операций <tex> \mathrm {union} </tex> и <tex> \mathrm {findSet} </tex>, требует для выполнения <tex>O(m+n \log n)</tex> действий.
-|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях <math> \mathrm {union} </math>. Рассмотрим количество обновлений отдельно для каждого элемента.
+|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях <tex> \mathrm {union} </tex>. Рассмотрим количество обновлений отдельно для каждого элемента.
 Оказывается, что для каждого элемента мы можем обновить указатель не более <tex>O(\log n)</tex> раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго {{ --- }} четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит <tex>O(\log n)</tex>.
@@ Строка 52: / Строка 52: @@
 Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет <tex>O(n \log n)</tex>.
-Необходимо также отметить, что слить два списка и обновить поле длины при выполнении <math> \mathrm {union} </math> можно за константное количество операций (последние три строчки в псевдокоде).
+Необходимо также отметить, что слить два списка и обновить поле длины при выполнении <tex> \mathrm {union} </tex> можно за константное количество операций (последние три строчки в псевдокоде).
-Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция <math> \mathrm {init} </math> за <tex>O(n)</tex>, <tex>O(m)</tex> операций <math> \mathrm {findSet} </math> и часть работы операции <math> \mathrm {union} </math> на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией <math> \mathrm {union} </math> для каждого элемента за <tex>O(n \log n)</tex> действий.
+Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция <tex> \mathrm {init} </tex> за <tex>O(n)</tex>, <tex>O(m)</tex> операций <tex> \mathrm {findSet} </tex> и часть работы операции <tex> \mathrm {union} </tex> на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией <tex> \mathrm {union} </tex> для каждого элемента за <tex>O(n \log n)</tex> действий.
 }}

@@ Строка 16: / Строка 16: @@
   s[n]
   '''function''' init():
-    '''for''' i = 0 '''to''' n - 1:
+    '''for''' i = 0 '''to''' n - 1
       s[i].set  = i    <font color = "green">// номер-идентификатор множества</font>
       s[i].next = null

@@ Строка 5: / Строка 5: @@
 Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.
-При такой реализации операция init для создания n множеств состоящих из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции findSet достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция union. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
+При такой реализации операция <math> \mathrm {init} </math> для создания n множеств состоящих из одного элемента займет <tex>O(n)</tex> времени. Для выполнения операции <math> \mathrm {findSet} </math> достаточно перейти по ссылке на представителя за <tex>O(1)</tex>. Узким местом такой реализации является операция <math> \mathrm {union} </math>. Слить списки и обновить указатели на представителя для одного из списков мы можем лишь за время пропорциональное количеству элементов.
-Нетрудно придумать последовательность из <tex>n - 1</tex> операций union, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция union обновляет <tex>i</tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1</tex> операциями union равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции union составляет <tex>O(n)</tex>.
+Нетрудно придумать последовательность из <tex>n - 1</tex> операций <math> \mathrm {union} </math>, требующую <tex>O(n^2)</tex> времени. Достаточно каждый раз сливать одно и тоже множество с одним новым элементом в том порядке, чтобы требовалось обновить указатели на представителя именно элементам "большого" множества. Поскольку <tex>i</tex>-ая операция <math> \mathrm {union} </math> обновляет <tex>i</tex> указателей, общее количество указателей, обновленных всеми <tex>n - 1</tex> операциями <math> \mathrm {union} </math> равно <tex>\sum\limits_{i=1}^{n-1} i = O(n^2)</tex>. Отсюда следует, что амортизированное время выполнения операции <math> \mathrm {union} </math> составляет <tex>O(n)</tex>.
 == Реализация с весовой эвристикой ==
-Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция union по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций union требует <tex>O(n \log n)</tex> действий.
+Недостаток наивной реализации проявляется при слиянии относительно большого множества с множеством из одного элемента. В наивной реализации список указанный первым всегда подвешивается ко второму. Хотя в данном случае гораздо выгоднее подвесить меньший список к большему, обновив один указатель на представителя, вместо обновления большого числа указателей в первом списке. Отсюда следуют очевидная оптимизация {{ --- }} будем для каждого множества хранить его размер и изменять указатели на представителя всегда элементам из "меньшего" списка. Хотя одна операция <math> \mathrm {union} </math> по-прежнему может потребовать <tex>\Omega(n)</tex> действий, если оба множества имеют <tex>\Omega(n)</tex> членов, но последовательность из <tex>n</tex> операций <math> \mathrm {union} </math> требует <tex>O(n \log n)</tex> действий.
 '''Псевдокод:'''
   s[n]
-  init():
+  '''function''' init():
-     for i = 0 to n - 1:
+   '''for''' i = 0 '''to''' n - 1:
-         s[i].set  = i    // номер-идентификатор множества
+     s[i].set  = i    <font color = "green">// номер-идентификатор множества</font>
-         s[i].next = null
+     s[i].next = null
-         s[i].head = s[i]
+     s[i].head = s[i]
-         s[i].tail = s[i] // храним только для представителя
+     s[i].tail = s[i] <font color = "green">// храним только для представителя</font>
-         s[i].count  = 1  // храним только для представителя
+     s[i].count  = 1  <font color = "green">// храним только для представителя</font>
-  find(x): // подразумевается, что x {{ --- }} ссылка на один из элементов
+  find(x): <font color = "green">// подразумевается, что x {{ --- }} ссылка на один из элементов</font>
       return x.head.set
-  union(x, y):
+  '''function''' union(x, y):
-     x = x.head
+   x = x.head
-     y = y.head
+   y = y.head
-     if x == y:
+   '''if''' x == y
-         return
+     '''return'''
-     else:
+   '''else'''
-         if x.count > y.count:
+     '''if''' x.count > y.count
-             swap(x, y)
+       swap(x, y)
-         i = x.head
+     i = x.head
-         while i != null:
+     '''while''' i != null
-             i.head = y
+       i.head = y
-             i = i.next
+       i = i.next
-         y.tail.next = x.head // соединили списки
+     y.tail.next = x.head <font color = "green">// соединили списки</font>
-         y.tail = x.tail
+     y.tail = x.tail
-         y.count += x.count
+     y.count += x.count
 == Доказательство оценки времени выполнения ==
 {{Утверждение
-|statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции init для n элементов и m операций union и findSet, требует для выполнения <tex>O(m+n \log n)</tex> действий.
+|statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции <math> \mathrm {init} </math> для n элементов и m операций <math> \mathrm {union} </math> и <math> \mathrm {findSet} </math>, требует для выполнения <tex>O(m+n \log n)</tex> действий.
-|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях union. Рассмотрим количество обновлений отдельно для каждого элемента.
+|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях <math> \mathrm {union} </math>. Рассмотрим количество обновлений отдельно для каждого элемента.
 Оказывается, что для каждого элемента мы можем обновить указатель не более <tex>O(\log n)</tex> раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго {{ --- }} четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит <tex>O(\log n)</tex>.
@@ Строка 52: / Строка 52: @@
 Таким образом, общее время, необходимое для обновления указателей для n элементов, составляет <tex>O(n \log n)</tex>.
-Необходимо также отметить, что слить два списка и обновить поле длины при выполнении union можно за константное количество операций (последние три строчки в псевдокоде).
+Необходимо также отметить, что слить два списка и обновить поле длины при выполнении <math> \mathrm {union} </math> можно за константное количество операций (последние три строчки в псевдокоде).
-Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция init за <tex>O(n)</tex>, <tex>O(m)</tex> операций findSet и часть работы операции union на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией union для каждого элемента за <tex>O(n \log n)</tex> действий.
+Отсюда легко понять, что время необходимое для выполнения всей последовательности операций составит <tex>O(m + n \log n)</tex>. Операция <math> \mathrm {init} </math> за <tex>O(n)</tex>, <tex>O(m)</tex> операций <math> \mathrm {findSet} </math> и часть работы операции <math> \mathrm {union} </math> на обновление поля длины и слияния списков, каждая из которых выполняется за константное время, а также суммарное время обновления указателей на представителя операцией <math> \mathrm {union} </math> для каждого элемента за <tex>O(n \log n)</tex> действий.
 }}

@@ Строка 60: / Строка 60: @@
 * [[СНМ(наивные реализации)]]
 * [[СНМ(реализация с помощью леса корневых деревьев)]]
 == Ссылки ==

@@ Строка 66: / Строка 66: @@
 == Ссылки ==
 * [http://habrahabr.ru/blogs/algorithm/104772/ habrahabr.ru - Система непересекающихся множеств и её применения]
 [[Категория: Дискретная математика и алгоритмы]]

@@ Строка 2: / Строка 2: @@
 == Проблема наивной реализации ==
-[[Файл:ve.png|thumb|600px|Реализация без весовой эвристики]]
+[[Файл:ve.png|right|600px|Оценка количества переподвешиваний]]
 Рассмотрим реализацию системы непересекающихся множеств с помощью списков. Для каждого элемента списка будем хранить указатель на представителя и на следующий элемент в списке.
@@ Строка 46: / Строка 46: @@
 {{Утверждение
 |statement=При реализации СНМ на списках с указателями на представителя и применении весовой эвристики, последовательность из операции init для n элементов и m операций union и findSet, требует для выполнения <tex>O(m+n \log n)</tex> действий.
-|proof = [[Файл:ve2.png|thumb|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях union. Рассмотрим количество обновлений отдельно для каждого элемента.
+|proof = [[Файл:ve2.png|right|600px|Оценка количества переподвешиваний]] Оценим время работы необходимое для обновления указателей на представителя в операциях union. Рассмотрим количество обновлений отдельно для каждого элемента.
 Оказывается, что для каждого элемента мы можем обновить указатель не более <tex>O(\log n)</tex> раз. Это связано с тем, что при каждом объединении, множество, в котором оказывается объект, увеличивается не менее чем вдвое. Действительно, так как мы обновляем указатель на представителя элементу, то этот элемент находился в меньшем из множеств (согласно нашей эвристике), но тогда размер второго множества не меньше. Тогда после первого обновления элемент содержится в множестве, в котором не менее двух элементов, после второго {{ --- }} четырех, и так далее. В силу того, что множество не может содержать более n элементов, количество обновлений не превосходит <tex>O(\log n)</tex>.