СНМ (реализация с помощью леса корневых деревьев) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 12 участников)
Строка 1: Строка 1:
 
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
 
Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции (<tex>\mathrm{get}</tex> и <tex>\mathrm{union}</tex>) выполняются в среднем за практически константное время.
 
==Реализация==
 
==Реализация==
Каждое множество хранится в виде дерева. Элементы множества хранятся в узлах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
+
Каждое множество хранится в виде дерева. Элементы множества хранятся в вершинах дерева. У каждого множества есть его представитель {{---}} один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".  
  
 
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').
 
При объединении двух множеств, корень одного дерева подвешивается к другому (операция ''<tex>\mathrm{union}</tex>''). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция ''<tex>\mathrm{get}</tex>'').
  
Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализацими]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
+
Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где <tex>\mathrm{get}</tex> будет работать за линейное время, и никакого выигрыша по сравнению с [[СНМ(наивные_реализации)|наивными реализациями]] не будет. Выигрыш в скорости можно получить, используя две эвристики: '''объединение по рангу''' (union by rank) и '''сжатие пути''' (path compression).
  
 
===Объединение по рангу===
 
===Объединение по рангу===
 
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.  
 
Эта эвристика аналогична [[СНМ(списки_с_весовой_эвристикой)|весовой эвристике у связных списков]]. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.  
  
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>1</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.
+
Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен <tex>0</tex>. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на <tex>1</tex>.
  
 
===Сжатие пути===
 
===Сжатие пути===
Строка 18: Строка 18:
 
Для реализации СНМ будем поддерживать следующие массивы: <tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.
 
Для реализации СНМ будем поддерживать следующие массивы: <tex>p[x]</tex> {{---}} массив "родителей", <tex>r[x]</tex> {{---}} массив рангов.
 
===='''get'''====
 
===='''get'''====
  '''get'''(x)
+
  '''function''' '''get'''(x: '''int'''): '''int'''
    '''if''' p[x] != x
+
  '''if''' p[x] != x
      p[x] = get(p[x])
+
    p[x] = get(p[x])
    '''return''' p[x]
+
  '''return''' p[x]
  
 
===='''union'''====
 
===='''union'''====
  '''union'''(x, y)
+
  '''function''' '''union'''(x: '''int''', y: '''int'''):
    x = get(x)
+
  x = get(x)
    y = get(y)
+
  y = get(y)
    '''if''' x == y
+
  '''if''' x == y
      '''return'''
+
    '''return'''
    '''if''' r[x] == r[y]
+
  '''if''' r[x] == r[y]
      r[x]++
+
    r[x]++
    '''if''' r[x] < r[y]
+
  '''if''' r[x] < r[y]
      p[x] = y
+
    p[x] = y
    '''else'''
+
  '''else'''
      p[y] = x
+
    p[y] = x
 +
 +
Также возможна реализация функции <tex>\mathrm{get}</tex> без использования <tex>\mathrm{O(\log n)}</tex> дополнительной памяти.
 +
 
 +
===='''get'''====
 +
'''function''' '''get'''(x: '''int'''): '''int'''
 +
  root = x
 +
  '''while''' p[root] != root
 +
    root = p[root]
 +
  i = x
 +
  '''while''' p[i] != i
 +
    j = p[i]
 +
    p[i] = root
 +
    i = j
 +
  '''return''' root
  
 
==Асимптотика==
 
==Асимптотика==
Строка 47: Строка 61:
 
| ''<tex>\mathrm{union}</tex>''                || <tex>\mathrm{O(\log n)}</tex>            ||  <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
 
| ''<tex>\mathrm{union}</tex>''                || <tex>\mathrm{O(\log n)}</tex>            ||  <tex>\mathrm{O(\mathrm{\alpha(m, n)})}</tex>
 
|}
 
|}
Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций get и <tex>n</tex> элементов).
+
Где <tex>m</tex> {{---}} общее количество операций, <tex>n</tex> {{---}} полное количество элементов, <tex>\mathrm{\alpha(m, n)}</tex> {{---}} функция, обратная к функции Аккермана (если <tex>m</tex> операций <tex>\mathrm{get}</tex> и <tex>n</tex> элементов).
  
 
Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.
 
Докажем, что если глубина множества (т.е. его ранг) равна <tex>k</tex>, то в нем содержится как минимум <tex>2^k</tex> элементов. Из этого свойства следует, что глубина множества с <tex>n</tex> элементами есть <tex>\mathrm{O(\log n)}</tex>, а значит и время работы операции <tex>\mathrm{get}</tex> является логарифмическим.
Строка 67: Строка 81:
 
{| class="wikitable" border = 1
 
{| class="wikitable" border = 1
 
|-
 
|-
!<tex>m \backslash n</tex> !! <tex>0</tex> !! <tex>1</tex> !! <tex>2</tex> !! <tex>3</tex> !! <tex>4</tex> !! <tex>5</tex>
+
!<tex>\mathbf{m \backslash n}</tex> !! <tex>\mathbf{0}</tex> !! <tex>\mathbf{1}</tex> !! <tex>\mathbf{2}</tex> !! <tex>\mathbf{3}</tex> !! <tex>\mathbf{4}</tex> !! <tex>\mathbf{5}</tex>
 
|-style = "text-align = center"
 
|-style = "text-align = center"
! <tex>1</tex>  
+
! <tex>\mathbf{1}</tex>  
 
| <tex>1</tex> ||  <tex>2</tex> || <tex>4</tex> || <tex>8</tex> || <tex>16</tex> || <tex>32</tex>
 
| <tex>1</tex> ||  <tex>2</tex> || <tex>4</tex> || <tex>8</tex> || <tex>16</tex> || <tex>32</tex>
 
|-
 
|-
! <tex>2</tex>  
+
! <tex>\mathbf{2}</tex>  
 
| <tex>2</tex> || <tex>4</tex> || <tex>16</tex> || <tex>65536</tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
 
| <tex>2</tex> || <tex>4</tex> || <tex>16</tex> || <tex>65536</tex> || <tex>2^{2^{16}}</tex> || <tex>2^{2^{2^{16}}}</tex>
 
|-
 
|-
! <tex>3</tex>  
+
! <tex>\mathbf{3}</tex>  
 
| <tex>2</tex> || <tex>16</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
 
| <tex>2</tex> || <tex>16</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
 
|-
 
|-
! <tex>4</tex>  
+
! <tex>\mathbf{4}</tex>  
 
| <tex>2</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
 
| <tex>2</tex> || <tex>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex> || <tex>\cdots</tex>
 
|}
 
|}
  
Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция get выполняется за константное время.
+
Функция, обратная функции Аккермана <tex>\mathrm{\alpha(m, n)}</tex>, равна минимальному <tex>i</tex> такому, что <tex>\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n</tex>. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция <tex>\mathrm{get}</tex> выполняется за константное время.
  
 
===Анализ реализации с ранговой эвристикой===
 
===Анализ реализации с ранговой эвристикой===
  
Проведем анализ реализации с ранговой эвристикой, будем доказывать более слабую оценку (итерированный логарифм <tex>\mathrm(\log^*n)</tex>).
+
Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость <tex> \mathrm{get} = \mathrm{O(\log^{*}n)</tex>.
Рассмотрим <tex> a </tex> операций <tex> \mathrm{union}  </tex> и  <tex> b </tex> операций  <tex> \mathrm{get} ( b > a ) </tex>.
+
{{Определение
Не теряя общности, будем считать, что <tex> union </tex> принимает в качестве аргументов представителей,
+
|definition='''Итерированный логарифм''' (англ. ''Iterated logarithm'') <tex>\mathrm{\log^*n}</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex>.
 +
}}
 +
'''Пример''': <tex>\mathrm{\log^*_2 16} = 3</tex>
 +
 
 +
Рассмотрим <tex> n </tex> операций <tex> \mathrm{union}  </tex> и  <tex> m </tex> операций  <tex> \mathrm{get} </tex>. Можем считать, что число операций <tex> \mathrm{union}  </tex> равно числу элементов множества, так как количество операций <tex>\mathrm{union}</tex> не превосходит количество элементов множества <tex>n</tex>. Заметим, что <tex>m\geqslant n</tex>, так как при каждом вызове операции <tex>\mathrm{union}</tex> дважды вызывается операция <tex>\mathrm{get}</tex>.
 +
Не теряя общности, будем считать, что <tex> \mathrm{union} </tex> принимает в качестве аргументов представителей,
 
то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на  <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.
 
то есть <tex> \mathrm{union(v_1,v_2)} </tex> заменяем на  <tex> \mathrm{union(get(v_1),get(v_2))} </tex>.
 
<tex>\mathrm(\log^*n)</tex> — минимальное число логарифмирований <tex>n</tex>, необходимое для получения значения, не превосходящего <tex>1</tex> (Например: <tex>\mathrm(\log^*_2 16) = 3</tex>)
 
  
 
Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.   
 
Оценим стоимость операции <tex> \mathrm{get(v)} </tex>.   
Строка 98: Строка 115:
 
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.
 
<tex> \mathrm{K(v)} </tex> — количество вершин в поддереве, корнем которого является <tex>\mathrm{v}</tex>.
  
{{Утверждение  
+
{{Утверждение
 
|statement=
 
|statement=
<tex> \mathrm{R(P(v))} > \mathrm{R(v)} </tex>
+
<tex> \mathrm{R(P(v))} \geqslant \mathrm{R(v)} </tex>
 
|proof=
 
|proof=
Из принципа работы функции <tex> \mathrm{get} </tex> следует:
+
Если <tex>\mathrm{v}</tex> — представитель множества, то <tex>\mathrm{P(v)}=\mathrm{v}</tex> и <tex> \mathrm{R(P(v))} = \mathrm{R(v)} </tex>.
 +
 
 +
Иначе, из принципа работы функции <tex> \mathrm{union} </tex> следует:
 
#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.
 
#<tex> \mathrm{R(L(v))}>\mathrm{R(v)} </tex>.
#Между  <tex> v </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> v \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.
+
#Между  <tex> \mathrm{v} </tex> и <tex> \mathrm{P(v)} </tex> существует путь вида: <tex> \mathrm{v} \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} </tex>.
 
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
 
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
 
}}
 
}}
  
{{Утверждение  
+
{{Утверждение
 
|statement=
 
|statement=
<tex> \mathrm{R(v)} = i \Rightarrow \geqslant {\mathrm{K(v)}}  {2^i} </tex>
+
<tex> \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}</tex>
 
|proof=
 
|proof=
 
Докажем по индукции:  
 
Докажем по индукции:  
Строка 121: Строка 140:
 
Из последнего утверждения следует:
 
Из последнего утверждения следует:
  
#<tex> \mathrm{R(v)} \leqslant \log_2a </tex>.
+
{{Утверждение
#Количество вершин ранга <tex> i \leqslant \dfrac{a}  {2^i} </tex>.
+
|statement=
 +
<tex> \mathrm{R(v)} \leqslant \log_2n </tex>
 +
}}
 +
{{Утверждение
 +
|statement=
 +
Количество вершин ранга <tex> i \leqslant \dfrac{n}  {2^i} </tex>.
 +
|proof=
 +
Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее <tex>n</tex>. Это противоречит условию, по которому <tex>n</tex> — число всех вершин. Значит утверждение верно.
 +
}}
  
 
{{Теорема
 
{{Теорема
Строка 129: Строка 156:
 
|proof=
 
|proof=
  
В процессе выполнения каждой из операций <tex>get</tex> двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Заметим, что на каждом шаге ранг вершины строго возрастает: если <tex>\mathrm{u}</tex> - вершина, встретившаяся на пути поиска, а <tex>\mathrm{v}</tex> - следующая вершина, то есть <tex>\mathrm{v} = \mathrm{P(u)} </tex>, то <tex> \mathrm{R(v)} \leqslant \mathrm{R(u)}</tex>. Вершина <tex>\mathrm{u}</tex> может неоднократно встречаться в путях поиска, при выполнении рассматриваемой в теореме последовательности операций. При этом за ней могут идти разные вершины: если в некоторый момент за <tex>\mathrm{u}</tex> будет следовать уже не <tex>\mathrm{v}</tex>, а корень дерева, то есть вершина большего ранга, чем <tex>\mathrm{v}</tex>.
+
Рассмотрим все вызовы функции <tex>\mathrm{get(u)}</tex>. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина <tex>u</tex> не корень и не сын корня, то во время рекурсивных вызовов функции <tex>\mathrm{get(u)}</tex> текущее значение <tex>\mathrm{R(L(u))}</tex> возрастает.
Наблюдая за ростом ранга при переходе от вершины к её родителю, отдельно оценим количество шагов, при которых ранг сильно растет, а количество шагов, когда он растет не сильно. Выберем в качестве границы некоторую функцию <tex>\mathrm{B(k)}</tex>, определенную для неотрицательных целых <tex>\mathrm{k}</tex>. Мы предполагаем, что функция <tex>\mathrm{B}</tex> является монотонно возрастающей и что <tex>\mathrm{B(k)} \leqslant \mathrm{k}</tex> при всех <tex>\mathrm{k}</tex>. При переходе от вершины <tex>\mathrm{u}</tex> к её родителю <tex>\mathrm{v} = \mathrm{P(u)} </tex> ранг сильно растет сильно растет, если <tex> \mathrm{R(v)} \geqslant \mathrm{B(R(u))} </tex>.  
+
Пусть <tex>m</tex> — количество вызовов операции <tex>\mathrm{get(u)}</tex>, <tex>n</tex> — количество вызовов операции <tex>\mathrm{union(v, u)}</tex>, и <tex>m\geqslant n</tex>.
Оценим число шагов, при которых ранг не сильно растет, и сгруппируем их по вершинам, из которых этот шаг делается. Для вершины ранга <tex>\mathrm{k}</tex> ранги ее предка могут меняться от <tex>\mathrm{k+1}</tex> до <tex>\mathrm{B(k)}</tex> (после этого ранг растет сильно). Значит, число таких шагов(из данной вершины ранга <tex>\mathrm{k}</tex>) заведомо не больше <tex>\mathrm{B(k)}</tex>, поскольку каждый новый шаг ведёт в вершину большего ранга, чем предыдущий. Поскольку вершин ранга <tex>\mathrm{k}</tex> не более <tex>n/2^{k}</tex>, то общее число шагов, при которых ранг не сильно растет, не превосходит
+
Разделим все вершины на <tex>4</tex> типа:
 +
 
 +
:1. <tex>u</tex> — корень. Таких вызовов <tex>\mathrm{get(u)}</tex> будет ровно <tex>m</tex>.
 +
:2. <tex>u</tex> — сын корня. Таких вызовов <tex>\mathrm{get(u)}</tex> будет не больше чем <tex>m</tex>.
 +
Оставшиеся вершины разделим на:
 +
:3. Быстро растущие вызовы — такие что <tex>\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}</tex>, где <tex>i</tex> — число из диапазона <tex dpi="150">e ^{\frac{1}{e}} < i < 2</tex> <tex dpi="150">(e ^{\frac{1}{e}}\approx </tex> <tex>1.44</tex><tex dpi="150">)</tex>.
 +
:4. Медленно растущие вызовы — <tex>\mathrm{R(P(u))} < i^{\mathrm{R(u)}}</tex>.
 +
 
 +
Для первых двух типов вершин одна операция <tex>\mathrm{get(u)}</tex> работает за истинное время <tex>\mathrm{O(1)}</tex>, поэтому их суммарное время работы не превышает <tex>2\cdot m</tex>.
 +
 
 +
При каждом вложенном вызове функции <tex>\mathrm{get(u)}</tex> для вершин третьего типа ранг по условию возрастает до <tex>i^{\mathrm{R(u)}}</tex>. Ранг вершины может меняться в пределах от <tex>0</tex> до <tex>\log_2n</tex>. Значит количество рекурсивных вызовов равняется количеству возведений в степень <tex>\mathrm{R(n)}</tex> числа <tex>i</tex>,
 +
необходимых для достижения числа <tex>\log_2n</tex>. Или что то же самое, количеству логарифмирований по основанию <tex>i</tex> числа <tex>\log_2n</tex> для получения <tex>1</tex> и еще одному логарифмированию для получения <tex>0</tex>. Количество логарифмирований описывается функцией <tex dpi="130">\log^*_{i} \left (\log_2 n  \right )</tex>. С учетом последнего логарифмирования формула примет вид <tex dpi="130">\log^*_{i}n</tex>.
 +
Тогда время работы <tex>m</tex> быстро растущих вызовов равно <tex>\mathrm{O(m\cdot \log^* n)}</tex>.
 +
 
 +
Поскольку количество вершин с рангом <tex>k</tex> не превышает число <tex>\dfrac{n}{2^k}</tex>, то суммарное время работы медленно растущих вызовов равно
 
<center>
 
<center>
<tex>{\sum_{\mathrm{k}} \limits {\dfrac {n \mathrm{B(k)}} {2^{\mathrm{k}}}}}
+
<tex dpi="150">\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}</tex>
</tex>
 
 
</center>
 
</center>
Если выбрать функцию <tex>\mathrm{B}</tex> так, чтобы ряд <tex>{\sum_{} \limits n \mathrm{B(k)} / 2^{\mathrm{k}}}</tex> сходился, то общее число шагов такого рода есть <tex>\mathrm{O(n)}</tex>.
+
В итоге получаем, что суммарное время работы операции <tex>\mathrm{get(u)}</tex> равняется <tex>T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}</tex>.
Прежде чем выбрать функцию <tex>\mathrm{B(k)}</tex>, выясним, как оценить число шагов, при которых ранг сильно растет. Такие шаги мы сгруппируем не по вершинам, а по путям: на каждом пути поиска таких шагов мало, так как ранг не может многократно  сильно расти (он меняется всего лишь от <tex>0</tex> и <tex>\log n</tex>). Таким образом, на каждом пути число шагов, при котором ранг сильно растёт, не превосходит числа итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы дойти от <tex>0</tex> и <tex>\log n</tex>.
+
С учетом того факта что <tex>m\geqslant n</tex>, амортизированное время работы равно <tex>\mathrm{O(\log^* n)}</tex>.
Если положить <tex>\mathrm{B(k)} = 2^{\mathrm{k}}</tex>: тогда число итераций будет примерно равно <tex>\mathrm{O(\log^{*}n)}</tex>. Но тогда написанный выше ряд расходится. Возьмем меньшую функцию. Например, положим <tex>\mathrm{B(k)} = 1,9^{\mathrm{k}}</tex>, тогда ряд <tex>\sum_{} \limits \mathrm{B(k)} = 1,9^{\mathrm{k}}/2^{\mathrm{k}} \leqslant \sum_{} \limits \mathrm{B(k)} = (1,9^{\mathrm{k}}+1)/2^{\mathrm{k}}</tex> сходится. С другой стороны, число итераций функции <tex>\mathrm{B}</tex>, которые нужно сделать, чтобы от <tex>0</tex> дойти до какого-то числа, возрастет (по сравнению с функцией <tex>\mathrm{k}</tex>, стремящейся к <tex>2^{\mathrm{k}}</tex>) не более чем вдвое, поскольку <tex>\mathrm{B(B(k))} \geqslant 2^{\mathrm{k}}</tex>, и потому есть <tex>\mathrm{O(\log^*n)}</tex>.
 
 
}}
 
}}
  
Строка 149: Строка 188:
 
* [http://ru.wikipedia.org/wiki/Функция_Аккермана  Функция Аккермана {{---}} Википедия]
 
* [http://ru.wikipedia.org/wiki/Функция_Аккермана  Функция Аккермана {{---}} Википедия]
 
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ —  Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4
 
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ —  Вильямс, 2010. - стр 589. — ISBN 978-5-8459-0857-4
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:12, 4 сентября 2022

Данная реализация СНМ позволяет добиться наилучшей асимптотики при работе с этой структурой данных. А именно, обе операции ([math]\mathrm{get}[/math] и [math]\mathrm{union}[/math]) выполняются в среднем за практически константное время.

Реализация

Каждое множество хранится в виде дерева. Элементы множества хранятся в вершинах дерева. У каждого множества есть его представитель — один из элементов этого множества, он хранится в корне дерева. В каждом узле, кроме корня, хранится ссылка на "родителя".

При объединении двух множеств, корень одного дерева подвешивается к другому (операция [math]\mathrm{union}[/math]). Таким образом, чтобы определить, в каком множестве находится элемент достаточно пройтись по ссылкам по дереву вверх до корня (операция [math]\mathrm{get}[/math]).

Без использования дополнительных "улучшений", такое дерево может выродиться в линейный список, где [math]\mathrm{get}[/math] будет работать за линейное время, и никакого выигрыша по сравнению с наивными реализациями не будет. Выигрыш в скорости можно получить, используя две эвристики: объединение по рангу (union by rank) и сжатие пути (path compression).

Объединение по рангу

Эта эвристика аналогична весовой эвристике у связных списков. Идея в том, чтобы при объединении подвешивать дерево с меньшей глубиной к дереву с большей.

Вместо того, чтобы явно хранить высоту дерева, можно хранить его ранг, который по сути является некой верхней оценкой высоты дерева. У дерева, состоящего ровно из одного элемента ранг равен [math]0[/math]. При объединении дерево с меньшим рангом подвешивается к дереву с большим, и ранг объединенного дерева становится равным большему из этих двух рангов. Если ранги объединяемых деревьев равны, то не важно какое к какому дереву подвешивать, но ранг объединенного дерева следует делать большим на [math]1[/math].

Сжатие пути

Эта эвристика несколько модифицирует операцию [math]\mathrm{get}[/math]. Операция [math]\mathrm{get}[/math] вызывается для элемента [math]x[/math], проходит через несколько вершин и попадает в корень. Все пройденные в этом процессе вершины принадлежат тому же множеству, что и [math]x[/math]. Поэтому мы можем подвесить (изменить ссылки) эти вершины напрямую к корню дерева и, таким образом, уменьшить его высоту. При нерекурсивной реализации операция [math]\mathrm{get}[/math] становится двухпроходной.

Псевдокод

Для реализации СНМ будем поддерживать следующие массивы: [math]p[x][/math] — массив "родителей", [math]r[x][/math] — массив рангов.

get

function get(x: int): int
  if p[x] != x
    p[x] = get(p[x])
  return p[x]

union

function union(x: int, y: int):
  x = get(x)
  y = get(y)
  if x == y
    return
  if r[x] == r[y]
    r[x]++
  if r[x] < r[y]
    p[x] = y
  else
    p[y] = x

Также возможна реализация функции [math]\mathrm{get}[/math] без использования [math]\mathrm{O(\log n)}[/math] дополнительной памяти.

get

function get(x: int): int
 root = x
 while p[root] != root
   root = p[root]
 i = x
 while p[i] != i
   j = p[i]
   p[i] = root
   i = j
 return root

Асимптотика

см. также Анализ реализации с ранговой эвристикой
Операция Истинное время Амортизированное время
[math]\mathrm{get}[/math] [math]\mathrm{O(\log n)}[/math] [math]\mathrm{O(\mathrm{\alpha(m, n)})}[/math]
[math]\mathrm{union}[/math] [math]\mathrm{O(\log n)}[/math] [math]\mathrm{O(\mathrm{\alpha(m, n)})}[/math]

Где [math]m[/math] — общее количество операций, [math]n[/math] — полное количество элементов, [math]\mathrm{\alpha(m, n)}[/math] — функция, обратная к функции Аккермана (если [math]m[/math] операций [math]\mathrm{get}[/math] и [math]n[/math] элементов).

Докажем, что если глубина множества (т.е. его ранг) равна [math]k[/math], то в нем содержится как минимум [math]2^k[/math] элементов. Из этого свойства следует, что глубина множества с [math]n[/math] элементами есть [math]\mathrm{O(\log n)}[/math], а значит и время работы операции [math]\mathrm{get}[/math] является логарифмическим.

Будем доказывать данное свойство по индукции. Для [math]k = 0[/math], очевидно, в множестве содержится [math]1[/math] вершина. Пусть для множеств ранга [math]k - 1[/math] свойство выполняется. Как следует из ранговой эвристики, множество ранга [math]k[/math] может получиться только при подвешивании множества ранга [math]k - 1[/math] к множеству ранга [math]k - 1[/math]. Но тогда из предположения индукции в новом множестве действительно будет [math]2^k[/math] вершин, что и требовалось доказать.

Функция Аккермана

Функция Аккермана определяется следующим рекуррентным соотношением для целых неотрицательных чисел [math]m[/math] и [math]n[/math]:

[math]\mathrm{A(m, n)} = \begin{cases} 2^n, & m = 1 \\ 2, & m \gt 1, n = 0 \\ \mathrm{A(m - 1, A(m, n - 1))}, & m \gt 1, n \gt 0 \end{cases} [/math]

Таблица значений функции Аккермана:

[math]\mathbf{m \backslash n}[/math] [math]\mathbf{0}[/math] [math]\mathbf{1}[/math] [math]\mathbf{2}[/math] [math]\mathbf{3}[/math] [math]\mathbf{4}[/math] [math]\mathbf{5}[/math]
[math]\mathbf{1}[/math] [math]1[/math] [math]2[/math] [math]4[/math] [math]8[/math] [math]16[/math] [math]32[/math]
[math]\mathbf{2}[/math] [math]2[/math] [math]4[/math] [math]16[/math] [math]65536[/math] [math]2^{2^{16}}[/math] [math]2^{2^{2^{16}}}[/math]
[math]\mathbf{3}[/math] [math]2[/math] [math]16[/math] [math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math] [math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{A(3, 2)}[/math] [math]\cdots[/math] [math]\cdots[/math]
[math]\mathbf{4}[/math] [math]2[/math] [math]\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{17}[/math] [math]\cdots[/math] [math]\cdots[/math] [math]\cdots[/math] [math]\cdots[/math]

Функция, обратная функции Аккермана [math]\mathrm{\alpha(m, n)}[/math], равна минимальному [math]i[/math] такому, что [math]\mathrm{A \left (i, \left [\dfrac{m}{n} \right ] \right )} \geqslant \log n[/math]. Как видно из таблицы значений для функции Аккермана, обратная функция для любых значений, которые могут возникнуть при решении прикладных задач, не превышает 4, то есть можно считать, что операция [math]\mathrm{get}[/math] выполняется за константное время.

Анализ реализации с ранговой эвристикой

Проведем анализ реализации с ранговой эвристикой. Будем доказывать, что амортизационная стоимость [math] \mathrm{get} = \mathrm{O(\log^{*}n)} [/math].

Определение:
Итерированный логарифм (англ. Iterated logarithm) [math]\mathrm{\log^*n}[/math] — минимальное число логарифмирований [math]n[/math], необходимое для получения значения, не превосходящего [math]1[/math].

Пример: [math]\mathrm{\log^*_2 16} = 3[/math]

Рассмотрим [math] n [/math] операций [math] \mathrm{union} [/math] и [math] m [/math] операций [math] \mathrm{get} [/math]. Можем считать, что число операций [math] \mathrm{union} [/math] равно числу элементов множества, так как количество операций [math]\mathrm{union}[/math] не превосходит количество элементов множества [math]n[/math]. Заметим, что [math]m\geqslant n[/math], так как при каждом вызове операции [math]\mathrm{union}[/math] дважды вызывается операция [math]\mathrm{get}[/math]. Не теряя общности, будем считать, что [math] \mathrm{union} [/math] принимает в качестве аргументов представителей, то есть [math] \mathrm{union(v_1,v_2)} [/math] заменяем на [math] \mathrm{union(get(v_1),get(v_2))} [/math].

Оценим стоимость операции [math] \mathrm{get(v)} [/math]. Обозначим [math] \mathrm{R(v)} [/math] — ранг вершины, [math]\mathrm{P(v)}[/math] — представитель множества, содержащего [math]\mathrm{v}[/math], [math] \mathrm{L(v)} [/math] — отец вершины, [math] \mathrm{K(v)} [/math] — количество вершин в поддереве, корнем которого является [math]\mathrm{v}[/math].

Утверждение:
[math] \mathrm{R(P(v))} \geqslant \mathrm{R(v)} [/math]
[math]\triangleright[/math]

Если [math]\mathrm{v}[/math] — представитель множества, то [math]\mathrm{P(v)}=\mathrm{v}[/math] и [math] \mathrm{R(P(v))} = \mathrm{R(v)} [/math].

Иначе, из принципа работы функции [math] \mathrm{union} [/math] следует:

  1. [math] \mathrm{R(L(v))}\gt \mathrm{R(v)} [/math].
  2. Между [math] \mathrm{v} [/math] и [math] \mathrm{P(v)} [/math] существует путь вида: [math] \mathrm{v} \rightarrow \mathrm{L(v)} \rightarrow \mathrm{L(L(v))} \rightarrow \dots \rightarrow \mathrm{P(v)} [/math].
Записав неравенство из первого пункта вдоль пути из второго пункта, получаем требуемое.
[math]\triangleleft[/math]
Утверждение:
[math] \mathrm{R(v)} = i \Rightarrow {\mathrm{K(v)}} \geqslant {2^i}[/math]
[math]\triangleright[/math]

Докажем по индукции:

Для [math]0[/math] равенство очевидно. Ранг вершины станет равным [math] i [/math] при объединении поддеревьев ранга [math]i-1[/math], следовательно:

[math]\mathrm{K(v)} \geqslant \mathrm{K(v_1)} + \mathrm{K(v_2)} \geqslant 2^{i-1}+2^{i-1} \geqslant 2^i [/math].
[math]\triangleleft[/math]

Из последнего утверждения следует:

Утверждение:
[math] \mathrm{R(v)} \leqslant \log_2n [/math]
Утверждение:
Количество вершин ранга [math] i \leqslant \dfrac{n} {2^i} [/math].
[math]\triangleright[/math]
Если бы это было не так, то просуммировав количество вершин всех рангов, мы получили бы число большее [math]n[/math]. Это противоречит условию, по которому [math]n[/math] — число всех вершин. Значит утверждение верно.
[math]\triangleleft[/math]
Теорема:
Амортизационная стоимость [math] \mathrm{get} = \mathrm{O(\log^{*}n)} [/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим все вызовы функции [math]\mathrm{get(u)}[/math]. В процессе выполнения каждой операции двигаемся вверх по одному из деревьев, заканчивая поиск в его корне. Если вершина [math]u[/math] не корень и не сын корня, то во время рекурсивных вызовов функции [math]\mathrm{get(u)}[/math] текущее значение [math]\mathrm{R(L(u))}[/math] возрастает. Пусть [math]m[/math] — количество вызовов операции [math]\mathrm{get(u)}[/math], [math]n[/math] — количество вызовов операции [math]\mathrm{union(v, u)}[/math], и [math]m\geqslant n[/math]. Разделим все вершины на [math]4[/math] типа:

1. [math]u[/math] — корень. Таких вызовов [math]\mathrm{get(u)}[/math] будет ровно [math]m[/math].
2. [math]u[/math] — сын корня. Таких вызовов [math]\mathrm{get(u)}[/math] будет не больше чем [math]m[/math].

Оставшиеся вершины разделим на:

3. Быстро растущие вызовы — такие что [math]\mathrm{R(P(u))} \geqslant i^{\mathrm{R(u)}}[/math], где [math]i[/math] — число из диапазона [math]e ^{\frac{1}{e}} \lt i \lt 2[/math] [math](e ^{\frac{1}{e}}\approx [/math] [math]1.44[/math][math])[/math].
4. Медленно растущие вызовы — [math]\mathrm{R(P(u))} \lt i^{\mathrm{R(u)}}[/math].

Для первых двух типов вершин одна операция [math]\mathrm{get(u)}[/math] работает за истинное время [math]\mathrm{O(1)}[/math], поэтому их суммарное время работы не превышает [math]2\cdot m[/math].

При каждом вложенном вызове функции [math]\mathrm{get(u)}[/math] для вершин третьего типа ранг по условию возрастает до [math]i^{\mathrm{R(u)}}[/math]. Ранг вершины может меняться в пределах от [math]0[/math] до [math]\log_2n[/math]. Значит количество рекурсивных вызовов равняется количеству возведений в степень [math]\mathrm{R(n)}[/math] числа [math]i[/math], необходимых для достижения числа [math]\log_2n[/math]. Или что то же самое, количеству логарифмирований по основанию [math]i[/math] числа [math]\log_2n[/math] для получения [math]1[/math] и еще одному логарифмированию для получения [math]0[/math]. Количество логарифмирований описывается функцией [math]\log^*_{i} \left (\log_2 n \right )[/math]. С учетом последнего логарифмирования формула примет вид [math]\log^*_{i}n[/math]. Тогда время работы [math]m[/math] быстро растущих вызовов равно [math]\mathrm{O(m\cdot \log^* n)}[/math].

Поскольку количество вершин с рангом [math]k[/math] не превышает число [math]\dfrac{n}{2^k}[/math], то суммарное время работы медленно растущих вызовов равно

[math]\sum_u \limits i^{\mathrm{R(u)}}=\sum_{k=0}^{\log n} \limits \sum_{\mathrm{{R(u)}=k}} \limits i^k \leqslant \sum_{k=0}^{\log n} \limits i^k \cdot \frac{n}{2^k} \leqslant n \cdot \sum_{k=0}^{\log n} \limits \dfrac{i^k}{2^k} = \mathrm{O(n)}[/math]

В итоге получаем, что суммарное время работы операции [math]\mathrm{get(u)}[/math] равняется [math]T = \mathrm{O(m)} + \mathrm{O(m\cdot \log^* n)} +\mathrm{O(n)} = \mathrm{O(m\cdot \log^*n + n)}[/math].

С учетом того факта что [math]m\geqslant n[/math], амортизированное время работы равно [math]\mathrm{O(\log^* n)}[/math].
[math]\triangleleft[/math]

См. также

Источники информации