DSU Complexity

This section is adapted from Time Complexity - A Brief Introduction to Potential Analysis, with permission from the original author.

Definition

Ackermann Function

First, we define \(\alpha(n)\). To define it, we first define \(A_k(j)\).

Define \(A_k(j)\) as:

\[ A_k(j)=\left\{ \begin{aligned} &j+1& &k=0&\\ &A_{k-1}^{(j+1)}(j)& &k\geq1& \end{aligned} \right. \]

This is the Ackermann function.

Here, \(f^i(x)\) denotes applying \(f\) to \(x\) consecutively \(i\) times, i.e., \(f^0(x)=x\), \(f^i(x)=f(f^{i-1}(x))\).

Then define \(\alpha(n)\) as the smallest integer such that \(A_{\alpha(n)}(1)\geq n\). Note that it was previously described as \(A_{\alpha(n)}(\alpha(n))\geq n\), but since both grow very slowly, their values do not exceed 4.

Basic Definitions

Each node has a rank. Here, rank is not the number of nodes but the depth. The initial rank of a node is 0. During merging, if the ranks of two nodes differ, the node with the smaller rank is merged into the node with the larger rank, and the rank of the larger node is not updated. Otherwise, one node is randomly merged into the other, and the rank of the root node is increased by 1. The rank of the root node gives the height of the tree. Denote the rank of \(x\) as \(rnk(x)\), and similarly, denote the parent of \(x\) as \(fa(x)\). We always have \(rnk(x)+1\leq rnk(fa(x))\).

To define the potential function, we first need an auxiliary function \(level(x)\). Here, \(level(x)=\max(k:rnk(fa(x))\geq A_k(rnk(x)))\). When \(rnk(x)\geq1\), define another auxiliary function \(iter(x)=\max(i:rnk(fa(x))\geq A_{level(x)}^i(rnk(x))\). These functions are defined for \(x\) satisfying \(rnk(x)>0\) and \(x\) is not a root of any tree.

The above definitions might be confusing. To clarify, for any \(x\) and \(fa(x)\), if \(rnk(x)>0\), we can always find a pair \((i,k)\) such that \(rnk(fa(x))\geq A_k^i(rnk(x))\), where \(level(x)=\max(k)\), and under this condition, \(iter(x)=\max(i)\). \(level\) describes the maximum iteration level of \(A\), while \(iter\) describes the maximum iteration count at that level.

For these two functions, \(level(x)\) always increases or remains unchanged during operations. If \(level(x)\) does not increase, \(iter(x)\) will only increase or remain unchanged. Moreover, they always satisfy the following two inequalities:

\[ 0\leq level(x)<\alpha(n) \]

\[ 1\leq iter(x)\leq rnk(x) \]

Considering the definitions of \(level(x)\), \(iter(x)\), and \(A_k^j\), these are easy to prove and are left to the reader to familiarize with the definitions.

Define the potential function \(\Phi(S)=\sum\limits_{x\in S}\Phi(x)\), where \(S\) represents an entire disjoint-set union (DSU), and \(x\) is a node in the DSU. Define \(\Phi(x)\) as:

\[ \Phi(x)= \begin{cases} \alpha(n)\times \mathit{rnk}(x)& \mathit{rnk}(x)=0\ \text{or}\ x\ \text{is the root of a tree}\\ (\alpha(n)-\mathit{level}(x))\times \mathit{rnk}(x)-iter(x)& \text{otherwise} \end{cases} \]

Then, we prove the amortized time complexity is \(\Theta(\alpha(n))\) by analyzing the potential changes caused by operations. Note that here we discuss the \(union(x,y)\) operation, ensuring that \(x\) and \(y\) are roots of some trees, so no additional \(find(x)\) or \(find(y)\) is needed.

It can be observed that the potential is always non-negative. Additionally, initially, the potential of the DSU is \(0\).

Proof

union(x,y) Operation

Its time cost is \(\Theta(1)\), so we consider the change in potential.

Here, we assume \(rnk(x)\leq rnk(y)\), meaning \(x\) is attached to \(y\). Thus, only the potential of \(x\) (from root to non-root), \(y\) (rank may increase), and the children of \(y\) before the operation (parent's rank may increase) can increase. We first prove that the potential of a child \(c\) of \(y\) before the operation cannot increase, and if it decreases, it decreases by at least \(1\).

Let the potential of \(c\) before the operation be \(\Phi(c)\), and after the operation be \(\Phi(c')\). Here, \(c\) can be any non-root node with \(rnk(c)>0\), and the operation can be any operation, including the find operation below. We discuss three cases.

1. \(iter(c)\) and \(level(c)\) do not increase. Clearly, \(\Phi(c)=\Phi(c')\).
2. \(iter(c)\) increases, but \(level(c)\) does not. Here, \(iter(c)\) increases by at least 1, so \(\Phi(c')\leq \Phi(c)-1\), meaning the potential decreases by at least 1.
3. \(level(c)\) increases, and \(iter(c)\) may decrease. However, since \(0<iter(c)\leq rnk(c)\), \(iter(c)\) can decrease by at most \(rnk(c)-1\), while \(level(c)\) increases by at least 1. By definition \(\Phi(c)=(\alpha(n)-level(c))\times rnk(c)-iter(c)\), we have \(\Phi(c')\leq\Phi(c)-1\).
4. Other cases. Since \(rnk(c)\) remains unchanged and \(rnk(fa(c))\) does not decrease, such cases do not exist.

Therefore, only \(x\) or \(y\) may have increased potential. \(x\) changes from a root to a non-root. If \(rnk(x)=0\), then \(\Phi(x)=\Phi(x')=0\). Otherwise, we have \(\alpha(x)\times rnk(x)\geq(\alpha(n)-level(x))\times rnk(x)-iter(x)\). That is, \(\Phi(x')\leq \Phi(x)\).

Thus, the only node whose potential may increase is \(y\). And the potential of \(y\) increases by at most \(\alpha(n)\). Therefore, the amortized time complexity of the \(union\) operation is \(\Theta(\alpha(n))\).

find(a) Operation

If the search path contains \(\Theta(s)\) nodes, its time complexity is clearly \(\Theta(s)\). If no node's potential increases due to the find operation, and at least \(s-\alpha(n)\) nodes' potential decreases by at least 1, we can prove the time complexity of \(find(a)\) is \(\Theta(\alpha(n))\). To avoid confusion, we use \(a\) as the parameter, and \(x\) refers to any node in the DSU.

First, prove no node's potential increases. Clearly, as proven above, the potential of non-root nodes does not increase, and the \(rnk\) of root nodes does not change, so no node's potential increases.

Next, prove at least \(s-\alpha(n)\) nodes' potential decreases by at least 1. We have shown that if \(level(x)\) or \(iter(x)\) changes, their potential decreases by at least 1. So, we only need to prove that at least \(s-\alpha(n)\) nodes have changes in \(level(x)\) or \(iter(x)\).

Recall the definition of potential for non-root nodes: \(\Phi(x)=(\alpha(n)-level(x))\times rnk(x)-iter(x)\), where \(level(x)\) and \(iter(x)\) are the maximum values such that \(rnk(fa(x))\geq A_{level(x)}^{iter(x)}(rnk(x))\).

Thus, if \(root_x\) represents the root of the tree containing \(x\), we only need to prove \(rnk(root_x)\geq A_{level(x)}^{iter(x)+1}(rnk(x))\). By the definition of \(A_k^i\), \(A_{level(x)}^{iter(x)+1}(rnk(x))=A_{level(x)}(A_{level(x)}^{iter(x)}(rnk(x)))\).

Note: we may use \(k(x)\) for \(level(x)\) and \(i(x)\) for \(iter(x)\) to avoid overly lengthy expressions. Here, it becomes \(rnk(root_x)\geq A_{k(x)}(A_{k(x)}^{i(x)}(x))\).

When you see this, you might feel "what is this?". This might mean you need to read it a few more times or skip ahead and come back later.

Here, we need an external \(A_{k(x)}\), meaning we might need to find another point \(y\). Let \(y\) be a point on the search path after \(x\) such that \(k(y)=k(x)\), where "after \(x\) on the search path" means "an ancestor of \(x\)". Clearly, not every \(x\) has such a \(y\). It is easy to prove that the number of \(x\) without such a \(y\) does not exceed \(\alpha(n)+2\). Because only the last \(x\) for each \(k\), \(a\), and \(root_a\) lack such a \(y\).

We emphasize again that \(fa(x)\) refers to the parent of \(x\) before path compression, and after path compression, the parent of \(x\) is uniformly denoted as \(root_x\). For each \(x\) with a corresponding \(y\), we always have \(rnk(y)\geq rnk(fa(x))\). Also, we have \(rnk(fa(x))\geq A_{k(x)}^{i(x)}(rnk(x))\). Since \(k(x)=k(y)\), we use \(k\) to denote both, i.e., \(rnk(fa(x))\geq A_k^{i(x)}(rnk(x))\). We need to construct an \(A_k\), so we can ignore the value of \(iter(y)\) and directly use the weaker inequality \(rnk(fa(y))\geq A_k(rnk(y))\).

If we combine the inequalities, something magical happens. We find that \(rnk(fa(y))\geq A_k^{i(x)+1}(rnk(x))\). That is, to iterate from \(rnk(x)\) to \(rnk(fa(y))\), we can iterate \(A_k\) at least \(i(x)+1\) times without exceeding \(rnk(fa(y))\).

Clearly, \(rnk(root_y)\geq rnk(fa(y))\), and \(rnk(x)\) remains unchanged during path compression. Therefore, we obtain \(rnk(root_x)\geq A_k^{i(x)+1}(rnk(x))\), meaning \(iter(x)\) increases by at least 1. If \(rnk(x)\) does not increase, then \(level(x)\) must have increased.

Thus, \(\Phi(x)\) decreases by at least 1. Since there are at least \(s-\alpha(n)-2\) such nodes \(x\), \(\Phi(S)\) decreases by at least \(s-\alpha(n)-2\), making the amortized time complexity \(\Theta(\alpha(n)+2)=\Theta(\alpha(n))\).

Why DSU Can Be Exploited

This question asks: if we do not merge by rank, which properties are broken, causing the time complexity of DSU to not be guaranteed as \(\Theta(m\alpha(n))\)?

If during merging, a node with larger \(rnk\) is merged into a node with smaller \(rnk\), we set the \(rnk\) of the smaller node to the larger node's \(rnk\) plus one. This ensures \(rnk(fa(x))\geq rnk(x)+1\), preventing properties like "compile error everywhere" from being violated.

Clearly, in this case, we break the property that "the potential of y increases by at most \(\alpha(n)\)" in the \(union(x,y)\) function.

There exists a structure that reduces the time complexity of path-compressed DSU to \(\Omega(m\log_{1+\frac{m}{n}}n)\), defined as follows:

A binomial tree (actually different from the usual binomial tree), where \(j\) is a constant, and \(T_k\) is a \(T_{k-1}\) with a \(T_{k-j}\) attached as a child of the root.

Boundary conditions: \(T_1\) to \(T_j\) are single nodes.

Let \(rnk(T_k)=r_k\), where \(r_k=(k-1)/j\) (proof omitted). In each operation, we attach it to a single node and query the bottom \(j\) nodes. That is, when attaching to a single node, the potential of the single node increases by \((k-1)/j+1\). When \(j=\lfloor\frac{m}{n}\rfloor\), \(i=\lfloor\log_{j+1}\frac{n}{2}\rfloor\), \(k=ij\), the potential increase is:

\[ \alpha(n)\times((ij-1)/j+1)=\alpha(n)\times((\lfloor\log_{\lfloor\frac{m}{n}\rfloor+1}\frac{n}{2}\rfloor\times \lfloor\frac{m}{n}\rfloor-1)/\lfloor\frac{m}{n}\rfloor+1) \]

Simplifying and removing all floor functions, we find the potential increase \(\geq \alpha(n)\times(\log_{1+\frac{m}{n}}n-\frac{n}{m})\). Over \(m\) operations, this is \(\Omega(m\log_{1+\frac{m}{n}}n-n)=\Omega(m\log_{1+\frac{m}{n}}n)\).

About Heuristic Merge

Since merging by rank is harder to implement than heuristic merging, many experts choose to implement DSU using heuristic merging. Specifically, each root maintains a \(size(x)\), and each time the smaller \(size\) is merged into the larger one.

So, can heuristic merging be exploited?

First, we can consider the properties involving rank in the proof. If \(size\) can replace the role of \(rnk\), then heuristic merging can be used. Quickly summarizing, the properties involving rank in the proof are:

1. Each merge, at most one node's rank increases, and by at most 1.
2. Always \(rnk(fa(x))\geq rnk(x)+1\).
3. A node's rank never decreases.

Regarding the second and third properties, \(siz\) clearly satisfies them. However, the first property is not satisfied: if \(x\) is merged into \(y\), then \(siz(y)\) increases by \(siz(x)\).

Thus, consider using \(\log_2 siz(x)\) instead of \(rnk(x)\).

Regarding the first property, since a node's \(siz\) at most doubles, \(\log_2 siz(x)\) increases by at most 1. The second and third properties are obvious and omitted here.

Therefore, if you do not want to implement merging by rank, use heuristic merging instead. The time complexity remains \(\Theta(m\alpha(n))\).

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用