СНМ: различия между версиями
(Новая страница: «===Задача:=== Хотим реализовать структуру данных, которах поддерживает следующие операции...») |
|||
Строка 72: | Строка 72: | ||
====Шаг==== | ====Шаг==== | ||
Дерево ранга $r$ мы получаем только при объединении двух деревьев ранга $r - 1$. В каждом из них, по предположению индукции, хотя бы $2^{r-1}$ вершин. Значит, в их объединении будет хотя бы $2^{r}$ вершин. | Дерево ранга $r$ мы получаем только при объединении двух деревьев ранга $r - 1$. В каждом из них, по предположению индукции, хотя бы $2^{r-1}$ вершин. Значит, в их объединении будет хотя бы $2^{r}$ вершин. | ||
+ | |||
+ | Итак, мы с вами научились строить структуру данных, в которых сложность каждого запроса составляет $O(log(n))$. Оказывается, можно и быстрее. | ||
+ | |||
+ | Идея: если в какой-то момент мы узнали, что $root(v) = r$, то можно после этого переподвесить $v$ к $r$, не нарушив свойств нашей структуры. Более того, у всех вершин $u$ на пути от $v$ до $r$, $root(u) = r$, и их тоже можно подвесить к $r$, таким образом сократив время ответа на дальнейшие запросы $GetRoot(u)$. Эта эвристика носит название '''эвристики о сжатии путей'''. | ||
+ | |||
+ | Эта на первый взгляд непростая эвристика оказывается на удивлении лаконичной в смысле кода. | ||
+ | |||
+ | Итоговый код, с обеими эвристиками: | ||
+ | |||
+ | <syntaxhighlight lang="C++"> | ||
+ | |||
+ | vector<int> p; | ||
+ | vector<int> rank; | ||
+ | |||
+ | void init(n) { | ||
+ | p.resize(n); | ||
+ | p.iota(p.begin(), p.end(), 0); | ||
+ | /* equivalent to | ||
+ | * | ||
+ | * for (int i = 0; i < n; ++i) { | ||
+ | * p[i] = i; | ||
+ | * } | ||
+ | * | ||
+ | */ | ||
+ | |||
+ | rank.resize(n, 0); | ||
+ | } | ||
+ | |||
+ | int GetRoot(int i) { | ||
+ | if (p[i] == i) { | ||
+ | return i; | ||
+ | } | ||
+ | |||
+ | return p[i] = GetRoot(p[i]); | ||
+ | } | ||
+ | |||
+ | void Merge(int i, int j) { | ||
+ | int root_i = GetRoot(i); | ||
+ | int root_j = GetRoot(j); | ||
+ | |||
+ | // если вершины лежат в одном дереве | ||
+ | // то можно ничего не делать | ||
+ | if (root_i == root_j) { | ||
+ | return; | ||
+ | } | ||
+ | |||
+ | if (rank[root_i] < rank[root_j]) { | ||
+ | p[root_i] = root_j; | ||
+ | } else if (rank[root_j] < rank[root_i]) { | ||
+ | p[root_j] = root_i; | ||
+ | } else { | ||
+ | p[root_i] = root_j; | ||
+ | rank[root_j]++; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | </syntaxhighlight> | ||
+ | |||
+ | ====Сложность &GetRoot& (б/д)==== | ||
+ | Пусть нам поступаем $g$ запросов типа $GetRoot$. Тогда СНМ с обеими эвристиками выполнит их за суммарное время $O(g \times log^*(g))$ [https://ru.wikipedia.org/wiki/%D0%98%D1%82%D0%B5%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BB%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC Что такое $log^*(x)$] | ||
+ | |||
{{Автор|Александр Гришутин|rationalex}} | {{Автор|Александр Гришутин|rationalex}} |
Версия 12:51, 22 ноября 2019
Содержание
Задача:
Хотим реализовать структуру данных, которах поддерживает следующие операции:
- $init(n)$: создать $n$ независимых вершин, в каждой из которой записан свой номер, от $0$ до &n-1&
- $Merge(i, j)$: объединить в одну компоненту связности компоненты связности, в которых сейчас лежат вершины $i$ и $j$
- $GetComponentId(i)$: выдать идентификатор компоненты, в которой лежит вершина $i$. Разумеется, мы хотим, чтобы для всех вершин в одной компоненте ответ был одинаковый.
Реализуем эту структуру с помощью леса из корневых деревьев $~-$ каждая вершина будет знать своего предка в своём дереве, у вершины-корня положим предком её саму. Изначально (после $init$-а) все вершины будут являться деревом размера $1$.
Тогда, чтобы отвечать на $3$-ий запрос, нам достаточно возвращать корень дерева, в котором находится вершина $~-$ для этого надо подниматься в предка до тех пор, пока не дойдём до корня $~-$ у него предком будет он сам.
Чтобы реализовать $Merge(i, j)$, нам надо научиться объединять деревья. Вспомним, что в $GetComponentId$ нам нужно подниматься от вершины до корня. Значит, нам хотелось бы, чтобы эта величина была как можно меньше в среднем. Значит, надо следить за тем, чтобы деревья получались сбалансированными. Для этого будем хранить в каждой вершине $rank(i) ~-$ длину самого длинного пути от вершины вниз до листа. При $Merge(i, j)$ корневых деревьев у нас есть 2 варианта: подвесить $root(i)$ к $root(j)$ или наоборот. Выберем тот из вариантов, в котором получившееся дерево будет более сбалансированным. Для этого будем подвешивать вершину с меньшим рангом к вершине с большим, а при равенстве будем подвешивать первую вершину ко второй, увеличивая ранг второй на 1.
Talk is cheap. Show me the code
vector<int> p;
vector<int> rank;
void init(n) {
p.resize(n);
p.iota(p.begin(), p.end(), 0);
/* equivalent to
*
* for (int i = 0; i < n; ++i) {
* p[i] = i;
* }
*
*/
rank.resize(n, 0);
}
int GetRoot(int i) {
while (p[i] != i) {
i = p[i];
}
return i;
}
void Merge(int i, int j) {
int root_i = GetRoot(i);
int root_j = GetRoot(j);
// если вершины лежат в одном дереве
// то можно ничего не делать
if (root_i == root_j) {
return;
}
if (rank[root_i] < rank[root_j]) {
p[root_i] = root_j;
} else if (rank[root_j] < rank[root_i]) {
p[root_j] = root_i;
} else {
p[root_i] = root_j;
rank[root_j]++;
}
}
Лемма о ранговой эвристике
Если $rank(v) = r$, то в поддереве вершины $v$ хотя бы $2^v$ вершин.
Доказательство
Будем доказывать индукцией по $r$.
База
$r = 0$
Шаг
Дерево ранга $r$ мы получаем только при объединении двух деревьев ранга $r - 1$. В каждом из них, по предположению индукции, хотя бы $2^{r-1}$ вершин. Значит, в их объединении будет хотя бы $2^{r}$ вершин.
Итак, мы с вами научились строить структуру данных, в которых сложность каждого запроса составляет $O(log(n))$. Оказывается, можно и быстрее.
Идея: если в какой-то момент мы узнали, что $root(v) = r$, то можно после этого переподвесить $v$ к $r$, не нарушив свойств нашей структуры. Более того, у всех вершин $u$ на пути от $v$ до $r$, $root(u) = r$, и их тоже можно подвесить к $r$, таким образом сократив время ответа на дальнейшие запросы $GetRoot(u)$. Эта эвристика носит название эвристики о сжатии путей.
Эта на первый взгляд непростая эвристика оказывается на удивлении лаконичной в смысле кода.
Итоговый код, с обеими эвристиками:
vector<int> p;
vector<int> rank;
void init(n) {
p.resize(n);
p.iota(p.begin(), p.end(), 0);
/* equivalent to
*
* for (int i = 0; i < n; ++i) {
* p[i] = i;
* }
*
*/
rank.resize(n, 0);
}
int GetRoot(int i) {
if (p[i] == i) {
return i;
}
return p[i] = GetRoot(p[i]);
}
void Merge(int i, int j) {
int root_i = GetRoot(i);
int root_j = GetRoot(j);
// если вершины лежат в одном дереве
// то можно ничего не делать
if (root_i == root_j) {
return;
}
if (rank[root_i] < rank[root_j]) {
p[root_i] = root_j;
} else if (rank[root_j] < rank[root_i]) {
p[root_j] = root_i;
} else {
p[root_i] = root_j;
rank[root_j]++;
}
}
Сложность &GetRoot& (б/д)
Пусть нам поступаем $g$ запросов типа $GetRoot$. Тогда СНМ с обеими эвристиками выполнит их за суммарное время $O(g \times log^*(g))$ Что такое $log^*(x)$
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex